How Do You Find the Fake Coin in Three Weighings?

Start small: three coins

Three coins, and one is heavier. You may weigh once.

Nine coins, two weighings

Now nine coins, one heavier, and two weighings. Keep Show what’s still possible on, and watch the readout This weighing would leave as you load the pans: it counts how many coins could still be the fake after each answer, before you weigh.

Back to twelve

Go back to the twelve coins at the top of the page and press Show what’s still possible. Now the fake could be any of 12 coins, and either heavier or lighter: 24 cases. Load four coins on each pan and look at the readout: 8, 8 and 8. Then try three against three, or five against five.

Three answers, counted

Each weighing gives one of three answers: left (the left pan goes down), right, or level. Two weighings give 3 × 3 = 9 different pairs of answers: left-left, left-right, left-level, right-left and so on. Three weighings give 3 × 3 × 3 = 27.

Now count the cases, every different thing that might be true. A method that finds the fake must give a different set of answers for every case. If two cases gave exactly the same answers, nothing could tell them apart.

Twelve coins make 24 cases, and 24 is no more than 27: counting doesn’t rule them out. (The count only says what is not possible; the last column is checked properly below.) Fourteen coins make 28 cases, more than the 27 answers three weighings can give. However the weighings are chosen, two of the cases must give the same three answers. So fourteen coins can never be done, by anyone, in three weighings. You don’t even have to try.

Like binary search, but in three

You met this in Grade 8’s binary search: each look at the middle of a sorted list throws away half of it. A question with two answers can at best halve what is left. A balance asks a question with three answers, so a good weighing leaves only a third: 27 → 9 → 3 → 1.

That is the rule you found by playing: put a third of what is possible on each pan and leave a third off. Nine coins: 3, 3 and 3 off. Twelve coins, 24 cases: 4 against 4 leaves 8, 8 or 8.

A coin’s number in threes

The nine-coin method has a pattern. Number the groups 0 (coins 1, 2, 3 on the left), 1 (coins 4, 5, 6 on the right) and 2 (coins 7, 8, 9, left off). The first weighing gives the group, and the second gives the coin inside it, in the same order: left, right, level.

Write left as 0, right as 1 and level as 2. Then the two answers are the coin’s number, less one, written in base three: coin 8 is level then right, 2 and 1, and 2 × 3 + 1 = 7. In the mind-reading card trick each yes-or-no answer was one binary digit; here each weighing is one digit in threes.

With blocks: the nine-coin detective

This program plays the detective for nine coins, one heavier. It tells you what to weigh, asks which pan went down, and names the fake. The first answer sets group to the first coin of a group of three (1, 4 or 7); the second answer picks a coin in it.

In Python (from Grade 8): a balance

To check a method against every fake, a program needs a balance of its own. In weigh, every real coin weighs 10 grams and the fake 11 (heavier) or 9 (lighter). It gives back which pan goes down.

def weigh(left, right, fake, kind):    if kind == 'heavy':        fake_weight = 11    else:        fake_weight = 9    left_total = 0    for coin in left:        if coin == fake:            left_total = left_total + fake_weight        else:            left_total = left_total + 10    right_total = 0    for coin in right:        if coin == fake:            right_total = right_total + fake_weight        else:            right_total = right_total + 10    if left_total > right_total:        return 'left'    elif right_total > left_total:        return 'right'    else:        return 'level' print(weigh([1, 2, 3], [4, 5, 6], 5, 'heavy'))print(weigh([1, 2, 3], [4, 5, 6], 8, 'heavy'))print(weigh([1, 2], [3], 9, 'light'))

rightlevelleft

The last line shows why the pans need the same number of coins: two coins against one, and the left pan goes down whatever the fake is. That weighing tells you nothing.

Check a method against every fake

Here is the nine-coin detective again, as a function that is given the fake and uses only weigh to find it. The loop at the end tries it with every coin as the fake.

def weigh(left, right, fake, kind):    if kind == 'heavy':        fake_weight = 11    else:        fake_weight = 9    left_total = 0    for coin in left:        if coin == fake:            left_total = left_total + fake_weight        else:            left_total = left_total + 10    right_total = 0    for coin in right:        if coin == fake:            right_total = right_total + fake_weight        else:            right_total = right_total + 10    if left_total > right_total:        return 'left'    elif right_total > left_total:        return 'right'    else:        return 'level' def detective(fake):    first = weigh([1, 2, 3], [4, 5, 6], fake, 'heavy')    if first == 'left':        group = [1, 2, 3]    elif first == 'right':        group = [4, 5, 6]    else:        group = [7, 8, 9]    second = weigh([group[0]], [group[1]], fake, 'heavy')    if second == 'left':        return group[0]    elif second == 'right':        return group[1]    else:        return group[2] coins = 9found = 0for fake in range(1, coins + 1):    if detective(fake) == fake:        found = found + 1print('Found', found, 'of', coins, 'fakes')

Found 9 of 9 fakes

Now change coins = 9 to coins = 10 and run it again. Which fake does the detective miss? Could any method with two weighings find all ten?

A plan for twelve coins

With twelve coins, the next weighing usually depends on the last answer, and the instructions branch like a tree. But there is a neater way: decide all three weighings before you start. A plan is three weighings, each a list for the left pan and a list for the right. Weigh all three, look at the three answers, and look them up.

This program checks a plan. For each of the 24 cases (each coin, heavier and lighter) it works out the three answers the balance would give. If two cases give the same answers, that is a clash: the plan can’t tell them apart.

def weigh(left, right, fake, kind):    if kind == 'heavy':        fake_weight = 11    else:        fake_weight = 9    left_total = 0    for coin in left:        if coin == fake:            left_total = left_total + fake_weight        else:            left_total = left_total + 10    right_total = 0    for coin in right:        if coin == fake:            right_total = right_total + fake_weight        else:            right_total = right_total + 10    if left_total > right_total:        return 'left'    elif right_total > left_total:        return 'right'    else:        return 'level' def answers(plan, fake, kind):    said = []    for weighing in plan:        said.append(weigh(weighing[0], weighing[1], fake, kind))    return said def check_plan(plan, coins):    seen = []    cases = []    clashes = 0    for fake in range(1, coins + 1):        for kind in ['heavy', 'light']:            a = answers(plan, fake, kind)            if a in seen:                other = cases[seen.index(a)]                print('Clash:', fake, kind, 'and', other, 'both give', a)                clashes = clashes + 1            seen.append(a)            cases.append(str(fake) + ' ' + kind)    print(len(cases), 'cases,', clashes, 'clashes') easy_plan = [    [[1, 2, 3, 4], [5, 6, 7, 8]],    [[5, 6, 7, 8], [9, 10, 11, 12]],    [[1, 5, 9], [2, 6, 10]],]check_plan(easy_plan, 12)

Clash: 4 heavy and 3 heavy both give ['left', 'level', 'level']Clash: 4 light and 3 light both give ['right', 'level', 'level']Clash: 8 heavy and 7 heavy both give ['right', 'left', 'level']Clash: 8 light and 7 light both give ['left', 'right', 'level']Clash: 12 heavy and 11 heavy both give ['level', 'right', 'level']Clash: 12 light and 11 light both give ['level', 'left', 'level']24 cases, 6 clashes

Coins 3 and 4 go everywhere together, so nothing can tell them apart. Every coin needs a pattern of its own: where it goes in each of the three weighings.

Here is a plan that works. It is the one in Wikipedia’s article on the puzzle, with the coins numbered 1 to 12 instead of lettered.

def weigh(left, right, fake, kind):    if kind == 'heavy':        fake_weight = 11    else:        fake_weight = 9    left_total = 0    for coin in left:        if coin == fake:            left_total = left_total + fake_weight        else:            left_total = left_total + 10    right_total = 0    for coin in right:        if coin == fake:            right_total = right_total + fake_weight        else:            right_total = right_total + 10    if left_total > right_total:        return 'left'    elif right_total > left_total:        return 'right'    else:        return 'level' def answers(plan, fake, kind):    said = []    for weighing in plan:        said.append(weigh(weighing[0], weighing[1], fake, kind))    return said def check_plan(plan, coins):    seen = []    cases = []    clashes = 0    for fake in range(1, coins + 1):        for kind in ['heavy', 'light']:            a = answers(plan, fake, kind)            if a in seen:                other = cases[seen.index(a)]                print('Clash:', fake, kind, 'and', other, 'both give', a)                clashes = clashes + 1            seen.append(a)            cases.append(str(fake) + ' ' + kind)    print(len(cases), 'cases,', clashes, 'clashes') plan = [    [[1, 4, 7, 9], [2, 3, 6, 10]],    [[2, 5, 7, 8], [1, 3, 4, 11]],    [[3, 6, 8, 9], [1, 2, 5, 12]],]check_plan(plan, 12)print('Coin 4 lighter gives', answers(plan, 4, 'light'))print('Coin 4 heavier gives', answers(plan, 4, 'heavy'))

24 cases, 0 clashesCoin 4 lighter gives ['right', 'left', 'level']Coin 4 heavier gives ['left', 'right', 'level']

No clashes: all 24 cases give different answers, so the three answers always name the fake and say whether it is heavier or lighter. Coin 4 is on the left, then the right, then off; if it is heavier, the balance says exactly that, and if it is lighter, everything is the other way round.

Play the plan on the widget at the top of the page: weigh 1, 4, 7, 9 against 2, 3, 6, 10, then the second and third weighings, whatever the first said. Then find which case gives your three answers (★★ below asks a program to do that).

What about thirteen?

Thirteen coins make 26 cases, and 26 is still no more than 27. So is there a plan for thirteen? There are too many plans to try by hand, but a computer can try them all, if we think first.

A coin’s pattern is where it goes in the three weighings: L (left pan), R (right pan) or - (off), for example L-R. There are 3 × 3 × 3 = 27 patterns. Two can’t be used:

• ---: a coin that is never weighed. If it were the fake, every weighing would be level, heavier or lighter alike.
• A coin’s mirror (R-L for L-R): if it is heavier it gives the same answers as the first coin lighter.

So the 26 other patterns make 13 mirror pairs, and a plan for 13 coins must use one pattern from every pair. This program lists the pairs, then tries all 2¹³ = 8,192 ways of choosing one from each pair, and counts those where every weighing has the same number of coins on each pan. (Choosing a pattern or its mirror is a yes or no, so the program reads the choices from the binary digits of a number, as the mind-reading cards did.)

def mirror(pattern):    m = ''    for ch in pattern:        if ch == 'L':            m = m + 'R'        elif ch == 'R':            m = m + 'L'        else:            m = m + '-'    return m pairs = []for a in 'LR-':    for b in 'LR-':        for c in 'LR-':            p = a + b + c            if p != '---' and mirror(p) not in pairs:                pairs.append(p)print(len(pairs), 'pairs:', pairs) def balanced(patterns):    for w in range(3):        on_left = 0        on_right = 0        for p in patterns:            if p[w] == 'L':                on_left = on_left + 1            elif p[w] == 'R':                on_right = on_right + 1        if on_left != on_right:            return False    return True def count_plans(patterns):    n = len(patterns)    found = 0    for choice in range(2 ** n):        chosen = []        for i in range(n):            if (choice // 2 ** i) % 2 == 0:                chosen.append(patterns[i])            else:                chosen.append(mirror(patterns[i]))        if balanced(chosen):            found = found + 1    return found print('Plans for 13 coins:', count_plans(pairs)) twelve_coin_plans = 0for left_out in pairs:    twelve = []    for p in pairs:        if p != left_out:            twelve.append(p)    twelve_coin_plans = twelve_coin_plans + count_plans(twelve)print('Plans for 12 coins:', twelve_coin_plans)

13 pairs: ['LLL', 'LLR', 'LL-', 'LRL', 'LRR', 'LR-', 'L-L', 'L-R', 'L--', '-LL', '-LR', '-L-', '--L']Plans for 13 coins: 0Plans for 12 coins: 304

((choice // 2 ** i) % 2 is the binary digit worth 2ⁱ in choice, as in Grade 7. For twelve coins the program leaves out one pair at a time and tries the rest.)

• Nine coins, one heavier: all 9 found in two weighings. Nine cases, nine pairs of answers, one each.
• Twelve coins: a plan with no clashes. 24 cases fit into 27 answers, and your program found 304 different ways to choose twelve patterns that balance. (Each of them can still be given to the coins in any order.)
• Thirteen coins: no plan at all. 26 cases would fit into 27 answers, yet not one of the 8,192 choices balances. Here is why: in each weighing, 9 of the 13 pairs put a coin on the balance (count the L and R in the first place of each pattern). Nine coins can’t be split equally between two pans.
• Fourteen coins: impossible, without a program: 28 cases and only 27 answers.

What if the goldsmith chooses each weighing after seeing the last answer, as the nine-coin detective does? Thirteen still fails. Her first weighing puts some coins on each pan. With 4 against 4, if the pans balance, 5 coins are left: 10 cases, and the last two weighings give only 9 answers. With 5 against 5, if the left pan goes down, 10 cases are left again. Fewer or more coins only make one of those piles bigger. (★★★ below asks a program to do this counting for any number of coins.)

So information can be counted. Each weighing can at most triple the number of cases you can tell apart, the way each yes-or-no question can at most double it. Computer scientists often count like this before writing a program: if the cases outnumber the answers, no program can succeed. And when the count only just fits, as 24 into 27 does, every weighing must split the cases as evenly as it can.

A spare real coin. Suppose the goldsmith also has a thirteenth coin she knows is real. Then thirteen suspect coins can be done in three weighings: the real coin evens out the pans. Change check_plan to take 13 coins and try to find such a plan. (Hint: the 13 patterns of pairs are all needed, and the real coin goes wherever a weighing is one short.)

Not asking which way. If the goldsmith only needs to know which coin is fake, not whether it is heavier or lighter, thirteen coins can be done too. Can you see which case she could leave unsorted?

Weights for any load. With weights of 1, 3, 9 and 27 grams, and weights allowed on both pans, every whole number of grams from 1 to 40 can be weighed. (Put 9 on the pan with the load and 27 and 1 on the other: the load is 27 + 1 − 9 = 19 grams.) Write a program that finds how to weigh each number from 1 to 40. The puzzle is named after the French writer Claude-Gaspard Bachet, who put it in his book of puzzles in the early 1600s.

★ Twenty-seven coins (blocks)

Twenty-seven coins, one heavier, three weighings. The program below does the first weighing: 9 coins against 9, and group is set to the first coin of the nine that must hold the fake (1, 10 or 19). Finish it, so that after three answers it says The fake is coin and the number. Then press Test.

★★ Read the answers (Python, from Grade 8)

A plan has been weighed, and the balance gave three answers. Write decode(plan, coins, said) that gives back the fake as a list, [coin, 'heavy'] or [coin, 'light'], or None if no case gives those answers. plan is a list of weighings (each a left list and a right list), coins the number of coins, and said the list of answers.

def decode(plan, coins, said):    # try every case, and give back the one that matches    return None plan = [    [[1, 4, 7, 9], [2, 3, 6, 10]],    [[2, 5, 7, 8], [1, 3, 4, 11]],    [[3, 6, 8, 9], [1, 2, 5, 12]],]print(decode(plan, 12, ['right', 'left', 'level']))

★★★ Which first weighings pass the count? (Python, from Grade 8)

With coins coins, one fake (heavier or lighter), and weighings weighings, the first weighing puts k coins on each pan. If it tips, 2 × k cases are left (k that could be heavier and k that could be lighter); if it balances, 2 × (coins − 2 × k) cases are left. Either way, the weighings that remain give at most 3 to the power (weighings − 1) answers. Write first_weighings(coins, weighings) that gives back the list of every k, from 1 up, for which both piles pass that count. What do you find for 12 coins, and for 13?

def first_weighings(coins, weighings):    # every k for which both piles fit in the answers still to come    return [] print(first_weighings(12, 3))

• Grade 6, Zeros and Ones: each extra bit doubles the patterns; each extra weighing triples them.
• Grade 8, Searching and Sorting: binary search, which halves what is left with each look.
• How does the mind-reading card trick work? Five yes-or-no answers read a number in binary; here three weighings read a coin in threes.
• Can you cross the river with the tiger, the goat and the grass? Another puzzle solved by listing every case a program can check.