My PhD student Kevin Milans brought back the following fascinating puzzle from FOCS; ~~I don't know who gave it to him~~ Kevin heard it from Mohammad Mahdian. I'll pose a few warm-up questions (with answers below horizontal lines) before I get to the real puzzle.

You are given n balloons, which appear to be utterly identical. For each integer k between 1 and n, exactly one of the balloons can hold 1/k liters of air. You know that the balloons have these different capacities, but you do not know which ballons have which capacities. The only way to discover the capacity of a balloon is to overinflate it, causing it to pop. Your goal is to fill the balloons with as much air as possible. You don't get credit for the air you put into balloons that pop; only the surviving balloons count toward your total. **How much air can you get?**

It's not hard to find a strategy to capture 1 liter of air. For example, you could put 1/n liters in each balloon. Or you could try to put 1 liter in each balloon, potentially popping all but the largest. Or you could try to put 1/10 liters in every balloon; in the worst case, you pop all but the ten largest balloons. The second and third strategies *could* get you more than 1 liter of air, but you can't *guarantee* that you'll get more than 1 liter, so in a worst-case sense, none of these strategies is better than any other. **Is there a strategy that guarantees more than 1 liter?**

No. There is *no* deterministic strategy that always gets more than 1 liter of air in the worst case. Imagine that the capacities are not fixed in advance, but rather are determined by an all-powerful malicious aversary. The adversary uses the following simple strategy for each integer k: The first time you try to put more than 1/k liters of air into a balloon, the adversary gives *that* balloon capacity 1/k, and the balloon immediately pops. With this strategy in place, if there are m surviving balloons, each of them contains at most 1/m liters, so the total amonut of air in all balloons is at most 1 liter.

But what about randomized strategies? **Can we guarantee an ***expected* return larger than 1 liter?

Yes! Consider the case of two balloons. Choose one balloon at random and inflate it to 1 liter. If it survives, inflate the other balloon to 1/2 liter, for a total return of 3/2 liters. If the first balloon pops, inflate the second balloon to 1 liter, for a total return of 1 liter. Since you are equally likely to choose either balloon first, each of these two cases is equally likely, so your expected return is 5/4 liters.

We can generalize this idea to larger values of n by inflating the balloons in random order. Initlally, let i = 1. Pick up a random empty balloon and give it 1/i liters. If the balloon pops, shrug and move on. If the balloon does not pop, increment i. Repeat this procedure until there are no more empty balloons. At the end, the L largest balloons are fully inflated, for some integer L, and all smaller balloons have popped.

Balloon k (the one with capacity 1/k) survives if and only if balloons 1,2,...,k are inflated in that order, which happens with probability exactly 1/k!, because the order is chosen uniformly at random. Thus, our expected total return is at most ∑_{k≥1} 1/k·k! ≈ **1.3178 liters**.

This is *not* the best strategy. Can you do better? (I'll post a better strategy in a few days.)

Is there a randomized strategy whose expected return is not bounded by any constant? I suspect the answer is no, but I don't have a proof. Yet.

## Recent Comments