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

Home > Probability
Switching Teams (Posted on 2014-02-28) Difficulty: 3 of 5
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).

No Solution Yet Submitted by tomarken    
Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution n = 4 (spoiler) | Comment 5 of 8 |
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
  Posted by Steve Herman on 2014-02-28 16:19:41

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


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

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information