Among $239$ coins identical in appearance there are two counterfeit coins. Both counterfeit coins have the same weight different from the weight of a genuine coin. Using a simple balance, determine in three weighings whether the counterfeit coin is heavier or lighter than the genuine coin. A simple balance shows if both sides are in equilibrium or left side is heavier or lighter. It is not required to find the counterfeit coins.
Problem
Source:
Tags: weighings, combinatorics
06.06.2022 23:10
Solved with $\textit{JustinLee2017}$. Split the coins into three groups of $80$, $80$, and $79$ coins respectively. Denote these groups $G_1$,$G_2$, and $G_3$ respectively. Call a group clean if it has no counterfeits and dirty if it does. First weigh $G_1$ and $G_2$. Let $W(G)$ denote the weight of group $G$. We now split into cases depending on the results of the first weighing. $\textbf{Case 1:}$ $W(G_1)=W(G_2)$ Split $G_1$ into two groups, $G_{1a},G_{1b}$ with $40$ coins each. If $W(G_{1a})=W(G_{1b})$, then $G_1$ and $G_2$ are clean. Now take $79$ coins from $G_1$ and weigh with $G_3$. If $W(G_3)>W(G_1)$, the counterfeits are heaver. If $W(G_3)<W(G_1)$, the counterfeits are lighter. If $W(G_{1a}) \neq W(G_{1b})$, WLOG $W(G_{1a})>W(G_{1b})$. Take $40$ coins (denote this group $G_{3a}$) and weigh them with $G_1$. If $W(G_{1a})=W(G_{3a})$, then $G_{1a}$ is clean and $G_{1b}$ is dirty. Thus, since $G_{1b}<G_{1a}$ the counterfeits are lighter. If $W(G_{1a})>W(G_{3a})$, the counterfeits are heavier. If $W(G_{1a})<W(G_{3a})$, the counterfeits are lighter. $\textbf{Case 2:}$ $W(G_1)\neq W(G_2)$ WLOG $W(G_1)>W(G_2)$. Clearly, either $G_1$ or $G_2$ is dirty but not both. Split $G_1$ into two groups of $40$ coins each. Weigh these. If the two groups are not equal, then $G_1$ is dirty. Thus, the counterfeits are heavier since $W(G_1)>W(G_2)$. If the two groups are equal then either $G_1$ is clean or has two counterfeits. If $G_1$ is dirty, then $G_{1a}$ and $G_{1b}$ both have a counterfeit. Now split $G_{1a}$ into two groups of $20$ coins each. Weigh these groups. If they are equal, then $G_{1a}$ is clean, and it follows that $G_2$ is dirty implying the counterfeits are lighter. If the weights of two groups of $20$ coins aren't equal then $G_1$ is dirty implying the counterfeits are heavier. Having exhausted all cases in $3$ weighings, we are done. $\blacksquare$