Thursday, March 3, 2011

A puzzle and challenge

Imagine you have a black box that can play a betting game. On the top of the box is a button, two LEDs (red and green), and a slot in which you can insert a 25 cent piece.

You start the game by pressing the button. This resets the box to the initial state.

If the box is in the initial state, whenever you insert a 25 cent piece, the red LED will light (nothing else happens and you lose your money). While the box is in the initial state, you may insert as many 25 cent pieces as you wish (and they each will be happily devoured).

The box will remain in the initial state for somewhere between 1 millisecond and 10 seconds, at which point it silently changes to the final state.

In the final state, if you insert a 25 cent piece, the green LED will light, your 25 cent piece will be returned and the game is over. However, you may be awarded a bonus. The bonus starts at one dollar the instant the box changes to the final state, but the bonus is reduced by one cent every 10 milliseconds after the state change.

Once in the final state, the box remains there until the button is pressed to start the next round.

The challenge: develop and implement a strategy that maximizes your return.