## November 08, 2005

You know, this would be a perfect place to apply genetic programming.

Well, there ought to be a marginal improvement, for finite numbers of balloons, by using 1/z instead of 1/n (where z is the smallest unpopped balloon). Somehow I doubt that's the one that you mean.

This algorithm reminds me of the solution for another problem: consider a deck of N cards, each of which has a real number written on it. Reveal the numbers one at a time - the goal is to successfully identify the highest number in the deck when it appears (you have no knowledge of the numbers on the cards until you look at them, and can only choose the most recently turned card). What strategy gives the highest chance of success?

Is the card problem like the two-envelopes paradox, where you're not given the distribution the numbers are drawn from?

If I understand the card problem correctly, the following strategy would seem to have a 1/3 chance of success:

Flip over the first N/2 cards, noting the highest in that range. Then keep flipping until you find a higher one. If you do, choose it.

You understand the card problem correctly.

OK. And in that family of strategies, it's easy to see that N/2 is the optimal turning point. But is there any other kind of strategy to consider, or is 1/3 provably the best you can do?

Are you allowed to inflate a balloon in stages?
As in to put some air in one, put some air in another one, and then
add some more in the first one?

The comments to this entry are closed.