insideout Get Pro

07 · Search and worst cases

Pro

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?

14. Halving would take 7 with plenty of phones, but here every break costs a phone.

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.

  1. One phone leftk drops settle k floors

    A single phone can only climb floor by floor.

  2. 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.

  3. 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.

  4. Count what k drops coverk + (k − 1) + … + 1 = k(k + 1)/2

    The steps shrink by one each time, down to 1.

  5. 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.

drops so farfloors left to climbSteps of 10: the worst break costs 1910111213141516171819102030405060708090100Steps of 14, 13, 12 and down: none costs more than 141414141414141414141414121427395060697784909599100floor of the first phone's drop
Figure 1Where the first phone might break, and what that costs in all: drops so far (dark) plus floors left to climb (light). With steps of 10 the cost climbs to 19. With steps that shrink by one, no break costs more than 14.

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?

44 drops settle 44 × 45 / 2 = 990 floors and 45 settle 1,035, so start from floor 45. 32 is √1,000, the size of equal steps, which can cost 62 drops. 500 comes from halving.

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.

Still to come
  1. Compare in pairs
  2. Average or worst case

Puzzles and Brainteasers overviewSpotted a mistake? Tell us.