Explanation of Freeman Dyson's solution of the counterfeit coin problem

393 Views Asked by At

Freeman Dyson's paper, The problem of the pennies Math. Gaz., 30 (1946) 231-234, offers a solution to a counterfeit coin detection problem. I quote his solution of one case as follows. I would appreciate the explanation of the purpose the demarcation of clockwise and anticlockwise labels serves.

Identify a defective penny among a collection of $M$ pennies of identical appearance, knowing that the defective penny is of a different weight from the others, by the use of a pair of weigh In n operations of weighing, it is required to ident and to decide whether it is lighter or heavier than the others.

Solution of the problem for $M=\frac12(3^n-3)$.

Let the pennies be numbered from $1$ to $M$. Each penny is given a "label" consisting of its number expressed as a ternary decimal, with a sufficient number of zeroes placed at the beginning to make each label exactly $n$. Each penny is then given a second label obtained by subtracting its first label from the ternary decimal $3^n - 1= 2M + 2$. Each label of a given penny can be derived from the other by changing digits $0$ into $2$ and digits $2$ into $0$ while leaving digits $1$ unaltered. Every $n$-digit ternary decimal occurs just once as a label, except for the three consisting of one digit repeated $n$ times.

A label is called "clockwise " if the first change of digit in it after the beginning is a change from $0$ to $1$ or from $1$ to $2$ or from $2$ to $0$; it is called "anticlockwise" if the first change of digit is from $1$ to $0$ or from $2$ to $1$ or from $0$ to $2$. Of the two labels of a given penny, one is clockwise and the other anticlockwise. We denote by $C(i, d)$ the class of pennies whose clockwise labels have $d$ for their $i$-th digit. A cyclic permutation of digits changing $0$ to $1$, $1$ to $2$, $2$ to $0$ in the labels of all pennies would simply transfer all pennies from $C(i, 0)$ to $C(i, 1)$, from $C (i, 1)$ to $C (i, 2)$, and from $C(i,2)$ to $C(i, 0)$; this shows that the classes $C(i, 0)$, $C(i, 1)$ and $C(i, 2)$ all contain the same number $\frac13M$ of pennies.

The $n$ weighing operations are specified by the rule that at the $i$-th weighing the pennies of $C(i, 0)$ are weighed in the left-hand pan of the scales against the pennies of $C(i, 2)$ in the right-hand pan, the pennies of $C(i, 1)$ being laid aside. The result of the $i$-th weighing is symbolized by a number $a_i$ which we take to be $0$ if the left-hand pan sinks, $2$ if the right-hand pan sinks, and $1$ if the scales remain level. We consider the ternary decimal $$A = 3^{n-1}a_1 + 3^{n-2}a_2 + \dots + a_n.$$ It follows from the result of the $i$-th weighing that the defective penny either is heavy and has $a_i$ as the $i$-th digit of its clockwise label, or is light and has $a_i$ as the $i$-th digit of its anticlockwise label. Therefore after $n$ weighings the defective penny is determined uniquely as the penny one of whose labels is $A$, and it is heavier or lighter than the others according as this label is clockwise or anticlockwise. It is interesting to notice that the latter question will usually be decided by the first $2$ or $3$ weighing.

1

There are 1 best solutions below

1
On

Using the clockwise label of each coin to define $C(i,d)$ ensures that the sets $C(i,0)$, $C(i,1)$ and $C(i,2)$ all have the same size, for each $i$. For example, suppose $n=2$, and you just used the ternary representations to define $C(i,d)$. The labels are $01,02,10$. Note $C(1,0)=2,C(1,1)=1,C(1,2)=0$. If we instead use the clockwise labels, we instead get $01,20,12$, which is balanced.

The reason that the clockwise labels achieve balance is because the transformation which changes each digit of a label according to the rule $0\to 1\to 2\to 0$ preserves clockwise-ness. You start with a clockwise label, apply the transformation, and are left with a clockwise label. For a different choice of labels, what could go wrong is you start with a valid label, apply the transformation, but then you end up with an invalid label, so you have to take the complement. This would mean that the transformation would not necessarily take $C(i,1)$ to $C(i,2)$, so you do not have the bijection which proves they are the same size.