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).

Initially we can consider each person to be a team so there are 4 teams. Membership: (1,1,1,1)

With just 1 round this is transformed into 3 teams, one with two members and two with one member each. Membership: (2,1,1). This is the only configuration of 3 teams.

The next round this either does not change (prob. 1/2, as this happens if either of the two members on the 2-member team gets the red X so he either stays on the same team or just changes the identity of his teammate) or changes to 2 teams(prob 1/2: either of the single-player teams gets the red X). The overall probability is 1/6 of changing to a membership of (2,2) and 1/3 of becoming (3,1); the former if the two marked papers go to the two 1-member teams and the latter if one of these team players gets the X and a member of the 2-member team gets the star.

Since the probability of remaining (2,1,1) is 1/2, the expected number of  rounds to proceed to one of the 2-team states is 2, bringing the total expected rounds to 3 so far.

Call the expected number of rounds from (3,1), L and from (2,2), E (lopsided and even).

From the (3,1) state, the probability of going to (4), that is, the end state, is 1/4. The probability of remaining in the (3,1) state is (3/4)*(2/3)=6/12=1/2. The probability of going to the (2,2) state is (3/4)*(1/3)=3/12=1/4.

So from the (3,1) state, the expected remaining length,
L = 1/4 * 1 + 1/2 * (1+L) + 1/4 * (1+E).

Similarly, from the (2,2) state the expected remaining length of the game is,
E = 1 + (1/3) * E + (2/3) * L   -- the 1 being combined 1/3 * 1 + 2/3 * 1
or
2/3 * E = 1 + (2/3) * L
or
E = 3/2 + L

Substituting int he previous equation:

L = 1/4 * 1 + 1/2 * (1+L) + 1/4 * (1+3/2 + L)
  = 1/4 + 1/2 + 1/4 * 5/2 + L/2 + L/4
L/4 = 11/8
L = 11/2

E = 14/2 = 7

Remember that in the transition from 3 teams to 2, the state (3,1) is twice as likely as to (2,2) so the overall added rounds is

(2/3)*L + (1/3)*E = 11/3 + 14/6 = 6

and the expected length of the game is 3 + 6 = 9 rounds.

Simulation verification:

DEFDBL A-Z
RANDOMIZE TIMER
n = 4
DO
  tr = tr + 1
  REDIM team(n)
  FOR i = 1 TO n: team(i) = i: NEXT

  DO
    r1 = INT(n * RND(1) + 1)
    DO
      r2 = INT(n * RND(1) + 1)
    LOOP UNTIL r2 <> r1
    team(r2) = team(r1)
    drawct = drawct + 1
    done = 1
    FOR i = 1 TO n - 1
     IF team(i) <> team(i + 1) THEN done = 0
    NEXT
  LOOP UNTIL done
  PRINT tr, drawct / tr
LOOP

finds an average of 9.003221150570205 rounds after 161433 trials, when manually stopped.

Part 2:

Substituting other values of n, as in

DEFDBL A-Z
RANDOMIZE TIMER
n = 5
FOR tr = 1 TO 200000
  REDIM team(n)
  FOR i = 1 TO n: team(i) = i: NEXT

  DO
    r1 = INT(n * RND(1) + 1)
    DO
      r2 = INT(n * RND(1) + 1)
    LOOP UNTIL r2 <> r1
    team(r2) = team(r1)
    drawct = drawct + 1
    done = 1
    FOR i = 1 TO n - 1
     IF team(i) <> team(i + 1) THEN done = 0
    NEXT
  LOOP UNTIL done
  PRINT tr, drawct / tr
NEXT

finds 16.05239 for n=5 after 200,000 iterations.

n=6 yields 24.962935 and n=7 yields 35.97036 trials on average.

It appears that the expected number of rounds is (n-1)^2.