2014 OIM Problems/Problem 4

Problem

There are $N$ coins, of which $N-1$ are authentic of equal weight and one is false, of different weight than the others. The objective is, using exclusively a two-dimensional scale with dishes, find the fake coin and determine if it is heavier or lighter than the authentic ones. Whenever it can be deduced that one or more coins are authentic, then all those coins are separated immediately and cannot be used in subsequent weightings. Find all $N$ for which the objective can be achieved with certainty. (You can do so many weightings as desired.)

~translated into English by Tomas Diaz. ~orders@tomasdiaz.com

Solution

First, we show that placing different numbers of coins in each dish (call them dishes 1 and 2) does not provide any useful information. Consider placing $a$ coins in dish 1 and $b$ coins in dish 2, and WLOG assume $a>b$ . Furthermore, assume that the fake coin is of weight $0.5$ and the authentic coins are of weight $1$ . Then the first dish will always be heavier than the second dish, regardless of the position of the fake coin, so no new information is guaranteed (since we are not given the fake coin's weight) and thus we only need to consider placing the same number of coins in each dish.

First, we consider odd $N$ , and we claim that no odd $N$ work by induction except for $N=1$ , which clearly works. For our base case of $N=3$ , notice that we only consider placing equal numbers of coins into each dish, so we place one coin in each dish. If we are unlucky, then both are authentic; we detect this and remove the coins, so we are unable to determine the relationship between the weights of the real coins and the fake coin. Next, assume that for some odd $N=k$ , we are unable to complete the objective with certainty for all positive odd integers $i$ such that $3\le i\le k$ . We show that $N=k+2$ is not guaranteed either. Notice that in order to learn about the coins, we must weigh them; assume we place $p$ coins in each dish such that $2p\ne k+1$ . It is possible that the scale is balanced; thus all $2p$ coins are authentic and must be removed. We are left with $k+2-2p\le k$ coins, which cannot complete the objective. Next, consider the case where $2p=k+1$ ; then if the scale is balanced, we are left with the one fake coin. However, we again cannot learn about the relationship between the weights of the real and fake coins, so the objective is failed. Thus, we have shown using strong induction that for all odd $N$ , the objective is not guaranteed.

Next, we consider even $N$ . Again, we claim that the objective is never guaranteed for all even $N$ . Our base case $N=2$ is clearly impossible since we do not know if the fake coin is heavier or lighter than the authentic coin. Thus assume for some $N=k$ that for all positive even $i\le k$ , the objective is not guaranteed. We show that it is also not guaranteed for $N=k+2$ . If we are to place $p$ coins in each dish for $p\in\left[1,\frac{k}{2}\right]$ , then if the scale is balanced, all the $2p$ coins are authentic, so they are removed, leaving us with $k+2-2p\le k$ coins, which cannot guarantee the objective. However, assume that $p=\frac{k}{2}+1$ ; then all of our coins are placed on the scale. Clearly one side will be heavier than the other, but we still do not know whether the fake coin is lighter or heavier than the authentic coin; notice that from this we still are not given any new information. Thus, we must swap some coins between dishes such that the total number of coins on each dish remains the same (since if we remove any coins and all coins on the scale are authentic, then we reach a lower case, which is not guaranteed). Assume we swap $2m$ of the coins, $m$ on each dish, and the scale remains the same. Then the $2m$ coins we just swapped must all be authentic (since swapping the fake coin would change the balance), so we remove them and reach a lower case, which by the inductive step fails the objective. Thus by strong induction, all even $N$ fail, leaving only $\boxed{N=1}$ as the working solution.

~ eevee9406

Page

Toolbox

Search

2014 OIM Problems/Problem 4

Problem

Solution

See also