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?
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.
- Split into three3 + 3 + 3
Put 3 coins on each pan and keep 3 off the scale.
- 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.
- 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.
- Count the outcomes3 × 3 = 9
Two weighings give 9 different runs of outcomes, one for each coin.
Answer2 weighings.
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?
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.
- The counting bound
- Yes-or-no questions
Puzzles and Brainteasers overviewSpotted a mistake? Tell us.