|
On April 24 2009 10:15 Gliche wrote:
tyx's way is right. It's just that is does NOT always tell you which if it's heavier or light, but that's not required according to the op.
since byo didn't say that it's solved yet.. so there must be a 2nd solution?
no, read the problem theyango and byo brought up
if you dont know whether it's heavier or lighter within its own group, you can't find it in one more step
|
tyx just used *a variation on my method.
3 is not a guaranteed maximum.
|
tyx's method is not optimal.
Btw, if you do it cleverly enough, you can specify which balls to weigh against which before you get the results of any of your weighings.
|
For example, set A, B, C, D
if I weigh A against B
and both weigh the same
then I weigh A against C
if both weigh the same
then set D is the one with the fake in it.
At this stage you've weighed twice.
Now in set D, if I weigh D1 vs D2, and if there is a weight discrepancy, then either D1 or D2 is the fake. (weighed 3 times). In this situation you have to weigh D1 against D3 to get an answer (4th weigh).
If they weigh the same then sure, you have the answer in 3 goes.
Of course you can argue that if
A is lighter than C, then the fake coin is heavier.
In which situation, you can get the answer in 3.
But so can the other such displayed answers. So in this situation, the maximum is still 4.
|
1.) Place ABCDEF v GHIJKL on the scale. Remove a coin from each side of the scale until both sides are equal in weight.
2.) One of the last two coins removed from part one is the fake coin. So, you weigh each coin against one of the known real coins to find out which is fake
|
so.. max is 3 isn't it?
i'm too lazy to think it through but this question has appeared like a gazillion times before.
someone on tl even wrote a formula that gives you maximum # of weightings in a generalized case of n coins
|
LOL is that true, I guess I wasn't around long enough
Not so certain you can do set weighting before knowing the results....... i could be wrong.
|
On April 24 2009 10:36 Byo wrote:
LOL is that true, I guess I wasn't around long enough
Not so certain you can do set weighting before knowing the results....... i could be wrong.
You can do set weighting before knowing the results
It's pretty long winded to type out though
|
+ Show Spoiler +Three weighings.
1.. Weigh one group of 6 coins against the other 6 coins.
2.. Whichever group of 6 is heavier, measure 3 from that group against the other three. If these two groups of 3 weigh unequally, then the special coin must be heavier (since by the unequallity remaining within this group of 6 coins, the coin must be in this group, and since it is the heavier group of 6, the coin must be heavy). If the two groups of three in the heavier group of 6 weigh the same, the coin must be lighter, and in the other group of 6.
3.. If the special coin is in the lighter group of 6, weigh any 2 coins against each other from the lighter group of 3 within that group of 6. If the coin is in the heavier group of 6, weigh any 2 coins from the heavier group of 3 within that group of 6.
If the two coins weigh equally then the remaining coin from the relevant group of 3 is the coin sought. If they weigh unequally then the special coin is the heavier one if you are weighing coins out of the heavier group of 6, or the lighter coin if you're weighing coins from the lighter group of 6.
|
+ Show Spoiler +
3 Weighings:
EFGH vs IJKL
BFGK vs CDHL
CEHK vs ADGL
I think from the results of these 3 weighings you can always single out one of the coins to be the bad one.
|
United States47024 Posts
On April 24 2009 10:52 zobz wrote:+ Show Spoiler +Three weighings.
1.. Weigh one group of 6 coins against the other 6 coins.
2.. Whichever group of 6 is heavier, measure 3 from that group against the other three. If these two groups of 3 weigh unequally, then the special coin must be heavier (since by the unequallity remaining within this group of 6 coins, the coin must be in this group, and since it is the heavier group of 6, the coin must be heavy). If the two groups of three in the heavier group of 6 weigh the same, the coin must be lighter, and in the other group of 6.
3.. If the special coin is in the lighter group of 6, weigh any 2 coins against each other from the lighter group of 3 within that group of 6. If the coin is in the heavier group of 6, weigh any 2 coins from the heavier group of 3 within [that] group of 6.
If the two coins weigh equally then the remaining coin from the relevant group of 3 is the coin sought. If they weigh unequally then the special coin is the heavier one if you are weighing coins out of the heavier group of 6, or the lighter coin if you're weighing coins from the lighter group of 6.
+ Show Spoiler + Lemme work this out in A-L notation, just to see if I understand you correctly.
ABCDEF v GHIJKL
Suppose ABCDEF is heavier. Weigh ABC v DEF. If they're unequal, then the heavier one contains the fake one, and one more measurement will find it.. If they weigh the same, then the fake coin is in GHIJKL.
Now here's where I stop understanding you. If the fake is in GHIJKL and GHIJKL is lighter, how do you find a group of 3 in there thats lighter without taking a measurement? You haven't weighed within GHIJKL yet, so you can't know which group of 3 is "heavier" or "lighter".
|
On April 24 2009 10:52 zobz wrote:+ Show Spoiler +Three weighings.
1.. Weigh one group of 6 coins against the other 6 coins.
2.. Whichever group of 6 is heavier, measure 3 from that group against the other three. If these two groups of 3 weigh unequally, then the special coin must be heavier (since by the unequallity remaining within this group of 6 coins, the coin must be in this group, and since it is the heavier group of 6, the coin must be heavy). If the two groups of three in the heavier group of 6 weigh the same, the coin must be lighter, and in the other group of 6.
3.. If the special coin is in the lighter group of 6, weigh any 2 coins against each other from the lighter group of 3 within that group of 6. If the coin is in the heavier group of 6, weigh any 2 coins from the heavier group of 3 within [that] group of 6.
If the two coins weigh equally then the remaining coin from the relevant group of 3 is the coin sought. If they weigh unequally then the special coin is the heavier one if you are weighing coins out of the heavier group of 6, or the lighter coin if you're weighing coins from the lighter group of 6.
Unless I misread, I count 4 weighings if the coin is lighter.
A weighing to determine which group is heavier.
A weighing to determine if the coin is heavier or lighter.
A weighing to find the lighter group of 3 within the lighter group of 6.
A weighing to find the lighter coin from the group of 3.
|
United States47024 Posts
On April 24 2009 11:01 Slithe wrote:+ Show Spoiler +
3 Weighings:
EFGH vs IJKL
BFGK vs CDHL
CEHK vs ADGL
I think from the results of these 3 weighings you can always single out one of the coins to be the bad one.
+ Show Spoiler +This method runs into trouble, because I and J are indistinguishable. If the first measurement is unequal, and the second 2 are equal, I or J could be the fake. The following list gives the measurement results if each coin is the fake:
(E = equal, L = left is greater, R = right is greater)
A - EER
B - ELE
C - ERL
D - ERR
E - LEL
F - LLE
G - LLR
H - LRL
I - REE
J - REE
K - RLL
This could be the right way of thinking about it though. Props to you for that.
|
lol..
*edit i was too lazy to check all solutions.... perhaps all predetermined weights isn't optimum, i dunno
the solution i had was.....
+ Show Spoiler +
if abcd = efgh , i <> j, i <>k
if abcd > efgh , abe > cdf, a <> b
if abcd < efgh , abe > cdf, c <> d
|
United States47024 Posts
On April 24 2009 11:19 Byo wrote:
there its solved..... i learned something new too lol
?
Which solution solved it? Slithe's solution can't distinguish between I and J.
EDIT: was Slithe's your solution in a different combination?
|
On April 24 2009 11:14 TheYango wrote:Show nested quote +On April 24 2009 11:01 Slithe wrote:+ Show Spoiler +
3 Weighings:
EFGH vs IJKL
BFGK vs CDHL
CEHK vs ADGL
I think from the results of these 3 weighings you can always single out one of the coins to be the bad one.
+ Show Spoiler +This method runs into trouble, because I and J are indistinguishable. If the first measurement is unequal, and the second 2 are equal, I or J could be the fake. The following list gives the measurement results if each coin is the fake:
(E = equal, L = left is greater, R = right is greater)
A - EER
B - ELE
C - ERL
D - ERR
E - LEL
F - LLE
G - LLR
H - LRL
I - REE
J - REL
K - RLE
This could be the right way of thinking about it though. Props to you for that.
+ Show Spoiler +
Oh nice catch, I had a typo when converting my answer to letter format.
EFGH vs IJKL
BFGK vs CDHL
CEHJ vs ADGL
I may still have mistakes, so it would be good to verify.
|
United States47024 Posts
On April 24 2009 11:23 Slithe wrote:+ Show Spoiler +
Oh nice catch, I had a typo when converting my answer to letter format.
EFGH vs IJKL
BFGK vs CDHL
CEHJ vs ADGL
I may still have mistakes, so it would be good to verify.
Looks good, it seems you edited the 3-measurement results that I listed, so it seems consistent now.
Again, props for this way of attacking the problem.
|
United States2822 Posts
+ Show Spoiler +12 coins problem, labeled ABCDEFGHIJKL
Boolean comparison operators operate on WEIGHT, not the side that goes up or down.
eg:
ABCD > EFGH means that ABCD is heavier and on the bottom side of the scale
First weighing: ABCD vs. EFGH
Case 1: ABCD = EFGH
--This means that the counterfeit is in IJKL - weight undetermined
Case 2: ABCD > EFGH
--Counterfeit is in one of the two groups - weight undetermined
Case 3: ABCD < EFGH
--Counterfeit is in one of the two groups - weight undetermined
Case 1, Second weighing (Coins were even): IJK vs. ABC
ABC is known to be a good group, IJK is suspect.
Case 1a: IJK = ABC
IJK must also be good.
--Counterfeit is L - weight undetermined
Case 1b: IJK > ABC
IJK is heavier.
--Counterfeit is in IJK and it is heavier
Case 1c: IJK < ABC
IJK is lighter.
--Counterfeit is in IJK and it is lighter
Case 2, Second weighing (Left side heavier): ABCE vs. DIJK
ABCD may be heavy, E may be light, IJK are guaranteed good.
Case 2a: ABCE = DIJK
All of the coins tested are good.
--Counterfeit is in FGH and it is lighter
Case 2b: ABCE > DIJK
Right side contains only good coins.
--Counterfeit is in ABC and it is heavier
Case 2c: ABCE < DIJK
3 good coins + 1 bad coin on either side.
--Counterfeit is D and it is heavier OR counterfeit is E and it is lighter
Case 3, Second weighing (Right side heavier): DFGH vs. EIJK
EFGH may be heavy, D may be light, IJK are guaranteed good.
Case 3a: DFGH = EIJK
All of the coins tested are good.
--Counterfeit is in ABC and it is lighter
Case 3b: DFGH > EIJK
Right side only contains good coins.
--Counterfeit is in FGH and it is heavier
Case 3c: DFGH < EIJK
3 good coins + 1 bad coin on either side.
--Counterfeit is E and it is heavier OR counterfeit is D and it is lighter
Case 1a, Third weighing (Counterfeit coin known, but not its weight, L): L vs. A
Case 1a1: L < A
--Counterfeit is L, L is lighter
Case 1a2: L > A
--Counterfeit is L, L is heavier
Case 2c, 3c, Third weighing (Counterfeit is between two coins, but possible weights known, D and E): D vs. A
A is known to be good, counterfeit could be either D or E.
Case 2c1: D = A
--Counterfeit is E, E is lighter
Case 2c2: D > A
--Counterfeit is D, D is heavier
Case 1b, 2b, 3b, Third weighing (Counterfeit is heavy and in a group of 3 XYZ): X vs. Y
Case 1b1: X = Y
--Counterfeit is Z, Z is heavier
Case 1b2: X > Y
--Counterfeit is X, X is heavier
Case 1b3: X < Y
--Counterfeit is Y, Y is heavier
Case 1c, 2a, 3a, Third weighing (Counterfeit is light and in a group of 3 XYZ): X vs. Y
Case 1c1: X = Y
--Counterfeit is Z, Z is lighter
Case 1c2: X > Y
--Counterfeit is Y, Y is lighter
Case 1c3: X < Y
--Counterfeit is X, X is lighter
EDIT: Aah, looks like I got beaten to the punch.
|
United States47024 Posts
On April 24 2009 11:45 p3numbra wrote:+ Show Spoiler +12 coins problem, labeled ABCDEFGHIJKL
Boolean comparison operators operate on WEIGHT, not the side that goes up or down.
eg:
ABCD > EFGH means that ABCD is heavier and on the bottom side of the scale
First weighing: ABCD vs. EFGH
Case 1: ABCD = EFGH
--This means that the counterfeit is in IJKL - weight undetermined
Case 2: ABCD > EFGH
--Counterfeit is in one of the two groups - weight undetermined
Case 3: ABCD < EFGH
--Counterfeit is in one of the two groups - weight undetermined
Case 1, Second weighing (Coins were even): IJK vs. ABC
ABC is known to be a good group, IJK is suspect.
Case 1a: IJK = ABC
IJK must also be good.
--Counterfeit is L - weight undetermined
Case 1b: IJK > ABC
IJK is heavier.
--Counterfeit is in IJK and it is heavier
Case 1c: IJK < ABC
IJK is lighter.
--Counterfeit is in IJK and it is lighter
Case 2, Second weighing (Left side heavier): ABCE vs. DIJK
ABCD may be heavy, E may be light, IJK are guaranteed good.
Case 2a: ABCE = DIJK
All of the coins tested are good.
--Counterfeit is in FGH and it is lighter
Case 2b: ABCE > DIJK
Right side contains only good coins.
--Counterfeit is in ABC and it is heavier
Case 2c: ABCE < DIJK
3 good coins + 1 bad coin on either side.
--Counterfeit is D and it is heavier OR counterfeit is E and it is lighter
Case 3, Second weighing (Right side heavier): DFGH vs. EIJK
EFGH may be heavy, D may be light, IJK are guaranteed good.
Case 3a: DFGH = EIJK
All of the coins tested are good.
--Counterfeit is in ABC and it is lighter
Case 3b: DFGH > EIJK
Right side only contains good coins.
--Counterfeit is in FGH and it is heavier
Case 3c: DFGH < EIJK
3 good coins + 1 bad coin on either side.
--Counterfeit is E and it is heavier OR counterfeit is D and it is lighter
Case 1a, Third weighing (Counterfeit coin known, but not its weight, L): L vs. A
Case 1a1: L < A
--Counterfeit is L, L is lighter
Case 1a2: L > A
--Counterfeit is L, L is heavier
Case 2c, 3c, Third weighing (Counterfeit is between two coins, but possible weights known, D and E): D vs. A
A is known to be good, counterfeit could be either D or E.
Case 2c1: D = A
--Counterfeit is E, E is lighter
Case 2c2: D > A
--Counterfeit is D, D is heavier
Case 1b, 2b, 3b, Third weighing (Counterfeit is heavy and in a group of 3 XYZ): X vs. Y
Case 1b1: X = Y
--Counterfeit is Z, Z is heavier
Case 1b2: X > Y
--Counterfeit is X, X is heavier
Case 1b3: X < Y
--Counterfeit is Y, Y is heavier
Case 1c, 2a, 3a, Third weighing (Counterfeit is light and in a group of 3 XYZ): X vs. Y
Case 1c1: X = Y
--Counterfeit is Z, Z is lighter
Case 1c2: X > Y
--Counterfeit is Y, Y is lighter
Case 1c3: X < Y
--Counterfeit is X, X is lighter EDIT: Aah, looks like I got beaten to the punch.
Yeah that works. I still like Slithe's solution better. Its so much more elegant! 
|
United States2822 Posts
On April 24 2009 11:55 TheYango wrote:Show nested quote +On April 24 2009 11:45 p3numbra wrote:+ Show Spoiler +12 coins problem, labeled ABCDEFGHIJKL
Boolean comparison operators operate on WEIGHT, not the side that goes up or down.
eg:
ABCD > EFGH means that ABCD is heavier and on the bottom side of the scale
First weighing: ABCD vs. EFGH
Case 1: ABCD = EFGH
--This means that the counterfeit is in IJKL - weight undetermined
Case 2: ABCD > EFGH
--Counterfeit is in one of the two groups - weight undetermined
Case 3: ABCD < EFGH
--Counterfeit is in one of the two groups - weight undetermined
Case 1, Second weighing (Coins were even): IJK vs. ABC
ABC is known to be a good group, IJK is suspect.
Case 1a: IJK = ABC
IJK must also be good.
--Counterfeit is L - weight undetermined
Case 1b: IJK > ABC
IJK is heavier.
--Counterfeit is in IJK and it is heavier
Case 1c: IJK < ABC
IJK is lighter.
--Counterfeit is in IJK and it is lighter
Case 2, Second weighing (Left side heavier): ABCE vs. DIJK
ABCD may be heavy, E may be light, IJK are guaranteed good.
Case 2a: ABCE = DIJK
All of the coins tested are good.
--Counterfeit is in FGH and it is lighter
Case 2b: ABCE > DIJK
Right side contains only good coins.
--Counterfeit is in ABC and it is heavier
Case 2c: ABCE < DIJK
3 good coins + 1 bad coin on either side.
--Counterfeit is D and it is heavier OR counterfeit is E and it is lighter
Case 3, Second weighing (Right side heavier): DFGH vs. EIJK
EFGH may be heavy, D may be light, IJK are guaranteed good.
Case 3a: DFGH = EIJK
All of the coins tested are good.
--Counterfeit is in ABC and it is lighter
Case 3b: DFGH > EIJK
Right side only contains good coins.
--Counterfeit is in FGH and it is heavier
Case 3c: DFGH < EIJK
3 good coins + 1 bad coin on either side.
--Counterfeit is E and it is heavier OR counterfeit is D and it is lighter
Case 1a, Third weighing (Counterfeit coin known, but not its weight, L): L vs. A
Case 1a1: L < A
--Counterfeit is L, L is lighter
Case 1a2: L > A
--Counterfeit is L, L is heavier
Case 2c, 3c, Third weighing (Counterfeit is between two coins, but possible weights known, D and E): D vs. A
A is known to be good, counterfeit could be either D or E.
Case 2c1: D = A
--Counterfeit is E, E is lighter
Case 2c2: D > A
--Counterfeit is D, D is heavier
Case 1b, 2b, 3b, Third weighing (Counterfeit is heavy and in a group of 3 XYZ): X vs. Y
Case 1b1: X = Y
--Counterfeit is Z, Z is heavier
Case 1b2: X > Y
--Counterfeit is X, X is heavier
Case 1b3: X < Y
--Counterfeit is Y, Y is heavier
Case 1c, 2a, 3a, Third weighing (Counterfeit is light and in a group of 3 XYZ): X vs. Y
Case 1c1: X = Y
--Counterfeit is Z, Z is lighter
Case 1c2: X > Y
--Counterfeit is Y, Y is lighter
Case 1c3: X < Y
--Counterfeit is X, X is lighter EDIT: Aah, looks like I got beaten to the punch. Yeah that works. I still like Slithe's solution better. Its so much more elegant!
Actually, doesn't Slithe's say that it needs 4 weighings if the coin is lighter? Mine needs exactly 3 weighings regardless of the weight of the coin.
|
|
|
|
|
|
EPT
