7
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Interesting but probably useless observation: it doesn't look like the Minister's proclamation can hold true if both H and L are rational. For example, if H=5 and L=4, then h1=4,l1=0 has the same weight as h2=0,l2=5. The proclamation might hold for H=pi, L=3, though. $\endgroup$ – Kevin Oct 16 '15 at 16:53
  • $\begingroup$ @Kevin Can a coin have a weight of $\pi$? $\pi$ is not a finite number, so I don't see how it can apply to a finite quantity like the weight of a coin. The weight could be arbitrarily close to $\pi$, but wouldn't it still always have to be a rational number? $\endgroup$ – GentlePurpleRain Oct 18 '15 at 3:43
  • $\begingroup$ @Kevin it will also hold for some rational numbers as long as the total amount of coins is finite $\endgroup$ – DrunkWolf Oct 18 '15 at 6:04
  • 1
    $\begingroup$ @GentlePurpleRain it's quite possible for a coin to weigh exactly $\pi$ if the weight of a single atom is $\pi/x$ for some $x$. I would actually say that it's quite impossible for the weight to be a rational number because that would mean that a single atom would also need to have a rational weight and I don't think that happens in nature. With of course the very single exception if you make the coin of the material that is used to define the kilogram. $\endgroup$ – Ivo Beckers Oct 19 '15 at 8:37
  • $\begingroup$ @IvoBeckers It is impossible for a coin to weigh exactly π. It could weigh π units, but not just π. But you can always convert to a different unit where the value becomes a rational number again. Like how 2π radians is exactly 360 degrees. $\endgroup$ – Falc Jul 29 '16 at 9:05
13
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ I wrote a short script which went through all possible arrangements of heavy and light coins (1024), and discovered that this solution only gives 3 balanced weighings when all are heavy or all are light, ie confirms that it is correct. $\endgroup$ – Dr Xorile Oct 16 '15 at 21:26
1
$\begingroup$

I don't think it's possible. I can ID up to 8 coins in 3 trials by:

Weigh 1v1, if different, we have our answer.
Weigh 2(previous)v2
Weigh 4(prev)v4

This allows us to check up to 8 coins.

$\endgroup$
1
$\begingroup$

I believe that the answer is

No, it is not possible.

To explore why it isn't possible, let's look at a similar problem, with eight coins, numbered C1-C8.

Put four coins on each side of the balance.

C1-C4 vs C5-C8

If the balance is not equal, then we're done. We know for a fact that there are two weights of coins in the pile, and we don't need to go any further.

If, on the other hand, the balance does NOT move, then the two piles have equal numbers of each type of coin, and could conceivably all be the same weight. So the next step is to take C1-C4 and place two coins on each side of the balance.

C1&C2 vs C3&C4

Again, if the balance moves, we're done. If, on the other hand, the balance stays even, we will do one more test

C1 vs C2

Now, if the balance is STILL even, all of our coins are the same weight.

The 10 coin example doesn't work out quite as well, though. After the first weighing, we're left with five coins and two weighings, which is not enough to identify the coins. One weighing can identify two coins, two weighings can identify four, three weighings can identify eight.

There are some methods that can solve these problems more efficiently with larger numbers of coins, but the total number usually has to be divisible by 3 or 4. With 10 coins, I don't believe it can be done in 3 actions

$\endgroup$
  • 2
    $\begingroup$ What about if C1..10 = {H, L, H, L, L, H, L, H, L, L}? It will pass your test, but the coins are not all the same weight. Is there something I'm missing? $\endgroup$ – ard Oct 16 '15 at 15:47
  • $\begingroup$ You're right, there's definitely a problem with my answer. My method would've worked with 8 coins, but not 10. I'll try to devise a way to deal with the odd number of coins on the second and third trials. $\endgroup$ – The Other David Oct 16 '15 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.