even harder coin problem
Each weighing can have three possible outcomes: R(ight), L(eft), or B(alance). The three weighings taken together can have 3x3x3=27 possible outcomes, from which we must identify 24 different results (12 heavy coins and 12 light coins). 3 of the 27 outcomes must be impossible (in my solution, BBB, RRR, and LLL) and each of the other 24 must uniquely identify one of the 24 results.
Here is a solution that accomplishes that (arrived at by a much messier process than I'm about to describe).
Each weighing will have four coins on each side of the balance. Three coins will be used only once, six coins will be used twice, and three will be used three times.
Select three coins (1, 2, 3) that will be used in all three weighings. On each weighing, put a different one of these on the left side and put the other two on the right.
The six results that have one R two Ls or one L two Rs will occur when one of these three coins is bad. Take the result that disagrees with the other two (the one R or the one L). The coin on the left is bad. If the result is L, it's heavy; R means light.
Select three more coins (4, 5, 6) that will be used in only one weighing. On each weighing, put one of these coins on the right (together with two of 1, 2, 3).
The six results that have two Bs and one R or L will occur when one of these coins is bad. Take the result that isn't B. The coin on the right is bad. If the result is L, it's light; R means heavy.
The other six coins (7, 8, 9, 10, 11, 12) will be used in two weighings. Pick two of these coins. Select one weighing where both coins will be on the left side, one weighing where one will be on the right and the other on the left, and one weighing where they will not be used. Do the same thing for another two of the remaining four. Do the same for the remaining two.
Here is an example of a possible arrangement:
1 7 8 9 x 2 3 4 10
2 7 11 12 x 1 3 5 8
3 9 10 11 x 1 2 6 12
The twelve results that have one B and any combination of Rs and Ls will occur when one of the last six coins is bad. Take the B result. Two coins are not part of this weighing. One of them is bad. Take the result where both of these coins were on the left side. If the result is L, the bad coin is heavy; R means light. Take the remaining result (with one of the suspects on one side and the other suspect on the other side). This result tells you which of the two coins is bad. (You already know whether you are looking for a light coin or a heavy coin.)
Friday, July 26, 2002
Fog Creek Home