On Wed, Nov 28, 2012 at 12:17 AM, Gary Antonick <gantonick@post.harvard.edu> wrote:
Cornell mathematician Steven Strogatz thinks this is an unsolved problem but am wondering if there's something being overlooked.
Here's the basic -- and solved -- problem. There's a long line of people standing near each other. They're told to hold hands with someone - either the person to their right or to their left, if available, but not both. The ratio of the resulting singles to all the people in line approaches 1/e^2 as the line increases.
This seems not quite precisely defined. If we give people individually the instruction "If you're not holding hands with anyone, hold hands with either the person to your left or the person to your right, chosen at random, if both are available, or with the available one, if one of your neighbors is already holding hands with someone", then the number of singles depends on the order in which people are given this instruction. One way to define the problem is to give each person the instruction above in random order. But here's another way to interpret the problem: In each round, each person who is not holding hands with anyone yet chooses left or right randomly. If two people choose each other, they don't participate in future rounds. Continue until no two adjacent people are single. A slightly different version has someone whose right neighbor is already holding hands always choose L, rather than choosing L or R randomly, and I don't think that these two procedures end up with the same proportion of singles. It seems to me that the second procedure should have fewer singles. In particular, if you have a row of 4 singles, with couples on each side, the first procedure ends up with two singles with probability 4/11, while the second procedure ends up with two singles with probability 1/4. The same ambiguity exists in the two-dimensional case. But even in the one-dimensional case, we now have three problems. At least one of them is solved, and has the solution 1/e^2. But which one, and what are the solutions to the other two? Andy