All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
Game Over! (Posted on 2006-05-22) Difficulty: 3 of 5
You are playing a game where there are 9 boxes laid out in a row, numbered 1 through 9 from left to right. Randomly placed in one of the boxes is a slip of paper that says "GAME OVER". The other eight boxes each contain $1000.

You are to pick the boxes one at a time. If you pick a box with $1000, you keep the money and you must pick another box. If at any point you select the box that says "GAME OVER", the game ends and you leave with the prize money you've accumulated to that point. The only catch is, the host of the game show will tell you which direction the "GAME OVER" box is in, and you must guess your next box in that direction (it's like a guessing game where you have to guess a number from 1 to 9, and after each guess the host tells you "higher" or "lower" until you finally guess the number he is thinking of). However, the goal of this game is not to land on the "GAME OVER" box (since you eventually will), but to maximize the number of guesses you take (and thus your profit) before you land on it.

Question 1: Is there an optimal strategy for this game? If so, what is it and what is your expected profit? If not, why not?

Question 2: What if you were the host, and instead of randomly placing the "GAME OVER" box, you could choose where it went - is there a strategy that would minimize the expected profit of the contestant?

No Solution Yet Submitted by tomarken    
Rating: 3.5000 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution for question 2 | Comment 4 of 14 |
The host should place the box at either box 1 or box 9 (of the contestant plays optimally, i.e. choosing always left- or rightmost box).
As we do not exactly know which policy is used by the contestant, we can safely assume he will choose leftmost and rightmost both with probability 1/2.
For simplicity we can assume that the reward is 1 for each box.

define S(m,n) as the expected pay-off if the host chooses box m out of n different boxes. This implies S(1,1) = 0 (only one box to choose from).
We have:
S(1,n) = 1/2(S(1,n-1) + 1)
S(n,n) = 1/2(S(n-1,n-1)+1)
S(m,n) = 1/2(S(m,n-1)) + 1/2(S(m-1,n-1))
The first two follow from the policy of the contestant: with probability 1/2, the games goes on with one box less. The last one signifies if the chosen box is somewhere in the middle: either the rightmost box disappears or the leftmost. As the third value is the sum of the first two, it will be larger than both.
Calculating S(1,9) gives the expected profit:
S(1,9) = S(1,8)/2 + 1/2 = S(1,7)/4 + 1/4 + 1/2 = .... = 255/256.
So, instead of having expected payoff of 4000$ if the host chooses randomly, the contestant has only a expected payoff of 996.09 $.

  Posted by Robby Goetschalckx on 2006-05-22 12:32:42
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (5)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information