Dividing three real coins

Question

There are $n$ coins, three real (with equal positive weight) and the rest fake (with zero weight). You have a scale that, between two sets of coins, tells you which set is heavier (or if they are equal). What is the minimum number of weighings that you must use in order to divide the coins into three sets so that each set contains one real coin?

If we have to divide into two sets, then it is possible for any even number of coins using $\log n$ weighings. However, the method does not appear to extend to division into three sets.

Answer 1

Line the coins up in a row, split the row in the middle and weigh both sides of the split. Because there are an odd number of coins, the balance will always tip one way or the other. Use this fact to do a binary search to find the middle most real coin by repeatedly moving the splitting point. This takes $\log n$ weighings.

Now you have three groups: the coins to the left of the middle real coin, the middle coin itself and the coins to the right of middle real coin. Each group contains exactly 1 real coin.

Answer 2

Weigh half the coins against the other half. The light side has either zero or one real coins. Weigh the light side against nothing. If it balances, we have reduced the problem to one with half as many coins. If it doesn't balance, there is one real coin in that half and we can split the other half in $\log_2 n-2$ weighings per your other question. The worst case is that we keep putting the real coins in the same half, which leads to a solution in about $2 \log_2 n$ weighings. I don't know if this is optimal, but it gives a target to shoot at. The fact that you care about the result weighing against nothing suggests it is not optimal.

Answer 3

A simple solution is to reduce the problem to the two-coin problem. Start by dividing the coins to two piles of equal or near-equal size, and weigh the piles against each other. Since there are three real coins, an odd number, one side must be heavier than the other. The lighter side must clearly have either no real coins or just one real coin.

Split the lighter side into two halves, and weigh the halves against each other. If one side is heavier than the other, it must contain one real coin - now you have successfully extracted one pile with exactly one real coin, and can use the two-coin algorithm you already know to split the remaining coins into two piles, with one real coin in each.

Otherwise, if the scales are balanced, you can discard all the coins on them because none of them are real and start from the top by dividing the remaining coins into two equal or near-equal piles and repeating the process until you isolate a single real coin.

Since the pile is halved each time, the amount of weighings needed per fake coin grows logarithmically. The original algorithm needs a logarithmic amount of weighings as well, so the added step to isolate a single coin doesn't change the asymptotic number of weighings needed.