Harmonic Hot Air

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.

Comments

[Danil]

Best I can do comes to (π^2)/6.

Mohammad Mahdian posed this puzzle at FOCS.

[Arthur Ramer, School of Computer Science, University of NSW, Sydney, Australia]

The best solution is indeed \pi^2/6 as equal to 1+1/2^2+1/3^2+...
The easy way to find it, write E_n for the expected value that can be realised with n balloons. Then consider n+1 balloons and the possible sequences of inflating (it is fairly obvious that simulataneous inflating is never better
than sequential, for any subgroup of balloons).

With probability n/(n+1) the smallest balloon is *not* inflated last; then one can realise E_n volume. In the remaing cases of the smallest balloon balloon
being last (prob. 1/(n+1)), the expected volume is E_n + 1/(n+1). And, obviously, E_1=1.

This gives E_{n+1}=n/(n+1) E_n + 1/(n+1)(E_n+1/(n+1)) = E_n+1/(n+1)^2
for the limiting value 1 + 1/2^2 + .. = \pi^2/6 = 1.64..

[Bram Cohen]

I came up with the same answer as the other commenters did, but it isn't obvious to me how to prove that that's the best possible result.

[Danil]

It wasn't obvious to me either, until Arthur added his remarks. That makes it clear that
E(n) = E(n-1) + P(n)C(n) where
E is the expectation of the stratgy
P is the probability of successfully identifying the nth balloon
C is the amount of air the strategy puts in the nth ballon.

The maximum possible value for C(n) is 1/n, so it remains only to determine the maximum value of P(n). This can be shown to be 1/n by induction as follows.

Assume we have two balloons, where we know the capasity of the smaller. The two balloons are indistinguishable when we fill both up to that point. If we attempt to add an infinitesmal amount of air to one balloon, we will succeed 1/2 of the time.

Now assume it is true that we can identify the smallest ballon from a group of n balloons with probability 1/n. What happens with n+1 balloons? We fail immediately with probability 1/n+1, therefore we are intermediately successful with probability n/n+1 and are completely successful with probability n/(n+1)*1/n = 1/(n+1).

Therefore, the highest possible value a strategy can obtain for P(n) is 1/n. Ergo, no strategy can have an expectation higher than 1.64....

It only remains to show existance of a strategy that attains that limit. Which presumably y'all have done. QED.

[Amit Chakrabarti]

Good puzzle!

Would have made a cute new homework question for Algorithms class... except, now it's on the web for all to see!

[JeffE]

So rephrase it in terms of filling wooden boxes with gold dust, or filling hats with mercury, or asking alumni for donations, or jampelating gleeblezidos at flargens, or something.

[Amit Chakrabarti]

In fact googleproofing a puzzle is hard. Changing the key nouns in the problem statement is the most obvious idea, but try a google search for
[fill capacities "as much" "as possible" surviving]

!!

[Tits Magee]

thats all good and shit but what does that have to do with flargens?...what the fuck is a flargen?