Conversation

My National Review Online "Diary" column for December 2002 included a brainteaser about finding a conversation partner.  Here it is..

Conversation

——————

I go into a meeting which consists of six people sitting in a line along one side of a table, with a single chairman facing them on the other side.  I take a seat at the end of the line, so now there are seven of us sitting in a line, side by side.  The chairman announces:  “When I say ‘Go!’ I want you to begin a conversation with one of the people next to you.”  Assuming that, on the word of command, people (except the ones at the ends, who have no choice) turn either to their right or their left at random, and assuming that those who find a partner at once in this way stick with that partner, and assuming that those who don’t find a partner at once will behave rationally, doing their best to pair off with someone to their left or right, what is the probability I shall find myself with no-one to talk to?

———————————————
Solution.  Note the two conditions:  (1) The "randomness" condition — at the word of command, the middle five people turn right or left at random.  (2) The "rationality" condition — that everyone thereafter behaves rationally.

There are seven of us in a line, say A, B, C, D, E, F, and G.  I myself am A.  The key to whether or not I get a conversation partner is of course the behavior of B.

Since there are seven of us, one person is going to be left without a partner.  B wants to be sure it isn't him.

In the absence of the randomness condition, B's best strategy would simply be to turn directly to me on the word "Go!"  Since I, being at the end of the line, have no choices, he would then be certain to have a partner.

With the randomness condition I imposed, things are trickier.  On the word "Go!" each of the middle five people turns to either left or right at random.  There are 32 possibilities, which you could write out, if you wanted to, as "RRRRR," "RRRRL," "RRRLR," and so on.

Sixteen of those possibilities begin with "L," that is, with B turned to the left, towards me.  We strike up a conversation, and that's the end of that.

Of the remaining sixteen, there are eight that begin with "RL..."  That is, B turned to his right, away from me, and C turned to his left, towards B.  B and C struck up a conversation, I am out of luck, and that's that.

The other eight break out like this:

RRRRR, RRRRL, RRRLR, RRRLL, RRLRR, RRLRL, RRLLR, RRLLL.

Consider the two that begin "RRRL..," and look at them from the point of view of B (who is represented by that first "R").  C is facing away from him, but D and E have paired off.  C has no choice but to turn to B.  Neither, of course, have you.  Thus B is certain to get a partner, no matter what he does!

So what does he do?  What does "rational" mean in this circumstance?  Well, it probably means something to do with the relative physical attractiveness of A and C, the odor of their breath, and other imponderables.  From a game-theory — and also, I think from a common-sense — point of view, B will turn to either right or left at random again, since it makes no difference to him which he does.  Since there are two possibilities out of 32 that this situation arose, there is a net one in 32 that he will turn to C.

In the other six cases (RRRRR, RRRRL, RRLRR. RRLRL, RRLLR, and RRLLL), B's best move is to turn to me.

My chance of being without a partner is therefore 8 out of 32 plus 1 out of 32.

Solution:  9/32.