Two fake coins

Puzzle found here.

Among a pile of n gold coins, 2 of them are fake. Fake coins weigh the same, gold coins weight the same, but a fake coin weigh less than a gold coin. Given a balance scale with 2 weighting, the goal is to deduce which are the fake coins. 1. What is the maximum n and be able to achieve the goal? Support your answer with an algorithm. 2. What about with 3 weighting. 3. What about with 4 weighting.

Single fake coin

If there is only a single fake coin, the solution is very simple:

1. Divide pile of coins into 3 equally sized piles (or as close as possible) certainly make sure the first two piles are exactly equal, the third pile may be one more or less.
2. Weight one pile against the second
3. If one of the piles is lighter, continue with lighter pile
4. If the scale is balanced, continue with the third pile.
5. Continue until only one coin is left.

There are solutions to a stricter form of the puzzle, like for example, if you have to write down all your weightings on the beforehand, and I will explain this in a future blog post.

Upper bound

Let us call a specific pair of fake coins a configuration. The different weighting have to be able to distinguish all configurations. A weighting itself can distinguish 3 configurations (if for one configuration left is heavier, for another right is heavier and for the last one the scale is balanced.)

This means that a maximum of w weightings can distinguish 3^w different states.

Contrary to this, the number of possible configurations is ${2 \choose n} = \frac{n(n-1)}{2}$ for n weightings [source].

As all different configurations need to be distinguished, this means:

$3^w \geq \frac{n(n-1)}{2}$

$w \geq \log_3{ \frac{n(n-1)}{2}}$

as as the number of weightings is an integer

$w \geq \left\lceil \log_3{ \frac{n(n-1)}{2}} \right\rceil$

Is a lower bound for the number of weightings needed to distinguish n coins.

Anologous is

$\begin{aligned} 3^w &\geq \frac{n(n-1)}{2}\\ 2\times 3^w &\geq n(n-1)\\ 2\times 3^w &\geq n^2 - n\\ 0 &\geq n^2 - n - 2\times 3^w \\ n &\leq \frac{1 + \sqrt{1+8\times 3^w}}{2}\\ n &\leq \left\lfloor\frac{1 + \sqrt{1+8\times 3^w}}{2}\right\rfloor \end{aligned}$

An upper bound for the number of coins that can be distinguished.

To show that this upper bound can be reached, we just need a strategy that can reach the upper bound.

Sieving

Let call a subset of configurations that is still possible after a set of weighting a sieve. And let us call a sieve solvable in w weightings if there exists a strategy that can find the correct configuration of 2 fake coins in w or less weightings. Let us write out this definitions more mathematical, so we can more easily work with it.

The first thing we do is number each coin, with an index from 0 to n − 1

Definition 1 A configuration is a unordered pair of coins (integers). The set of all configurations C is the set of all unordered distinct pairs of integers in the range [0, n[

Definition 2 A weighting is an ordered pair of disjuct subsets of the integer range, of the same size. (the set of coins we put in the left scale and the set of coins we put on the right scale.)

Definition 3 Each weighting splits a sieve in three smaller sieves, depending on how the scale would react to the configuration. (so the configurations where the left side would be heavier, the configurations where the right side would be heavier, and the configurations would leave the scale balanced )

Theorem 1 If a sieve is solvable in w weightings, there exists a weighting that splits are sieve into 3 sieves that are solvable in w − 1 weightings.

Proof: Trivially proven by induction

Theorem 2 A sieve solvable in w weightings has at most 3^w elements.

Proof: Trivial

Strategy

Using the previous chapter, we can devise an algorithm to search for a strategy. For each sieve, find a weighting that splits it into 3 sieves with at most 3^w − 1 elements, but to make sure that we have margin for future weightings, we will try to split the sieve as evenly as possible. A good metric for how evenly something is split is the product of the sizes of the subsieves, but using this as an heuristic will put (0,0,2) on the same footing as (0,1,1), we will first add one to it, to prevent multiplication with zero.

To device the full strategy, we will use a Monte-Carlo simulation. This is the full algorithm:

1. Select a limit l
2. Start by creating a sieve containing all possible configurations.
3. For each sieve:
   1. Generate l weightings
   2. Select all valid weightings (where all subservient are smaller than 3^w − 1 with w the number of weightings left).
   3. Choose the valid weighting with the best heuristic. (As valid weightings always have better heuristics than invalid ones, these step can be switched with the previous one.)
   4. If there are no valid weightings, goto step 1 and increase the limit.
   5. Add the three new sieves to the set of step 3.
   6. If any of the sieves only has one element, this configuration is the correct configuration, do not add this sieve.

This algorithm does not guarantee a solution will be found, but it will usually find it.

The algorithms are displayed in interactive graphs. Each weighting is displayed as a box, with two sets of numbers in it, separated by <|>. The left set of numbers are the coins that have to be placed on the left set scale, the right numbers are the coins that have to be placed on the right scale. Each box can be clicked to expand or retract it. Expanding the box shows 3 path. The left one needs to be followed if the left scale is lighter, the right one if the right scale is lighter, and the middle one if the scale is balanced. If there are just 2 numbers with an ampersand between them, it means that those are the two fake coins.

Using this algorithm, I found solution for the following settings:

number of weightings	upper limit	number of coins for algorithm	strategy link.
2	4	4	[link]
3	7	7	[link]
4	13	13	[link]
5	22	22	[link]
6	38	38	[link]
7	66	66	[link]
8	115	115	[link]

Further reading:

this paper contains solutions up to w = 10: http://www.chgk.info/~knop/math/ff.pdf