Solving Coin-Weighing Problem (81 Coins, 1 Fake) Using Information Theory

Question

So I have a coin-weighing puzzle under these situations:

There are 80 real coins and 1 fake coin (total of 81 coins).
The real coins are all the same weight, and the weight of the fake coin is different from the real coin.
The real and fake coins cannot be distinguished, other than weight.
A balance is used to identify the fake coin.
When using the balance, the same number of coins is placed on either plate. The result is either "the left plate is heavier," "the right plate is heavier," or "the two plates are the same weight."

According to prior research, this problem cannot be solved by using the balance 4 times or less. I tried to show this by using information theory as follows, but I feel like I am missing something here.

Label the coins 1,...,81, and let $C$ be the number of the fake coin. Also, let $W$ be a random variable defined so that $W = 1$ when the fake coin is heavier than the real coin, and $W = 0$ when lighter. At the initial state, $C$ and $W$ can be regarded as independent random variables following a uniform distribution.

Then, define random variable $R_{k}$ so that $R_{k} = 0$ , $R_{k} = 1$ , $R_{k} = 2$ , when, the result after using the balance for the $k$ th time is, respectively, "the left plate is heavier," "the right plate is heavier," or "the two plates are the same weight."

Then, $R_{k}$ can be regarded as uniquely determined by $R_{1}, . . ., R_{k},$ and the real values of $C$ and $W$ . (Do I have to add additional proof that this is true?)

Assume that the fake coin can be surely identified by four measurements using the balance, then this means that the value of $C$ is determined when $R_{1}, . . ., R_{4}$ have been determined. Thus, using the entropy function and its chain rule,
$\begin{array}{rcl} H (C, W, R_{1}, . . ., R_{4}) & = & H (C) + H (R_{1} | C) + H (R_{2} | R_{1}, C) + H (R_{3} | R_{2}, R_{1}, C) + H (R_{4} | R_{3}, R_{2}, R_{1}, C) + H (W | R_{4}, R_{3}, R_{2}, R_{1}, C) \end{array}$

And, we also have
$\begin{array}{rcl} H (C, W, R_{1}, . . ., R_{4}) & = & H (W) + H (C | W) + H (R_{1} | C, W) + H (R_{2} | R_{1}, C, W) + H (R_{3} | R_{2}, R_{1}, C, W) + H (R_{4} | R_{3}, R_{2}, R_{1}, C, W) \end{array}$

Then we notice that $H (C | W) = H (C)$ , as $C$ and $W$ are independent variables. Also, $H (R_{1} | W, C) < H (R_{1} | C), H (R_{2} | R_{1}, C, W) < H (R_{2} | R_{1}, C)$ , and so on. Thus, from the two equations, we get $H (W) < H (W | R_{1}, . . ., R_{4}, C)$

But we know that $H (W | R_{1}, . . ., R_{4}, C) < H (W)$ , so there is a contradiction.

OK. So I somehow arrived at a contradiction, showing that the problem cannot be solved by using the balance for times. But then I realized that the same logic applies when using the balance for any number of times, so apparently there is something wrong...

What sort of logic am I missing? I would appreciate any help.

Oh boy...seems like I have made a stupid mistake in the final statement. — Kay, Jan 4 at 6:26

stochasticboy321 · Accepted Answer · 2021-01-04 22:43:39Z

Brian has pointed out your error correctly. However, your approach is almost there (this is basically a formalised version of wendy's argument):

I'll use $R_{1}^{4}$ to denote the joint random variables $(R_{1}, R_{2}, R_{3}, R_{4}) .$ Notice that if $(C, W)$ can be determined using $R_{1}^{4}$ then $H (C, W | R_{1}^{4}) = 0$ (this is the key point that you did not use in your attempt). But then

H (C, W, R_{1}^{4}) = H (C, W) + H (R_{1}^{4} | C, W) = H (R_{1}^{4}) + H (C, W | R_{1}^{4}) = H (R_{1}^{4}) .

Since entropies are non-negative, this means that

H (C, W) \leq H (R_{1}^{4}) \leq 4 \log 3,

where I've used the fact that

R_{1}, R_{2}, R_{3}, R_{4}

are ternary, and the upper bound on entropy provided by log of the support size. But

H (C, W) = H (C) + H (W) = 4 \log 3 + \log 2 > 4 \log 3

gives a contradiction.

Just for completeness, in this case $5$ weighings suffice - divide the $81$ coins into three groups of 27. Measure the first two groups, and then the second and the third groups. This tells you both if the anomalous coin is heavier or lighter, and which of the three groups it lies in. Divide this group into three groups of $9$ , and measure the first two - since you know the direction of the anomaly, this reduces the identity of the anomalous coin to $9$ options. Doing this division into three groups two more times fixes the coin in a total of $5$ measurements.

Thank you for your answer. This is very helpful. – Kay Jan 5 at 2:26 — Kay, Jan 5 at 2:26

wendy.krieger · Accepted Answer · 2021-01-04 06:15:12Z

2

You have 162 possible outcomes. You can't do light and heavy in just four trinary weighs. The usual means is 12 in three weighs or 120 in five. This gives 24 or 240 outcomes.

answered Jan 4 at 6:15

wendy.krieger

6,4241 gold badge17 silver badges31 bronze badges

Thank you for the comment. – Kay Jan 5 at 2:27

Add a comment |

Brian Moehring · Accepted Answer · 2021-01-04 06:21:39Z

The conclusion in this statement is wrong:

Then we notice that $H (C | W) = H (C)$ , as $C$ and $W$ are independent variables. Also, $H (R_{1} | W, C) < H (R_{1} | C), H (R_{2} | R_{1}, C, W) < H (R_{2} | R_{1}, C)$ , and so on. Thus, from the two equations, we get $H (W) < H (W | R_{1}, . . ., R_{4}, C)$

The conclusion would be $H (W) > H (W | R_{1}, \dots, R_{4}, C)$ .

Your logic would be like saying "If $a + b = c + d$ and $b < c$ , then $a < d$ " The inequality is backwards.

Thany you for pointing it out. Not sure why I never realized this... — Kay, Jan 5 at 2:27

Solving Coin-Weighing Problem (81 Coins, 1 Fake) Using Information Theory

3 Answers 3

Your Answer

Not the answer you're looking for? Browse other questions tagged discrete-mathematics stochastic-processes information-theory stochastic-analysis entropy or ask your own question.

Hot Network Questions

Solving Coin-Weighing Problem (81 Coins, 1 Fake) Using Information Theory

3 Answers 3

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged discrete-mathematics stochastic-processes information-theory stochastic-analysis entropy or ask your own question.

Related

Hot Network Questions