Physically Incorrect

This is the solution to the Matchmaking Game riddle posted on this blog.

The answer is 7.46 pairs, on average.

If you get sidetracked by counting configurations, stop. The key to solving this puzzle is thinking in terms of a pair of adjacent seats, computing the average for just one pair and using the fact that the average of sums is the sum of averages. Let me show you what I mean in more detail.

Define a random variable X1 as follows:

X1 = 0 is there isn’t a female-male pair in seats 1 & 2, and X1 = 1 if there is.

Note that X = X1 + X2 + … + X14 is the total number of pairs for a particular seating arrangement.

Now, if E[Z] is the expected value of a random variable Z, then Average number of pairs = E[X] = E[X1 + X2 + ... + X14] = E[X1] + E[X2] + …. + E[X14]. Each of the variables X1, X2, … X14 behaves in a similar manner, i.e. has the same probability distribution function, in “mathspeak” (subtle point: convince yourself that it doesn’t matter where the pair is. A pair of seats next to the edge of the row has the same probability distribution as a pair of seats in the middle). So let’s focus on a single pair, say X1; computing E[X1] would mean we could easily deduce E[X], since E[X] = 14E[X1].

By definition,

E[X1] = Prob[X1 = 1]*1 + Prob[X1=0]*0 = Prob(X1=1)

What is Prob[X1=1], really? It is the probability of getting a pair. There are four possible configurations, MM, MF, FM and FF, with probabilities:

MM:   7/15 * 6/14

FF: 8/15 * 7/14

MF:   7/15 * 8/14

FM: 8/15 * 7/14

For example, consider the probability of getting MF. That would be the probability of seating a guy in the first seat (7 guys, 15 seats, so that would be 7/15), and seating a girl in next seat (8 girls, 14 seats left, so 8/14).

To sum up, Prob[X1=1]= Prob[MF] + Prob[FM] = 8/15, and hence E[X] = 14*E[X1] = 14*Prob[X1=1]  =  7.46.