I face a question as follow from my friend. I wonder whether we can identify the location of counterfeits or just the number of coins lie between them.
Given 16 identical coins in a row. There is exactly one counterfeit coin in the first 8 coins (Left group) and exactly one counterfeit coin in the last 8 coins (Right group). Both counterfeit coins have the same weight, which is lighter than a genuine coin. We need to determine the number of genuine coins located between the two counterfeit coins using exactly three weighings on a balance scale (without standard weights). Each weighing may place any number of coins on each side.
This is my try!
Let the position of the counterfeit coin in the Left group be $x$, with $1 \le x \le 8$.
Let the position of the counterfeit coin in the Right group be $y$, with $9 \le y \le 16$.
The number of genuine coins to be found is $y - x - 1$.
We perform the three weighings as follows:
- Weighing 1:Left $\{1, 2, 5, 6, 9, 10, 13, 14\}$ and Right Pan $\{3, 4, 7, 8, 11, 12, 15, 16\}$
- Weighing 2: Left $\{1, 3, 5, 7, 9, 11, 13, 15\}$ (The coins at odd positions) and Right $\{2, 4, 6, 8, 10, 12, 14, 16\}$ (The coins at even positions)
- Weighing 3:Left $\{1, 2, 3, 4, 13, 14, 15, 16\}$ and $\{5, 6, 7, 8, 9, 10, 11, 12\}$
For each weighing $k \in \{1, 2, 3\}$, we define a property $C_k(n)$ for each coin $n \in \{1, \dots, 16\}$: $$ C_k(n) = \begin{cases} +1 & \text{if coin } n \text{ is on the left pan in weighing } k \\ -1 & \text{if coin } n \text{ is on the right pan in weighing } k \end{cases} $$ The outcome of weighing $k$ depends on the sum $C_k(x) + C_k(y)$. Since the counterfeit coins are lighter, we have:
Left pan is lighter ($\downarrow$): $C_k(x) + C_k(y) > 0 \implies C_k(x) = +1$ and $C_k(y) = +1$.
Right pan is lighter ($\uparrow$): $C_k(x) + C_k(y) < 0 \implies C_k(x) = -1$ and $C_k(y) = -1$.
Balanced ($=$): $C_k(x) + C_k(y) = 0 \implies C_k(x) = -C_k(y)$. Each weighing gives us the exact pair of values $(C_k(x), C_k(y))$ if the scale is unbalanced, or tells us they are opposite if the scale is balanced.
We define a property vector for each coin $n$ as $\vec{v}(n) = (C_1(n), C_2(n), C_3(n))$. Let $y' = y - 8$, with $1 \le y' \le 8$.
The weighings are designed in a special way to have the following relationships:
$C_1(y) = C_1(y')$, due to the repeating structure for the two groups of 8 coins.
$C_2(y) = C_2(y')$, due to the repeating structure for the two groups of 8 coins.
$C_3(y) = -C_3(y')$, because the group $\{9, \dots, 12\}$ is on the right pan while the group $\{1, \dots, 4\}$ is on the left, and similarly for the other groups.
Everything works well, except when the scale is balanced all three times. Can I improve this strategy, or do you have any hints?
