logical deduction - 121 coins and a balance

Inspired by this puzzle...

You have $121$ apparently identical gold coins. At most one of these is fake, and weighs a different amount than a genuine coin.

In front of you is balance with two pans. In your pocket you have a single coin which you know is genuine.

What is the minimum number of weighings it takes to find the fake (if there is one), and determine whether it is heavier or lighter than the others?

Hint:

Use your first weighing to reduce this to a similar problem, but with fewer coins.

Answer

Lemma. Given a set $A$ of coins that may be too heavy, a set $B$ of coins that may be too light. Assume $A\cap B=\emptyset$ and exactly one of the coins is a fake. If $|A|+|B|=3^k$, then the fake coin can be determined in $k$ weighings.

Proof. If $k=0$, there is nothing to be shown. Assume the lemma is true for soem $k$; we shall show that it also holds for $k+1$: Partition $A$ into three nearly equal-sized sets $A_1,A_2,A_3$ (that is, $\lfloor\frac {|A|}3\rfloor\le |A_i|\le \lceil\frac {|A|}3\rceil\le 3^k$). Since only two possible sizes are possible, at least two of the $A_i$ have the same size. Without loss of generality, $|A_1|=|A_2|$. Now we can partition $B$ into sets $B_1,B_2,B_3$ with $|B_i|=3^k-|A_i|$ Put the coins from $A_1\cup B_2$ into the left pan, $B_1\cup A_2$ into the right pan. Ignore the coins in $A_3\cup B_3$. Note that both pans contain the same number of coins. Now if the left pan goes down, we know that the fake coin is $\in A_1\cup B_1$; if the right pan goes down, the fake coin is $\in A_2\cup B_2$; if the pans weigh the same, the fake coin is $\in A_3\cup B_3$.At any rate, the induction hypothesis applies. $_\square$

Proposition. Given a known good coin and $\frac{3^k-1}2$ coins among which there may be exactly one too heavy or too light fake coin or no fake coin at all. It is possible to determine which coin is fake and in which way, or that there is no fake coin, in $k$ weightings.

Proof. Again induction. For $k=0$, there is nothing to be shown. Assume the proposition holds for $k$; we shall show that it also holds for $k+1$: Put the known good coin and $\frac{3^k-1}2$ coins into the left pan, $\frac{3^k+1}2$ into the right pan, and leave the remaing $\frac{3^k-1}{2}$ coins aside. If the left pan goes down, we have $\frac{3^k-1}2$ coins that may be too heavy, $\frac{3^k+1}2$ that may be too light, and the rest is known good. By the lemma, we can finish with $k$ more weighings. The case with the right pan going down is similar: we have $\frac{3^k+1}2$ coins that may be too heavy, $\frac{3^k-1}2$ that may be too light, and the rest is known good. Finally, if both pans weigh the same, we are left with the $\frac{3^k-1}2$ unused coins among which there may be a fake coin or not. By induction hypothesis, this can be solved with $k$ weighings. $_\square$

Remark. Since it is clar that it takes at least $k$ weighings to distinguish among $3^k$ possible outcomes, the result of the proposition is best possible.

Corollary. The puzzle with $121$ coins can be solved in $5$ weighings.