Fog Creek Software
Discussion Board




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 08, 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 non-adaptive structure in all cases, since the non-adaptive 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 14-27 | 28-40 X
--- Weigh 1-4 13 14-18  | 5-8 X 19-22 33-36 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 3-weigh 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 3-weighings 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 13-coin 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 forty-coin problem:

First:
14-27 | 28-40 x

Second:
1 2 3 4 5 | 6 7 8 9 X
14-18 | 28-31 X
32-36 | 19-22 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