If you haven't done any of the other coin problems, then you might want to go back and try those now, this one is very difficult, even if you have figured out the other ones.

This time, as the title implies, there are 39 coins, and one is fake. You have a balance scale, which can be used 4 times.

How would you find the fake coin?

If we number the coins 1-39, we’d like to place the coins on the left (L) or right(R) according to the following schedule for the four weighings:

1 LLLL
2 -LLL
3 RLLL
4 L-LL
5 --LL
6 R-LL
7 LRLL
8 -RLL
9 RRLL
10 LL-L
11 -L-L
12 RL-L
13 L--L
14 ---L
15 R--L
16 LR-L
17 -R-L
18 RR-L
19 LLRL
20 -LRL
21 RLRL
22 L-RL
23 --RL
24 R-RL
25 LRRL
26 -RRL
27 RRRL
28 LLL-
29 -LL-
30 RLL-
31 L-L-
32 --L-
33 R-L-
34 LRL-
35 -RL-
36 RRL-
37 LL--
38 -L--
39 RL--
where a hyphen indicates to leave that coin off for that weighing.

These are based on the ternary representation of one less than the coin number, with L representing 0, - representing 1, and R representing 2, and presented low order to high order. Note that no two lines exist where one is the same as the other with L's replaced by R's and vice versa, so for example, if the left pan went down every time except for the 3rd weighing, we'd know that coin 19 was heavy as there is no line that has RRLR which could indicate that its coin was light.

However there is a problem: the second weighing has three more coins on the left pan than on the right; the third has 9 more on the left than the right; and the fourth has all 27 of its coins on the left.

This can be remedied, however. After the first weighing, there are either 13 or 26 coins that we know to be good. During the second weighing, any three of these can be reallocated: if one was to appear on the left, it can be left out, or if it was to be left out it could be put on the right. The same applies to weighing 3, as the imbalance is only 9 and we have 13 to work with.

On the fourth weighing, there are 27 coins scheduled to appear on the left pan. But at least 19 of those can be known from one of the previous weighings or another to be good. And instead of leaving any one of those off, it can be switched to the right pan, and that counts for two in balancing the sides. As an odd number must be accounted for, one can be merely not placed on a pan.

Then simply find the pattern of Ls and Rs on the above chart. Only one will be found, and it will apply to the given pan either going up or going down (as mentioned before, there is no corresponding negative value of, say, LLR- vs RRL-).

So, for example, if the left pan went up, you'd know that all those that weren't weighed in the first weighing are good. So in weighing 2 you'd place the coins as per the second column above, except you'd leave, say, coins 2, 11 and 20, known to be good, off, instead of on the left pan. Say this time the pans balanced. All the coins on each balance are now known to be good, so in the next weighing, number 3, place all the coins as per the third column except 2, 3, 5, 7, 8, 9, 28, 29 and 30, as these would be scheduled for the left pan but can be left off as they are knwon to be good from either not being weighed in weighing 1, or being weighed in weighing 2. Say in weighing 3, the left side goes down again. Then place coins 1-27 on the left pan, except for 1, 2, 3, 5, 7, 8, 9, 10, 11, 12, 13, 14 and 15, which are to be placed on the right pan instead, and 16, which is to be left off, as these are known to be good from the previous weighings and allow an equal number of coins on the two pans. Now, if neither side goes down, we match the results to line 31 representing coin 31, and since the corresponding side, L, went down each time, it is heavier than the rest.

Posted by Charlie on 2003-04-23 13:12:14