You and three friends decide to play a strange game.
Into a hat you place four slips of paper. One has a gold star, one has a red X, and the other two are blank.
Each round will proceed as follows: Each person will select a piece of paper from the hat. Whichever player chooses the slip with the red X joins the "team" of the player who chooses the slip with the gold star. Then all four slips are returned to the hat and the process is repeated. The game ends when all four players are on the same team.
1) On average, how many rounds will the game last until all four players are on the same team?
2) Find a general solution for n players (where the hat contains one gold star, one red X, and n-2 blank slips).
Interesting. A random walk problem.
The different states are:
a) (1,1,1,1)
b) (2,1,1)
c) (2,2)
d) (3,1)
e) (4)
On any given round, the transition probabilities are:
a --> b 100%
b --> c 1/6 (if the two singles get the two marked cards)
--> d 1/3 (if one of the two-team gets the star and the other gets a blank)
--> b 1/2 (otherwise)
c --> d 2/3 (if each team gets a blank)
--> c 1/3 (otherwise)
d --> e 1/4 (if the single player gets the X)
--> c 1/4 (if the single player gets the star)
--> d 1/2 otherwise
Let f(x) be the expected number of turns to get from state x to state e.
Then f(e) = 0
f(d) = 1 + (f(e) + f(c) + 2*f(d))/4
f(c) = 1 + (2*f(d) + f(c)) / 3
f(b) = 1 + (f(c) + 2*f(d) + 3*f(b))/6
f(a) = 1 + f(b)
Solving gives
f(e) = 0
f(d) = 5.5 turns
f(c) = 7 turns
f(b) = 8 turns
f(a) = 9 turns
Final answer (fixed with a correction from Charlie), is 9 turns (f(a)). This agrees with his math and his simulation, so I am very confident.
Edited on February 28, 2014, 9:07 pm
n = 4 (spoiler)
