
even harder coin problem
I haven't seen a solution for this one, so here's mine.
Assign the coins numbers 1 to 12.
The first weighing is 1 2 3 4  5 6 7 8
The second weighing is 1 5 6 7  9 10 11 8
The third weighing is 1 2 5 9  3 6 10 12
The scale can show each one of three positions:
left side down ( / ), flat (  ), or right side down ( \ )
The following table of options then gives us the possible solutions.
Each line shows the result of the 3 weighings, with
conclusion.
/ / / 1 is heavy
/ /  8 is light
/ / \ impossible
/  / 2 is heavy
/   4 is heavy
/  \ 3 is heavy
/ \ / 6 is light
/ \  7 is light
/ \ \ 5 is light
 / / 10 is light
 /  11 is light
 / \ 9 is light
  / 12 is light
   impossible
  \ 12 is heavy
 \ / 9 is heavy
 \  11 is heavy
 \ \ 10 is heavy
\ / / 5 is heavy
\ /  7 is heavy
\ / \ 6 is heavy
\  / 3 is light
\   4 is light
\  \ 2 is light
\ \ / impossible
\ \  8 is heavy
\ \ \ 1 is light
While on this subject, is it possible to differentiate more than 12 coins in 3 weighings, given a pile of 'known good coins', adaptive weighing allowed. (Hint, it is :) )
Generalizing further, given 4 weighings, how many coins can I cope with. (n weighings, anyone?)
Paul Viney
Wednesday, March 27, 2002
when adaptive weighing is not allowed.
take  / \ symbols as a part of a no. system. let ~ of these symbols be  \ / respectively. further suppose that a no. x under such a system made of 3 digits represents that coin n is heavy. then ~x means that the same coin is light.
with 3 digits in such a number system we can form 3*3*3 different numbers. of which  is invalid no. because there is atleast one coin with different weight. now we are left with 26 possible numbers. So we can do upto 13 coins with 3 weighings without being adaptive. moreover if we don't need to find out whether the bad coin is heavy or light we can do upto 14 coins with 3 weighing without being adaptive. in which  would mean the 14th coin is bad. I think extending it to n weighings should be easy.
Don't know how much increase in the numbers would adaptive weighing bring. But it will definitely be good....
****
Monday, April 8, 2002
I'm under the impression that, given N weighings, you can differentiate the counterfeit in up to the theoretical limit of M = [(N^3)/2] coins.
That is, with respect to coins, since there are 2M possible outcomes, all you need is the lowest N such that N^3 > 2M.
I believe this should be doable in a nonadaptive structure in all cases, since the nonadaptive solution is just all of the adaptive cases piled on top of each other without actually adding complexity.
I believe you'll need to assume you have some bank of normal coins, which I'll label "X." The weighings below work, I'll leave it up to you to deduce the unambiguous results.
1 weighing: [(N^3)/2)] = 0 coins
 Not surprising.
2 weighings: [(N^3)/2] = 4 coins
 Weigh 1 2  3 X
 Weigh 1 4  2 X
3 weighings: [(N^3)/2] = 13 coins
 Weigh 1 2 3 4 13  5 6 7 8 X
 Weigh 1 2 5 9 X  3 6 7 10 11
 Weigh 1 3 7 10 12  2 4 8 11 X
4 weighings: [(N^3)/2] = 40 coins
 Weigh 1427  2840 X
 Weigh 14 13 1418  58 X 1922 3336 X X
By the end of weighing two, the problem has broken down to one of two scenarios:
1) If it balanced to begin with, then it's just the 13 coin problem above, and I've reproduced weighing#1 here as weighing#2.
2) If it didn't balance, we're either at 4 potentially heavy/5 potentially light or vice versa.
3) The 4/5 scenario is easily solvable from the 3weigh by placing AAB and AAB on each side of the scale, where "A" is in the group of 5 and "B" is in the group of 4. This is what is done in weighing #2 for the 3weighings scenario.
Note) If it sounds like I'm getting adaptive, I'm not, you just pile each of your scenarios on top of each other. (for example, if it's scenario (1) above, then there's just an extra pile of dummy coins piled on each side of the scale.
Here's the third weighing, broken into scenarios (14 on each side)
 Weigh 1 2 5 9 X  3 6 7 10 11
 With 14 15 33  16 17 34
 With 28 29 19  30 31 20
 With 23 24 37  25 26 38
Here's the fourth (also 14 on each side):
 Weigh 1 3 7 10 12  2 4 8 11 X
 With 14 16 35  15 17 36
 With 28 30 21  29 31 22
 With 23 25 39  24 26 40
I haven't thought it through, and I am sort of guessing on the weighings, but I believe the above should be appropriate. (I haven't actually tested the proposed solution)
Michael Feng
Monday, April 15, 2002
Hm. Whoops. I think I mixed up my labeling there.
Here are the weighings for the 13coin problem:
1 2 3 4 5  6 7 8 9 X
1 2 6 10 X  3 4 7 11 12
1 3 8 11 13  2 4 9 12 X
Here are the four weighings for the fortycoin problem:
First:
1427  2840 x
Second:
1 2 3 4 5  6 7 8 9 X
1418  2831 X
3236  1922 X
(If you want 14 coins per side, just flip one set above and remove the redundant "X"s)
Third weighing should be:
1 2 6 10 X  3 4 7 11 12
14 15 28  16 17 29
32 33 19  34 35 20
23 24 37  25 26 38
Fourth should be:
1 3 8 11 13  2 4 9 12 X
14 16 30  15 17 31
32 34 21  33 35 22
23 25 39  24 26 40
That sounds more correct. . .
Michael Feng
Monday, April 15, 2002
Oh, and that's 3^N, not N^3.
Michael Feng
Monday, April 15, 2002
40 coins in 4 weighings is absolutely right, PROVIDED you have at least one extra coin which you know is good (a "reference coin"). Otherwise, you can handle only 39.
To be more precise, with N weighings, you can distinguish ((3^N)3)/2 coins, if you have no known good coins. So with 5 weighings, you could handle 121 coins.
If you have a reference coin, the formula becomes ((3^N)1)/2  you can squeeze in an extra coin. So for 1 weighing, you can actually test one coin successfully. 4 for 2, 13 for 3, etc.
Paul Brinkley
Tuesday, April 16, 2002
You've both come up with the answer I came up with. I'm fairly sure it's correct, although I haven't proved it rigorously. The extra coin helps because you want to handle coins in sets of 3s once you have light/heavy infomation, three coins being the maximum you can handle in one go once you know whether they're heavy or light.
With 2 weighings + a reference coin you weigh 1 +3
With 3 weighings + a reference coin you weigh 1 + 3 +9
With 4 weighings + a reference coin you weigh 1 + 3 + 9 + 27
Without the reference coin you can't squeeze in the last set of three because the scales would be unbalanced.
Paul Viney
Paul Viney
Tuesday, April 16, 2002
Recent Topics
Fog Creek Home
