insideout Get Pro

04 · Weighings and information

Pro

Puzzles and Brainteasers, lesson 4

Weighings and information

Count what each test can tell apart to find the fewest tests.

Some puzzles ask for the fewest tests that always find something: a fake coin with a balance, or a hidden number with yes-or-no questions. The way in is to count the cases the answer could be, and how many of them one test can tell apart. You need powers of 2 and 3, and nothing else.

Part 1. Three outcomes per weighing

Find one heavier coin in the fewest weighings by splitting the coins into three groups.

Guess first

9 coins look identical, but one is slightly heavier than the rest. You have a balance with two pans and no weights. What's the fewest weighings that always finds the heavy coin?

2. A balance can tip left, tip right or stay level, and a good plan uses all three outcomes. The example shows how.

The obvious plan halves the coins: 4 against 4 with one aside, then 2 against 2, then 1 against 1. That takes three weighings in the worst case. It treats the balance as a yes-or-no test, and a balance has three outcomes.

Example 1.1

Nine coins, three groups

Find the heavy coin among 9 in two weighings.

  1. Split into three3 + 3 + 3

    Put 3 coins on each pan and keep 3 off the scale.

  2. Read the first weighingleft down, right down or level

    A pan that goes down holds the heavy coin. If the pans stay level, it's among the 3 left off. Either way, 3 coins remain.

  3. Split the 31 + 1 + 1

    Put one coin on each pan and keep one off. The pan that goes down holds it, and level means it's the one left off.

  4. Count the outcomes3 × 3 = 9

    Two weighings give 9 different runs of outcomes, one for each coin.

Answer2 weighings.

left downit's on the leftlevelit's one of the 3 asideright downit's on the right3 coins a pan, 3 coins aside
Figure 1One weighing, three outcomes. Whichever way the balance goes, it points to one group of 3 coins, so 9 suspects become 3, and the next weighing turns 3 into 1.

Every weighing ends one of three ways, so two weighings have 3 × 3 = 9 possible runs. 9 coins need 9 different runs, one per coin, so 2 is just enough. One weighing has 3 runs and can't single out one coin among 9.

Three-way split

Split the coins that could be the heavy one into three groups as equal as you can, and weigh two equal groups against each other. Whatever happens, one group is left. k weighings find one heavy coin among as many as 3ᵏ coins, read "3 to the power k".

k weighings → up to 3ᵏ coins

Halving wastes the third outcome: level is news too, since it says the coin is off the scale. When the coins don't split evenly, keep every group to a third of them, rounded up, with the two on the pans equal. 10 coins go 3, 3 and 4.

Your turn

Now there are 100 coins, and one is heavier. What's the fewest weighings that always finds it?

4 weighings tell apart at most 3⁴ = 81 coins, too few for 100. 5 are enough: keep each group to a third, rounded up, and 100 suspects shrink to 34, 12, 4, 2 and 1. The answer 7 comes from halving, since 2⁷ = 128.

Part 2. The counting bound

Count the cases a puzzle can be in, and find the fewest weighings any plan could need.

Keep going with Pro

You've done the first part. Pro opens the rest of this lesson, and every other one.

Still to come
  1. The counting bound
  2. Yes-or-no questions

Puzzles and Brainteasers overviewSpotted a mistake? Tell us.