After having worked on The Twelve Coins Puzzle by hand, I got curious about implementing Dyson’s “elegant” oblivious solution, which I mentioned in that previous post. While a quick skim gave me the general gist of the approach—and it is elegant—a deeper read for details made me wonder how mathematicians ever got anything done at all, in the old days. The note is telegraphic, to say the least.

But I finally figured it out, and coded it up in R. This may actually be the preferable language, since Dyson’s discussion indexes from 1, as R does. The basic idea is to label each coin by its trinary representation, and then to schedule the weighings in such a way that, with the appropriate representation of the measurement outcomes, the weighings “spell out” the label of the dud coin, if it exists. There is a known label for the case when there is no dud.

Dyson’s original algorithm used standard base-3 representations, where the digits are (0, 1, 2). I decided to implement my version using signed trinary, where the digits are (-1, 0, 1). This is the representation that I used for the Four Weights Puzzle, and I just find it more natural for balance scale problems. As a bonus, it also makes Dyson’s algorithm easier to describe.

The algorithm below works specifically for the case where the number of coins is exactly

and

## The Algorithm #

I’ll describe the procedure with the example

**1: Label the coins** with the numbers 1 through

```
1 = [0 1]
2 = [1 -1]
3 = [1 0]
```

**2: Set the trinary representations to rotate “forward.”**

We say that a number in base-3 rotates “forward” (Dyson called it
“clockwise”) if the first change of digits increases by 1, modulo 3. So
the forward sequence is

```
is_forward = function (ptrinary) {
delta = diff(ptrinary)
# get only the nonzero diffs
delta = delta[!(delta==0)]
if(length(delta)==0)
stop("constant vector")
# check if we are rotating forward, and return
delta[1] %% 3 == 1
}
```

If a signed trinary number

```
1 = [0 1] : rotates forward
2 = [1 -1]: rotates forward
3 = [1 0]: rotates backward, so replace with [-1 0] (-3)
```

Representing all the coins with forward rotating numbers removes the ambiguity that arises from not knowing whether the dud coin is heavier or lighter than the good coins: if the balance scale tilts the left pan down, that could be because a heavy dud is in the left pan, or because a lighter dud is in the right pan. As we will see, setting all the coin labels to rotate forward means that a heavy dud will produce a pattern of behaviors that “spell out” the location of the dud, while a light dud will spell out the negation of the label.

**3: Plan the weighing schedule.**

Now let’s label the possible positions on (or off) the scale.

```
1 = [0 1]: table, then right pan
2 = [1 -1]: right pan, then left pan
3 = [-1 0]: left pan, then table
```

Using the scale notation we’ve been using for balance scale problems, that looks like this:

```
First weighing:
[coin 3 | coin 2]
------------------
coin 1
Second weighing:
[coin 2 | coin 1]
-----------------
coin 3
```

Note that the weighing schedule can be calculated in advance if you know

**4: Weigh the coins according to the schedule**

We’ll record the outcome of each weighing,

Then the location of the dud is

** Note that the sign of **; it’s
whether the trinary representation of

And that’s it! Let’s walk through a few examples.

- No dud
- Scale: (balanced, balanced), so
: no dud

- Scale: (balanced, balanced), so
- The dud is coin 1, and it is light
- Scale: (balanced, left), so
and rotates backward: coin 1, light.

- Scale: (balanced, left), so
- The dud is coin 2, and it is heavy
- Scale: (right, left), so
and rotates forward: coin 2, heavy.

- Scale: (right, left), so
- The dud is coin 3, and it is heavy
- Scale: (left, balanced), so
and rotates forward: coin 3, heavy.

- Scale: (left, balanced), so

## Back to the 12 coins #

So now we can do the problem that we actually care about. I have R code to implement it, here.

Let’s show the forward representations of the coins.

```
# https://github.com/NinaZumel/DysonsAlgorithm/blob/main/dyson_signed_specialcase.R
source("dyson_signed_specialcase.R")
nrounds = 3
ncoins = (3^nrounds - 3)/2 # 12
# Show the forward representations of the coins
get_forward_representation(nrounds)
```

```
## [,1] [,2] [,3]
## [1,] 0 0 1
## [2,] 0 1 -1
## [3,] 0 1 0
## [4,] 0 1 1
## [5,] 1 -1 -1
## [6,] 1 -1 0
## [7,] 1 -1 1
## [8,] -1 0 1
## [9,] -1 0 0
## [10,] -1 0 -1
## [11,] 1 1 -1
## [12,] -1 -1 0
```

In my implementation, I precompile the weighing schedule ahead of time,
so I can just weigh coins over and over again. The `precompile()`

function
calls `get_forward_representation()`

internally, and returns a list. Each
element of the list is the weighing schedule for that weighing, as a
data frame, with columns `(left, table, right)`

. Each column of the data
frame holds the coins that go into that position for that weighing.

```
Cset = precompile(ncoins, nrounds)
# show the schedule
knitr::kable(Cset[[1]], caption = "Weighing 1")
```

left | table | right |
---|---|---|

8 | 1 | 5 |

9 | 2 | 6 |

10 | 3 | 7 |

12 | 4 | 11 |

Weighing 1

`knitr::kable(Cset[[2]], caption = "Weighing 2")`

left | table | right |
---|---|---|

5 | 1 | 2 |

6 | 8 | 3 |

7 | 9 | 4 |

12 | 10 | 11 |

Weighing 2

`knitr::kable(Cset[[3]], caption = "Weighing 3")`

left | table | right |
---|---|---|

2 | 3 | 1 |

5 | 6 | 4 |

10 | 9 | 7 |

11 | 12 | 8 |

Weighing 3

Now we can find duds. It doesn’t matter how much the coins weigh, as
long as all good coins weigh the same amount. My function `find_dud()`

returns a value `D`

such that `abs(D)`

gives the index of the dud, and
`sign(D)`

gives the dud’s relative weight; negative means the dud is
light, and positive means the dud is heavy. In other words,

```
# a good coin weighs 1 unit
coins = numeric(ncoins) + 1
epsilon = 0.5
# check the no dud case
find_dud(coins, Cset)
```

## [1] "No dud."

## [1] 0

```
# check a specific case
idud = 7
relative_wt = -1 # make it lighter
coins[idud] = 1 + epsilon*relative_wt
find_dud(coins, Cset)
```

## [1] -7

```
# verify this works in all possible cases
for(idud in 1:ncoins) {
for(relative_wt in c(-1, 1)) {
actual = idud*relative_wt # location and direction
coins = numeric(ncoins) + 1
coins[idud] = 1 + epsilon*relative_wt
A = find_dud(coins, Cset)
stopifnot(actual==A)
}
}
```

And that’s the solution of the

## Reference #

Dyson, Freeman J. “Note 1931–The problem of the pennies,” *The
Mathematical Gazette* Vol. 30, No 291) (October 1946). JSTOR
link