As Andy said, the problem as given by Gary isn't well-defined. I offer a different rigorization. N people stand in line. There are 2^(N-1) ways they can take hands, ranging from nobody holding hands at all, to everybody taking hands to make a long chain. Of these 2^(N-1) ways, the "proper" patterns satisfy the following constraints: 1. Nobody is holding hands with both neighbors. 2. Of every pair of adjacent people, at least one of the pair is holding hands with somebody. If we select a pattern at random from among all proper patterns, what is the expected fraction of unpaired people? For N=1, it's 1. For N=2, it's 0. For N=3, it's 1/3. For N=4 there are two proper patterns, one with no singletons and one with 2, so the answer is 1/4. For N=5 there are three proper patterns, all with exactly one singleton, so the answer is 1/5. For N=6 the answer is back to 1/4 (three patterns with two singletons, and one with none). My intuition is that the limiting fraction will involve the golden ratio, not e; if that's the case it means I have the wrong rigorization. I think I'll Google for Strogatz and try to find out. Gary, where did you hear about this problem? On Wed, Nov 28, 2012 at 9:49 AM, Andy Latto <andy.latto@pobox.com> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun