### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,158)
- misc (2)
- project euler (2)
- puzzle (40)
- site news (44)
- tantalizer (42)
- teaser (3)

### Site Stats

- 177,972 hits

Advertisements

Programming Enigma Puzzles

23 January 2012

Posted by on **From New Scientist #2754, 3rd April**** 2010** [link]

I recently purchased a number of seemingly identical antique coins knowing that an unspecified one of them was counterfeit and significantly different in weight from the others.

By coincidence, I have another exactly similar and authentic coin already in my collection.

Using a sensitive two-pan balance, I calculate that to be certain of finding the offending coin and whether it is heavier or lighter than the others, I shall need three weighings.

Had the number of coins I purchased been any larger, I would have needed at least one more weighing to be sure of achieving the same outcome.

How many coins did I purchase?

[enigma1589]

Advertisements

%d bloggers like this:

This is a tough one to solve programmatically.

From n weighings there are 3^n outcomes, and with exactly one counterfeit coin to detect from m coins (which could be heavier or lighter) there are 2m possibilities. So the maximum number of coins that could satisfy the problem would be floor(3^n / 2), which for n=3 is 13.

And this paper elegantly shows that 13 is indeed an achievable solution. [ http://www.link.cs.cmu.edu/15859-s11/notes-2005/maacoins.pdf ]

Programatically, we construct a decision tree, by considering possible balance sets at each stage. For three balances this runs in 8.7s (or 4.0s using PyPy). Although I think it would be possible to reduce the runtime by exploiting the symmetry of the decision tree.

Note:The program is longer than necessary, as it includes code to output the decision tree.Solution:You purchased 13 coins.This is a much faster variant on the previous program (it runs in 64ms), although it doesn’t directly construct a decision tree (but you can deduce it from the computation). Instead of tracking the individual coins it deals with the number of different kinds of coins, keeping track of ‘G’ (good coins), ‘S’ (coins which may be suspect) and ‘H’, ‘L’ (coins which may be suspect, but if they are they are heavy or light respectively). It then reduces the search space by generating sets of different numbers of each kind of coin.

Note:You can modify the terminating condition in thebalance()function to allow a single suspect coin to terminate the function (without knowing if it’s heavier or lighter), and it turns out you could purchase 14 coins and still determine the fake (but you might not know if it’s heavier or lighter).Although the general case of the problem is having

aknown good coin, I’m not sure that it’s obvious that multiple good coins are not necessary in the intervening stages (although, as it turns out, they are not).Certainly there’s no point having good coins on both sides of the balance. If you remove the condition of having a single good coin, and instead ignore balances with good coins on both sides this algorithm still finds the solution in under a second (750ms).

This is a well-known puzzle, but nowhere have I seen the following formulation of the solution, that lends itself to a generalization to larger numbers.

Write down the integer 1 and three successive integers starting at 3: i.e. 1, 3, 4, 5. Convert them to 3-digit numbers in base 3: 001, 010, 011, 012. For each number, permute the digits cyclically: 112, 121, 122, 120; 220, 202, 200, 201. For each digit position, we now have four numbers with each of 0, 1, and 2. Write a different one of the twelve numbers on each coin. In this variant with a thirteenth suspect coin, write 222 on it and 111 on the coin known to be good.

Declare the left-hand scale pan as no. 1, the right-hand as no. 2 (it could be the other way about, but that seems a reasonable convention).

In the first weighing, put all those with 1 as the first digit on scale pan 1, all those with 2 as the first digit on scale pan 2, and leave on the table those with 0 as the first digit. Write down which pan goes down, or write 0 if they balance. In the subsequent two weighings, repeat the procedure with the second and then the third digit position. The three numbers we wrote down, read as a single 3-digit number, give the number of the coin that is heavier. If there is no coin with that number, then swap 1s and 2s to give the number of the coin that is lighter. For example, a number 210 means that coin 120 is the lighter one. A result of 000 would mean that all coins have the same weight (though in this case one coin is known to be counterfeit). If more than one coin is counterfeit, the method fails and one might do better to weigh each of the thirteen in turn against the good one.

The method can be extended to 39 coins (or 40 if there is an additional one known to be good) with four weighings by extending the series to include nine successive integers starting at 9, and converting them all to 4-digit numbers in base 3. That was the subject of Sunday Times Teaser no. 2500. Five weighings should be enough for 120 coins (27 more integers starting with 27), and so on.

The simplest case, of course, is three coins labelled 01, 12, 20, optionally with a fourth labelled 22 and a known-good one labelled 11, in two weighings.

There are many different expositions showing how operations in the ternary (base 3) number system can be used to provide a systematic approach to their solution for aany number of coins. There is a nice overview at Cut The Knot site.