In the country of Ebbozonia, there are only two type of coins: light coins and heavy coins. The weights of these coins satisfy the following properties:
- All light coins have the same weight $L$.
- All heavy coins have the same weight $H$.
- Heavy coins are heavier than light coins: $H>L$
The precise values of $L$ and $H$ are not known to the public. The difference between $L$ and $H$ should be fairly small, as there is no way of distinguishing the two coin types without a balance. His Highness, the Honourable Minister of Treasury, has recently announced the following important property of the Ebbozonian coin system:
- If a balance is in perfect equilibrium with $h_1$ heavy and $\ell_1$ light coins on the right pan and with $h_2$ heavy and $\ell_2$ light coins on the left pan, then $h_1=h_2$ and $\ell_1=\ell_2$ must necessarily hold true.
Cosmo puts 10 Ebbozonian coins on the table and asks Fredo to determine quickly whether these 10 coins all have the same weight. On the table, there is a balance with two pans (but there are no weights).
Question: Can Fredo solve Cosmo's problem by using the balance at most three times?
Answer
The answer is
Yes
I ran a test with 6 coins, leaving 2 off each time. I got that to work. This made me think I could scale it up to 10 coins by doing 3 on each side. I tried that and got all the cases where 2 coins were different, but 3 coins would stop me (and I thought only the even sets would be a problem). That made me try a different number of coins in each weighing. That's when I found:
Weighing 1: 1 2 3 vs 4 5 6
Weighing 2: 1 2 3 6 vs 7 8 9 10
Weighing 3: 1 2 3 4 5 vs 6 7 8 9 10
No comments:
Post a Comment