Dyson’s Algorithm

Dyson’s algorithm actually solves a more general version of the coins problem:

You have coins, to appearance exactly identical; but possibly one is counterfeit (we’ll call it a “dud”). You do not know if a dud is present, nor whether it is heavier or lighter than the good coins. Can you determine in weighings on a balance scale: (1) whether there is a dud, (2) if so, which coin, and (3) its relative weight (lighter or heavier than the good coins)?

Dyson shows that the largest number of coins that can be resolved in weighings is . That’s 3 coins in 2 weighings, 12 coins in 3 weighings, 39 coins in 4 weighings, and so on. The algorithm I’ll show in this post solves the case where you have exactly coins. I’ll discuss the general case where in a subsequent article.

The basic idea of Dyson’s algorithm it 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

I’ll describe the procedure with the example (3 coins, 2 weighings), since that’s easy to work out by hand. Then I’ll point you to some code for larger cases.

1: Label the coins with the numbers 1 through , and convert them to signed trinary using digits. I’ve described the conversion procedure to signed trinary before, here. For , that looks like this:

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 (Note that , and ). In R, that looks something like this, assuming you’ve implemented the base-3 number as a vector:

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 rotates forward, then its negation rotates backward, and vice-versa. So replace any of the coin labels that rotate backwards with its negation:

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. means the left pan, means the right pan, and means the table. The weighing schedule is such that for the th weighing, a given coin is in the location described by its label’s th digit (counting from the left, so the ones digit is last). For our example, this gives the schedule:

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 (and ), before you even see a specific set of coins. It can also be used over and over, for any set of coins. This is what we mean when we call this algorithm “oblivious.”

4: Weigh the coins according to the schedule

We’ll record the outcome of each weighing, , as which pan was heavier (if any): means the left pan is heavier, means the right pan is heavier, means the scale is balanced. This means that if the th coin is a heavy dud, it will spell out its own label in signed trinary, as . A light dud will spell out the negation of the label. You can recover the decimal representation of the final outcome, as

Then the location of the dud is , and the dud is heavy if rotates forward, and it is light if rotates backward. If there is no dud, then .

Note that the sign of is NOT whether the dud is heavy or light; it’s whether the original trinary representation of rotated forward or backward.

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

• No dud
  • Scale: (balanced, balanced), so : no dud
• The dud is coin 1, and it is light
  • Scale: (balanced, left), so and rotates backward: coin 1, light.
• The dud is coin 2, and it is heavy
  • Scale: (right, left), so and rotates forward: coin 2, heavy.
• The dud is coin 3, and it is heavy
  • Scale: (left, balanced), so and rotates forward: coin 3, heavy.

Back to the 12 coins

So now we can do the problem that we actually care about. One could do it by hand, but code is easier. I have R code for the special case here.

Let’s show the forward representations of the coins.

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")

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

knitr::kable(Cset[[3]], caption = "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, !! But the notation is concise, and easy to write checks for.

# 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 coins in weighings problem, for the special case when . In the next post, I’ll describe the general case, when .

Nina Zumel is a data scientist based in San Francisco, with 20+ years of experience in machine learning, statistics, and analytics. She is the co-founder of the data science consulting firm Win-Vector LLC, and (with John Mount) the co-author of Practical Data Science with R, now in its second edition.

References