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.


Mark Engelberg said...

Don't you need to know what the distribution is of the random process that determines the delay before switching to final state?

Joe Marshall said...

Part of the challenge would be to determine what distribution there is and to try to tale advantage of it.

James Antill said...

I assume that "the bettor" is non-human so can easily insert coins at centisecond intervals. And that the randomization is "perfect".

At that point it's basically a simple game of roulette, with 1011 numbers to choose from.

If you pick number 1011 you always get back your 25c.

If you pick number 1000 you always get back your 25c, and 1/1000 of the time you get $1 and 1/1000 of the time you get 99c [skip 97] and 1/1000 of the time you get 1c.

If you pick number 999 you get back your 25c 999/1000 times. Lose 25c once, and have the same bonus payout as picking 1000.

The same happens for 998, but you lose 25c twice.

[skip ...]

If you pick 1, then you get back 25c 1/1000 but lose it 999/1000. And get a bonus of $1 1/1000.

Seems pretty obvious you should always pick 1000, to me :).

James Antill said...

Blah, off by "one" errors in my answer (that's what QA is for :). There's 1100 numbers, where 1100 just gives you your money back and 1099 dito. but gives you 1c every 100 tries). So you still want to pick 1000 all the time :).

Gareth McCaughan said...

James, your answer has to be wrong, because for all you know the machine may be set up so that it always switches state after only 5s. In that case, you maximize your return by inserting the coin then.

JRM, is the idea that we play this game exactly once, or that we get to play lots of times to figure out the behaviour?

Joe Marshall said...

The game will be played a lot.

John Metcalf said...

Always put 25c in after 25 seconds. You never lose anything, and occasionally you receive a bonus.