Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- This is a one-player game. The goal of the game is to have N points.
- You start with zero points.
- You take a turn by rolling a six-sided die.
- On a 1, you gain 1 point.
- On a 6, you lose all points.
- On a 2, 3, 4, or 5, nothing happens.
- On average, how many turns will it take you to reach N points?
- 6*((2^N)-1)
- f(cur, n): the expected number of turns to the end of the game
- if cur == n: 0
- else: (
- 1 + f(cur+1, n) +
- 1 + f(cur, n) +
- 1 + f(cur, n) +
- 1 + f(cur, n) +
- 1 + f(cur, n) +
- 1 + f(0, n)
- ) / 6
- == (6 + f(cur+1, n) + 4*f(cur, n) + f(0,n)) / 6
- let X = f(cur, n) when cur != n
- X = (6 + f(cur+1, n) + 4*X + f(0,n)) / 6
- 6*X = 6 + f(cur+1, n) + 4*X + f(0,n)
- 2*X = 6 + f(cur+1, n) + f(0,n)
- X = (6 + f(cur+1, n) + f(0,n)) / 2
- f(cur, n) = (6 + f(cur+1, n) + f(0,n)) / 2
- Let n == 4.
- Let Z = f(0,4)
- f(cur, n) = (Z + 6 + f(cur+1, n)) / 2
- f(4,4) = 0.
- f(3,4) = (Z + 6) / 2 = Z/2 + 3
- f(2,4) = (Z + 6 + Z/2 + 3) / 2 = (3/4)*Z + 9/2
- f(1,4) = (Z + 6 + (3/4)*Z + 9/2) / 2 = ((7/4)*Z + 21/2) / 2 = ((7/8)*Z + 21/4)
- f(0,4) = Z = (Z + 6 + (7/8)*Z + 21/4) / 2
- 2*Z = Z + 6 + (7/8)*Z + 21/4
- Z = 6 + (7/8)*Z + 21/4
- (1/8)*Z = 6 + 21/4
- Z = (6 + 21/4)*8 = 48 + 42 = 90
- WLOG, f(0, n) = uhhhhhhhh
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement