Source

I got this problem from Rustan Leino, who got it from Dave Detlefs, who read it in an MIT Alumni magazine. This puzzle is a bit more involved than most puzzles on this page, so you may want a paper and pen (and some tenacity) for this one. Once you get into it, though, it's a hard puzzle to put aside until you've solved it.

I solved it and wrote up my solution.

Problem

There are two kinds of coins, genuine and counterfeit. A genuine coin weighs $X$ grams and a counterfeit coin weighs $X+\delta$ grams, where $X$ is a positive integer and delta is a real number satisfying $0 < |\delta| < 5.$ You're presented with 13 piles of 4 coins each. All of the coins are genuine, except for one pile, in which all 4 coins are counterfeit. You're given a precise scale (say, a digital scale capable of displaying any real number). Using it, you have to determine three things: $X,$ $\delta,$ and which pile contains the counterfeit coins. But, you're only allowed to use the scale twice! How can you do this?

Solution
Reveal

Number the piles 1 through 13, and call the number of the pile containing counterfeit coins $c$. Let $w_1$ and $w_2$ be the results of weighings 1 and 2, respectively. Define $a_i,$ $b_i,$ and $r_i$ according to the following table: \[ \begin{array}{lccccccccccccc} \mbox{Pile #} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ a_i & 4 & 4 & 4 & 4 & 4 & 3 & 3 & 3 & 2 & 2 & 1 & 1 & 0 \\ b_i & 0 & 1 & 2 & 3 & 4 & 1 & 2 & 4 & 3 & 4 & 3 & 4 & 4 \\ r_i = a_i / b_i & & 4 & 2 & 4/3 & 1 & 3 & 3/2 & 3/4 & 2/3 & 1/2 & 1/3 & 1/4 & 0 \end{array} \] Define $[]$ as the rounding operator, i.e., for any $v,$ define $[v]$ to be the closest integer to $v,$ breaking ties in favor of the higher integer.

For weighing 1, use $a_i$ coins from each pile $i.$ Let $\hat{x} = [w_1/35].$ Now, depending on whether $|w_1 - 35\hat{x}| < 15,$ proceed in two different ways.

If $|w_1 - 35\hat{x}| < 15,$ determine that $X = \hat{x}.$ Then, for weighing 2, use $b_i$ coins from each pile $i.$ If $w_2 = 35X,$ then determine that $c = 1$ and that $\delta = (w_1 - w_2)/4.$ Otherwise, determine that $c$ is the unique pile number satisfying $r_c = (w_1 - 35X)/(w_2 - 35X),$ and determine that $\delta = (w_2 - 35X)/b_c.$

If $|w_1 - 35\hat{x}| \geq 15,$ then, for weighing 2, use $b_i$ coins from each pile $i$ where $1 \leq i \leq 5$ and use 4 coins from each pile 6–13. Then, determine that $X = [w_2/42]$ and that $\delta = (w_1 - 35X)/4.$ Then, determine that $c$ is the unique number between 1 and 5 inclusive that satisfies $b_c = (w_2 - 42X)/\delta.$

Because of the way we choose coins for weighing 1, and because $\sum_{i=1}^{13} a_i = 35,$ we have $w_1 = 35X + a_c\delta.$ There are two cases to consider, as follows.

Observe that $|a_c\delta| < 20$ since $0 \leq a_c \leq 4$ and $|\delta| < 5.$ So, since $w_1 - 35X = a_c\delta,$ we have $|w_1 - 35X| < 20.$ If $X$ were different from $\hat{x},$ then $w_1$ would be less than 15 away from one integer multiple of 35 (i.e, $35\hat{x}$) and less than 20 away from a different integer multiple of 35 (i.e., $35X$), which is impossible since integer multiples of 35 are spaced at least $15+20=35$ apart from each other. So, we know $X = \hat{x}.$

Because of the way we choose coins for weighing 2 in case 1, and because $\sum_{i=1}^{13} b_i = 35,$ we have $w_2 = 35X + b_c\delta.$

If $w_2 = 35X,$ we know $b_c\delta = 0,$ and since $\delta \neq 0$ we know $b_c = 0.$ There's only one $i$ for which $b_i = 0,$ so we're right to determine that $c = 1.$ In this case, we know $a_c = 4,$ so we can compute $\delta = (w_1 - 35X)/a_c = (w_1 - 35X)/4.$

If $w_2 \neq 35X,$ then we know $b_c\delta \neq 0,$ so $c$ can't be 1 and thus $r_c$ is well-defined. We also know that $(w_1 - 35X)/(w_2 - 35X)$ is well-defined and equal to $(a_c\delta)/(b_c\delta) = a_c/b_c = r_c.$ Since the 12 defined values of $r_i$ are all distinct, we can determine the unique $c$ that satisfies $r_c = (w_1 - 35X)/(w_2 - 35X).$ Once we have this, we can compute $\delta = (w_2 - 35X)/b_c$ since $b_c \neq 0$ whenever $c \neq 1.$

The closest multiple of 35 to $w_1$ is at least 15 away, so every multiple of 35 is at least 15 away from $w_1.$ In particular, $|w_i - 35X| \geq 15.$ This means that $|a_c\delta| \geq 15.$ Since $\delta < 5,$ we can't have $a_c \leq 3$ and thus must have $a_c = 4.$ The only piles $i$ for which $a_i = 4$ are piles 1–5, so we know $c$ is one of piles 1–5.

Because of the way we choose coins for weighing 2 in case 2, and because $\sum_{i=1}^{5} b_i + \sum_{i=6}^{13} 4 = 42,$ we have $w_2 = 42X + b_c\delta.$

Observe that $|b_c\delta| < 20$ since $0 \leq b_c \leq 4$ and $|\delta| < 5.$ So, since $w_2 - 42X = b_c\delta,$ we have $|w_2 - 42X| < 20.$ Since $w_2$ will be within 20 of this integer multiple of 42, it'll be at least 22 away from any other integer multiple of 42. So, the closest integer multiple of 42 will be $42X$ and we're correct to determine that $X = [w_2/42].$

Since $w_1 = 35X + a_c\delta$ and $a_c = 4,$ we can compute $\delta = (w_1 - 35X)/4.$ Since $w_2 = 42X + b_c\delta,$ we can compute $b_c = (w_2 - 42X)/\delta.$ We've narrowed down $c$ to 1–5, and those piles $i$ have different values of $b_i.$ So, we can uniquely determine $c.$