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{eqnarray*} 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{eqnarray*}
And, we also have\begin{eqnarray*} 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{eqnarray*}
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.
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) \le H(R_1^4) \le 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.