« Logic: It's not just for breakfast any more! | Main | We're doomed »

November 08, 2005

Comments

Bill Tozier

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

Danil

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?

Bob Hearn

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

Bob Hearn

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.

Danil

You understand the card problem correctly.

Bob Hearn

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?

Vladimer

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.