Puzzles and Brainteasers, lesson 7
Search and worst cases
The fewest tries that work even when luck is against you.
Some puzzles ask for a plan that always works in the fewest tries, however unlucky you are: the floor where a dropped phone starts to break, or the largest number in a list. The answer is the worst case of the best plan. You need the case counting of the weighings lesson and nothing else.
Part 1. Even out the worst cases
Find the fewest drops that always work with two phones, by making every outcome cost the same.
Guess first
A tower has 100 floors. From some lowest floor up, a dropped phone breaks; from any floor below that, it lands unharmed and can be dropped again. It might break even from floor 1, or not at all. You have two identical phones. What's the fewest drops that always finds that floor?
Once a phone breaks, the other must climb a floor at a time from the last safe floor, or a break could leave a floor untested. So an early break is expensive, and a good plan prices that in.
Example 1.1
Two phones, 100 floors
Find a plan that always finds the floor, and the fewest drops it can promise.
- One phone leftk drops settle k floors
A single phone can only climb floor by floor.
- Place the first dropfloor k, with k drops to spend
If it breaks, floors 1 to k − 1 take k − 1 more drops, k in all. Start any higher and a break costs more than k.
- Shorten each stepthen k − 1 floors higher, then k − 2
Each drop that survives spends one, so the next break must leave one floor fewer to climb.
- Count what k drops coverk + (k − 1) + … + 1 = k(k + 1)/2
The steps shrink by one each time, down to 1.
- Find the smallest k13 × 14 / 2 = 91 < 100 ≤ 105 = 14 × 15 / 2
13 drops can't cover 100 floors, and 14 can.
Answer14 drops: the first phone goes from floors 14, 27, 39, 50, 60 and so on, until it breaks.
With steps of 10, an early break is cheap and a late one dear, and the late ones set the worst case. Shrinking steps move work from the dear outcomes to the cheap ones until all cost the same.
Minimax
Choose the plan whose worst case is smallest, which is called minimising the maximum. Aim for a plan where every outcome costs the same.
2 phones, k drops → k(k + 1)/2 floors
Halving is the tempting plan. If the first phone breaks at floor 50, the second must climb floors 1 to 49: 50 drops in all. Halving suits tests that cost nothing when they fail; here each failure costs a phone.
Your turn
Same rules and two phones, but the tower has 1,000 floors. What's the fewest drops that always finds the floor?
Part 2. Compare in pairs
Find the largest and the smallest of a list in the fewest comparisons, by pairing first.
Keep going with Pro
You've done the first part. Pro opens the rest of this lesson, and every other one.
- Compare in pairs
- Average or worst case
Puzzles and Brainteasers overviewSpotted a mistake? Tell us.