Welcome to techInterview, a site for technical interview questions, brain teasers, puzzles, quizzles (whatever the heck those are) and other things that make you think!
You have $10,000 dollars to place a double-or-nothing bet on the Yankees in the World Series (max 7 games, series is over once a team wins 4 games).
Unfortunately, you can only bet on each individual game, not the series as a whole. how much should you bet on each game, so that, if the yanks win the whole series, you expect to get 20k, and if they lose, you expect 0?
Basically, you know that there may be between 4 and 7 games, and you need to decide on a strategy so that whenever the series is over, your final outcome is the same as an overall double-or-nothing bet on the series.
This probably isn’t the cleanest solution, but…
a dynamic-programming type solution is:
(1) Create a 5x5 matrix P.
So, P[i,j] holds your pile of money when the yanks have won i games and the mets have won j games.
initialize P[4,j] := 20 for j from 0 to 3 initialize P[i,4] := 0 for i from 0 to 3
fill P in bottom-right to top left by averaging bottom and right adjacent cells:
P[i,j] := (P[i+1,j]+P[i,j+1]) / 2
(2) Make another 5x5 matrix, B, which represets your bet at any-time.
So, B[i,j] represents your bet when the yanks have won i games and the Mets j games.
fill this top-left to bottom right by:
B[i,j] = P[i+1,j] - P[i,j]
(3) Look in matrix B for your bet at any time.
The final matricies are: