Reader DeralterChemiker was able to solve the first problem:
Take any three coins and weigh them against any other three coins. If they weigh the same, the heavy coin is one of the other two; weigh those two coins against each other, and the heavier coin will be identified.And Secret Squïrrel solved the second problem:
If one set of three coins is heavier than the other, take two coins from the heavier set and weigh them against each other. If one of those is heavier than the other, the heavy coin has been identified. If those two coins weigh the same, the heavy coin is the third coin from that set of three.
Ok, the bonus problem requires a bit more work and a more elaborate decision tree but I'll try to be as succinct as I can. I'll label the coins with letters (A to L) so they don't get confused with my numbering of the steps.If I may offer a more general tip relating to this sort of weighing problem...
Step 1. Weigh any four coins against any other four, say ABCD - EFGH. The three possible results are: (a) balance, (b) ABCD is heavier, (c) EFGH is heavier.
(a) If they balance, then the fake coin must be one of the others (IJKL). Go to Step 2.1.
OR
(b) If ABCD is heavier, then either one of ABCD is fake and it's heavy OR one of EFGH is fake and it's light. Go to Step 2.2.
OR
(c) If EFGH is heavier, then either one of ABCD is fake and it's light OR one of EFGH is fake and it's heavy. Go to Step 2.3.
Step 2.1. (ABCD balanced EFGH).
Now weigh three known genuine coins (say ABC) against IJK. The three possible results are (a) balance, (b) ABC is heavier, (c) IJK is heavier.
(a) If they balance then L must be the fake. For your 3rd weighing, weigh it against any other coin to see whether it's heavy or light. DONE.
OR
(b) If ABC is heavier then one of IJK is the fake and it's light. For your 3rd weighing, weigh two of them against each other (say I - J). If one of them is lighter then that is the fake, otherwise it is the other one (K) and it's lighter. DONE.
OR
(c) Very similar to (a), if IJK is heavier then one of IJK is the fake and it's heavy. For your 3rd weighing, weigh two of them against each other (say I - J). If one of them is heavier then that is the fake, otherwise it is the other one (K) and it's heavier. DONE.
Step 2.2. (ABCD heavier than EFGH).
Weigh two coins from each group against one from each group plus two known genuine coins; eg IJKL are known to be not fake so weigh ABEF against CGIJ. The three possible results are (a) balance, (b) ABEF is heavier, (c) CGIJ is heavier.
(a) If they balance then the fake is one of the others, either D (and it's heavy) or H (light). For your 3rd weighing, weigh DH against IJ. If DH is heavier then D is the fake, if lighter then H is the fake. DONE.
OR
(b) If ABEF is heavier then either A or B are fake and heavy or G is fake and light. For your 3rd weighing, weigh A against B to see if one of them is the fake. If they balance then G is fake. DONE.
OR
(c) If CGIJ is heavier then either E or F are fake and light or C is fake and heavy. For your 3rd weighing, weigh E against F to see if one of them is the fake. If they balance then C is fake. DONE.
Step 2.3. (EFGH heavier than ABCD).
Perform the same weighing as for step 2.2 - weigh ABEF against CGIJ (IJ known to be genuine). The same three possible results are (a) balance, (b) ABEF is heavier, (c) CGIJ is heavier (however, the implications of these results are different from 2.2).
(a) If they balance then the fake is one of the others, either D (and it's light) or H (heavy). For your 3rd weighing, weigh DH against IJ. If DH is heavier then H is the fake, if lighter then D is the fake. DONE.
OR
(b) If ABEF is heavier then either E or F are fake and heavy or C is fake and light. For your 3rd weighing, weigh E against F to see if one of them is the fake. If they balance then C is fake. DONE.
OR
(c) If CGIJ is heavier then either A or B are fake and light or G is fake and heavy. For your 3rd weighing, weigh A against B to see if one of them is the fake. If they balance then G is fake. DONE.
It is useful to think of the problem in terms of information and possibilities. Think about how many possibilities you need to distinguish. In the first problem, there are 8 possibilities, because the fake coin can be any one of 8. In the second problem, there are 24 possibilities, since there are 12 coins which could be fake, and the fake coin could either be lighter or heavier. Every time you use the scale, there are three possible results: tilt left, tilt right, or balance. By observing the result, you have received a piece of information, basically a 0, 1, or 2.
With two weighings, you can distinguish between up to 9 possibilities. With three, you can distinguish between up to 27 possibilities.
What would have happened if, in the second problem, you tried weighing three against three instead of four against four? If the scale tilted left or right, then 6 possibilities would remain. If the scale balanced, then 12 possibilities would remain. Since you can only use the scale two more times, it is impossible to distinguish between all 12 of these possibilities. So you know you were on the wrong track.
Trial and error should get you the rest of the way.
4 comments:
Nice! I didn't think very much about your last puzzles when I read them, but perhaps I'll try to solve some of the next ones :)
Your advices at the end of the post are very useful. Thanks!
Miller, following on from your general tip, I was thinking that if you can distinguish between 27 possibilities, it might be therefore be possible to determine which of 13 coins is fake. However, that doesn't seem to be the case and I stand by what said in my second comment on the puzzle post.
The problem is that 3 of the "possible" data series are actually not. Using your 0, 1, 2 scheme, where 0 means left pan heavy, 1 is balance and 2 is right heavy; it can immediately be seen that getting a 1 for each of the 3 weighings (111) would mean that none of the coins were fake. Two other combinations will not occur because they are self-contradictory. The numbers will vary depending on what coins you choose for each weighing, but with the solution I gave, they are 011 and 211.
If anybody's interested, here is the complete dataset with results. The numbers refer to the steps in my solution. Alphabetically "lower" coins (listed first in the solution) are always in the left pan.
2.1a
110 - L light
112 - L heavy
111 - no fake
2.1b
100 - J lt
102 - I lt
101 - K lt
2.1c
120 - I hv
122 - J hv
121 - K hv
2.2a
010 - D hv
012 - H lt
011 - not possible as fake is definitely in the last weighing
2.2b
000 - A hv
002 - B hv
001 - G lt
2.2c
020 - F lt
022 - E lt
021 - C hv
2.3a
210 - H hv
212 - D lt
211 - not possible as fake is definitely in the last weighing
2.3b
200 - E hv
202 - F hv
201 - C lt
2.3c
220 - B lt
222 - A lt
221 - G hv
Here is a simple solution to the 12 coin problem:
Form three (3) main groups – each containing 1 and 3 coin sub-groups. Place one main group on each pan of a two pan balance – the third main group on the table. Observe the condition of the balance. This is the first weighing.
Rotate the 3 coin sub-groups (from pan A to the table, pan B to pan A, and from the table to pan B. Observe the condition of the balance. (second weighing).
If there is a change, it will identify the 3 coin group that contains the odd coin and its relative weight. In this case, clear the area of all other coins. Split this group into single coins, placing two on the pans of the balance. This willl be the third weighing and will identify the odd coin. We already know its relative weight. Problem solved.
If there is no change, one of the single coins (two of which are already on the pans of the balance) is the odd coin. In this case, rotate the single coins. This will be the third weighing an will identify the odd coin and its relative weight. Problem solved.
A better problem is:120 coins/5 weighings. It is just as easy, but a little longer
Nice! It took a moment to understand, but the solution has an intuitive quality, and is generalizable to larger problems. You could use your solution to prove that (3^n-3)/2 coins is the best you can do with n weighings.
Post a Comment