[math-fun] checkerboard version of an e-related dating problem
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. Now the unsolved version: what if the people are instead in a grid and have up to four people to choose from (but can hold hands with at most 1)?
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
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
Whether in the 1D or 2D grid case (or for that matter in nD), one way to give this problem well-defined probabilities (that I think is in some sense the most natural way) is to first give each pair of adjacent hands an independent probability of ½ as to whether they or not they hold each other -- and then restrict attention to only those outcomes satisfying the conditions of the problem: That each person holds at most one hand. I'm not sure if this agrees with the probabilities in one of Andy's two methods. The problem becomes more symmetrical if the 1D case is a circle instead of a line (and in nD a K^n grid on an n-dimensional torus) -- but this won't affect the asymptotic expected fraction of singles. --Dan On 2012-11-28, at 6:49 AM, Andy Latto 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. . . . . . . . . .
On Wed, Nov 28, 2012 at 1:49 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Whether in the 1D or 2D grid case (or for that matter in nD), one way to give this problem well-defined probabilities (that I think is in some sense the most natural way) is to first give each pair of adjacent hands an independent probability of ½ as to whether they or not they hold each other -- and then restrict attention to only those outcomes satisfying the conditions of the problem: That each person holds at most one hand.
That's a different problem, because you're ignoring the second condition of the problem; no two adjacent single people. If you restrict attention to those, you have a formulation equivalent to Allan's, I think, but different from both of mine. Andy
I'm not sure if this agrees with the probabilities in one of Andy's two methods.
The problem becomes more symmetrical if the 1D case is a circle instead of a line (and in nD a K^n grid on an n-dimensional torus) -- but this won't affect the asymptotic expected fraction of singles.
--Dan
On 2012-11-28, at 6:49 AM, Andy Latto 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. . . . . . . . . .
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
Good point, but it wasn't intentional -- I was just careless. So, I should've said "then restrict attention to only those outcomes satisfying the conditions of the problem: That each person holds at most one hand and no two singles are adjacent." Or, put another way: After giving each pair of adjacent hands an independent ½ probability of holding each other, restrict attention to the configurations having a maximal set of adjacent pairs of gridpoints each connected by the line segment between them, such that no line segment touches another one. (This almost suggests a way to obtain the results for 1D.) --Dan On 2012-11-28, at 11:44 AM, Andy Latto wrote:
On Wed, Nov 28, 2012 at 1:49 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Whether in the 1D or 2D grid case (or for that matter in nD), one way to give this problem well-defined probabilities (that I think is in some sense the most natural way) is to first give each pair of adjacent hands an independent probability of ½ as to whether they or not they hold each other -- and then restrict attention to only those outcomes satisfying the conditions of the problem: That each person holds at most one hand.
That's a different problem, because you're ignoring the second condition of the problem; no two adjacent single people. If you restrict attention to those, you have a formulation equivalent to Allan's, I think, but different from both of mine.
Andy
I'm not sure if this agrees with the probabilities in one of Andy's two methods.
The problem becomes more symmetrical if the 1D case is a circle instead of a line (and in nD a K^n grid on an n-dimensional torus) -- but this won't affect the asymptotic expected fraction of singles.
--Dan
On 2012-11-28, at 6:49 AM, Andy Latto 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.
Going back to trying to make sense of the 1D problem, the number of valid configurations for N people satisfies a[0]=a[1]=a[2]=1, a[n+3]=a[n]+a[n+1]. There are about half a dozen sequences in OEIS with this "tribonacci" rule, with minor differences in offset and initial conditions. Let b[N] be the aggregate number of singletons in all valid N-person configurations. I'm getting a recurrence b[n+3] = a[n] + b[n] + b[n+1]. Now b[0] = 0, b[1] = 1, b[2] = 0, and then the recurrence gives 2, 3, 3, 6, 7, 10, 15, 19 ... The last entry diverges from A121833, but the rule is so simple that I can't believe it's not in OEIS, so I must have miscalculated. Anyway, the wanted expected number of singletons is lim b[n]/a[n]. Peering at the small entries I realize I must have blundered somewhere. Can somebody with more attention to give it please repeat this reasoning but do it correctly? On Wed, Nov 28, 2012 at 3:09 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Good point, but it wasn't intentional -- I was just careless.
So, I should've said "then restrict attention to only those outcomes satisfying the conditions of the problem: That each person holds at most one hand and no two singles are adjacent."
Or, put another way: After giving each pair of adjacent hands an independent ½ probability of holding each other, restrict attention to the configurations having a maximal set of adjacent pairs of gridpoints each connected by the line segment between them, such that no line segment touches another one.
(This almost suggests a way to obtain the results for 1D.)
--Dan
On 2012-11-28, at 11:44 AM, Andy Latto wrote:
On Wed, Nov 28, 2012 at 1:49 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Whether in the 1D or 2D grid case (or for that matter in nD), one way to give this problem well-defined probabilities (that I think is in some sense the most natural way) is to first give each pair of adjacent hands an independent probability of ½ as to whether they or not they hold each other -- and then restrict attention to only those outcomes satisfying the conditions of the problem: That each person holds at most one hand.
That's a different problem, because you're ignoring the second condition of the problem; no two adjacent single people. If you restrict attention to those, you have a formulation equivalent to Allan's, I think, but different from both of mine.
Andy
I'm not sure if this agrees with the probabilities in one of Andy's two methods.
The problem becomes more symmetrical if the 1D case is a circle instead of a line (and in nD a K^n grid on an n-dimensional torus) -- but this won't affect the asymptotic expected fraction of singles.
--Dan
On 2012-11-28, at 6:49 AM, Andy Latto 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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I was talking to Strogatz yesterday about the 1D problem and he mentioned that the 2D version was unsolved. He just sent me a related chapter from Sid Redner's " Kinetic-View-Statistical-Physics<http://www.amazon.com/Kinetic-View-Statistical-Physics/dp/0521851033>." I'll forward the chapter to each of you by email. On Wed, Nov 28, 2012 at 12:42 PM, Allan Wechsler <acwacw@gmail.com> wrote:
Going back to trying to make sense of the 1D problem, the number of valid configurations for N people satisfies a[0]=a[1]=a[2]=1, a[n+3]=a[n]+a[n+1]. There are about half a dozen sequences in OEIS with this "tribonacci" rule, with minor differences in offset and initial conditions.
Let b[N] be the aggregate number of singletons in all valid N-person configurations. I'm getting a recurrence b[n+3] = a[n] + b[n] + b[n+1]. Now b[0] = 0, b[1] = 1, b[2] = 0, and then the recurrence gives 2, 3, 3, 6, 7, 10, 15, 19 ... The last entry diverges from A121833, but the rule is so simple that I can't believe it's not in OEIS, so I must have miscalculated.
Anyway, the wanted expected number of singletons is lim b[n]/a[n]. Peering at the small entries I realize I must have blundered somewhere. Can somebody with more attention to give it please repeat this reasoning but do it correctly?
On Wed, Nov 28, 2012 at 3:09 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Good point, but it wasn't intentional -- I was just careless.
So, I should've said "then restrict attention to only those outcomes satisfying the conditions of the problem: That each person holds at most one hand and no two singles are adjacent."
Or, put another way: After giving each pair of adjacent hands an independent ½ probability of holding each other, restrict attention to the configurations having a maximal set of adjacent pairs of gridpoints each connected by the line segment between them, such that no line segment touches another one.
(This almost suggests a way to obtain the results for 1D.)
--Dan
On 2012-11-28, at 11:44 AM, Andy Latto wrote:
On Wed, Nov 28, 2012 at 1:49 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Whether in the 1D or 2D grid case (or for that matter in nD), one way to give this problem well-defined probabilities (that I think is in some sense the most natural way) is to first give each pair of adjacent hands an independent probability of ½ as to whether they or not they hold each other -- and then restrict attention to only those outcomes satisfying the conditions of the problem: That each person holds at most one hand.
That's a different problem, because you're ignoring the second condition of the problem; no two adjacent single people. If you restrict attention to those, you have a formulation equivalent to Allan's, I think, but different from both of mine.
Andy
I'm not sure if this agrees with the probabilities in one of Andy's two methods.
The problem becomes more symmetrical if the 1D case is a circle instead of a line (and in nD a K^n grid on an n-dimensional torus) -- but this won't affect the asymptotic expected fraction of singles.
--Dan
On 2012-11-28, at 6:49 AM, Andy Latto 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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Andy, Allan, Dan - As you noticed pretty quickly, I didn't state the problem correctly. Thanks for pointing out. I'm actually interested in sequential and not simultaneous seating. The following is Strogatz' presentation from Joy of x. I'm wondering if a 2D version of this has been solved. Imagine there’s a very popular new movie showing at the local theater. It’s a romantic comedy, and hundreds of couples (many more than the theater can accommodate) are lined up at the box office, desperate to get in. Once a lucky couple get their tickets, they scramble inside and choose two seats right next to each other. To keep things simple, let’s suppose they choose these seats at random, wherever there’s room. In other words, they don’t care whether they sit close to the screen or far away, on the aisle or in the middle of a row. As long as they’re together, side by side, they’re happy. Also, let’s assume no couple will ever slide over to make room for another. Once a couple sits down, that’s it. No courtesy whatsoever. Knowing this, the box office stops selling tickets as soon as there are only single seats left. Otherwise brawls would ensue. At first, when the theater is pretty empty, there’s no problem. Every couple can find two adjacent seats. But after a while, the only seats left are singles—solitary, uninhabitable dead spaces that a couple can’t use. In real life, people often create these buffers deliberately, either for their coats or to avoid sharing an armrest with a repulsive stranger. In this model, however, these dead spaces just happen by chance. The question is: When there’s no room left for any more couples, what fraction of the theater’s seats are unoccupied? On Wed, Nov 28, 2012 at 12:42 PM, Allan Wechsler <acwacw@gmail.com> wrote:
Going back to trying to make sense of the 1D problem, the number of valid configurations for N people satisfies a[0]=a[1]=a[2]=1, a[n+3]=a[n]+a[n+1]. There are about half a dozen sequences in OEIS with this "tribonacci" rule, with minor differences in offset and initial conditions.
Let b[N] be the aggregate number of singletons in all valid N-person configurations. I'm getting a recurrence b[n+3] = a[n] + b[n] + b[n+1]. Now b[0] = 0, b[1] = 1, b[2] = 0, and then the recurrence gives 2, 3, 3, 6, 7, 10, 15, 19 ... The last entry diverges from A121833, but the rule is so simple that I can't believe it's not in OEIS, so I must have miscalculated.
Anyway, the wanted expected number of singletons is lim b[n]/a[n]. Peering at the small entries I realize I must have blundered somewhere. Can somebody with more attention to give it please repeat this reasoning but do it correctly?
On Wed, Nov 28, 2012 at 3:09 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Good point, but it wasn't intentional -- I was just careless.
So, I should've said "then restrict attention to only those outcomes satisfying the conditions of the problem: That each person holds at most one hand and no two singles are adjacent."
Or, put another way: After giving each pair of adjacent hands an independent ½ probability of holding each other, restrict attention to the configurations having a maximal set of adjacent pairs of gridpoints each connected by the line segment between them, such that no line segment touches another one.
(This almost suggests a way to obtain the results for 1D.)
--Dan
On 2012-11-28, at 11:44 AM, Andy Latto wrote:
On Wed, Nov 28, 2012 at 1:49 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Whether in the 1D or 2D grid case (or for that matter in nD), one way to give this problem well-defined probabilities (that I think is in some sense the most natural way) is to first give each pair of adjacent hands an independent probability of ½ as to whether they or not they hold each other -- and then restrict attention to only those outcomes satisfying the conditions of the problem: That each person holds at most one hand.
That's a different problem, because you're ignoring the second condition of the problem; no two adjacent single people. If you restrict attention to those, you have a formulation equivalent to Allan's, I think, but different from both of mine.
Andy
I'm not sure if this agrees with the probabilities in one of Andy's two methods.
The problem becomes more symmetrical if the 1D case is a circle instead of a line (and in nD a K^n grid on an n-dimensional torus) -- but this won't affect the asymptotic expected fraction of singles.
--Dan
On 2012-11-28, at 6:49 AM, Andy Latto 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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The PDF file Gary sent some of us explains this model carefully, and indeed, it resolves all the ambiguity in the original statement. In particular, it's different (at least on its face) from any of the interpretations Andy proposed in his first response. Furthermore, it definitely differs from my formulation, in which all the legal configurations are equally likely. This difference is already present for N=4. There are two legal configurations. If we write a 0 for a pair of unjoined hands, and 1 for a pair of held hands, these two configurations can be written 101 and 010. In my formulation these two configurations are equally likely. One of them has two singletons and one has none, for an average of one singleton per trial. But in Strogatz's formulation, the first bond to settle in creates one of the three preliminary configurations, 100, 010, 001, with equal likelihood. 010 is saturated, but 100 and 001 both must progress to 101. So 101 is twice as likely to occur as 010, for an average of 2/3 singletons per trial. At this point I'm perfectly ready to believe the e^(-2) result, and to agree that the 2-dimensional case is much, much harder to analyze. I wouldn't expect it to have a closed-form solution, but surely it's worth doing a big Monte Carlo trial on, say, a 100 by 100 grid, and feed the resulting average density to Simon's number recognizer. On Thu, Nov 29, 2012 at 12:47 PM, Gary Antonick <gantonick@post.harvard.edu>wrote:
Andy, Allan, Dan -
As you noticed pretty quickly, I didn't state the problem correctly. Thanks for pointing out. I'm actually interested in sequential and not simultaneous seating.
The following is Strogatz' presentation from Joy of x. I'm wondering if a 2D version of this has been solved.
Imagine there’s a very popular new movie showing at the local theater. It’s a romantic comedy, and hundreds of couples (many more than the theater can accommodate) are lined up at the box office, desperate to get in. Once a lucky couple get their tickets, they scramble inside and choose two seats right next to each other. To keep things simple, let’s suppose they choose these seats at random, wherever there’s room. In other words, they don’t care whether they sit close to the screen or far away, on the aisle or in the middle of a row. As long as they’re together, side by side, they’re happy.
Also, let’s assume no couple will ever slide over to make room for another. Once a couple sits down, that’s it. No courtesy whatsoever. Knowing this, the box office stops selling tickets as soon as there are only single seats left. Otherwise brawls would ensue.
At first, when the theater is pretty empty, there’s no problem. Every couple can find two adjacent seats. But after a while, the only seats left are singles—solitary, uninhabitable dead spaces that a couple can’t use. In real life, people often create these buffers deliberately, either for their coats or to avoid sharing an armrest with a repulsive stranger. In this model, however, these dead spaces just happen by chance.
The question is: When there’s no room left for any more couples, what fraction of the theater’s seats are unoccupied?
On Wed, Nov 28, 2012 at 12:42 PM, Allan Wechsler <acwacw@gmail.com> wrote:
Going back to trying to make sense of the 1D problem, the number of valid configurations for N people satisfies a[0]=a[1]=a[2]=1, a[n+3]=a[n]+a[n+1]. There are about half a dozen sequences in OEIS with this "tribonacci" rule, with minor differences in offset and initial conditions.
Let b[N] be the aggregate number of singletons in all valid N-person configurations. I'm getting a recurrence b[n+3] = a[n] + b[n] + b[n+1]. Now b[0] = 0, b[1] = 1, b[2] = 0, and then the recurrence gives 2, 3, 3, 6, 7, 10, 15, 19 ... The last entry diverges from A121833, but the rule is so simple that I can't believe it's not in OEIS, so I must have miscalculated.
Anyway, the wanted expected number of singletons is lim b[n]/a[n]. Peering at the small entries I realize I must have blundered somewhere. Can somebody with more attention to give it please repeat this reasoning but do it correctly?
On Wed, Nov 28, 2012 at 3:09 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Good point, but it wasn't intentional -- I was just careless.
So, I should've said "then restrict attention to only those outcomes satisfying the conditions of the problem: That each person holds at most one hand and no two singles are adjacent."
Or, put another way: After giving each pair of adjacent hands an independent ½ probability of holding each other, restrict attention to the configurations having a maximal set of adjacent pairs of gridpoints each connected by the line segment between them, such that no line segment touches another one.
(This almost suggests a way to obtain the results for 1D.)
--Dan
On 2012-11-28, at 11:44 AM, Andy Latto wrote:
On Wed, Nov 28, 2012 at 1:49 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Whether in the 1D or 2D grid case (or for that matter in nD), one way to give this problem well-defined probabilities (that I think is in some sense the most natural way) is to first give each pair of adjacent hands an independent probability of ½ as to whether they or not they hold each other -- and then restrict attention to only those outcomes satisfying the conditions of the problem: That each person holds at most one hand.
That's a different problem, because you're ignoring the second condition of the problem; no two adjacent single people. If you restrict attention to those, you have a formulation equivalent to Allan's, I think, but different from both of mine.
Andy
I'm not sure if this agrees with the probabilities in one of Andy's two methods.
The problem becomes more symmetrical if the 1D case is a circle instead of a line (and in nD a K^n grid on an n-dimensional torus)
--
but this won't affect the asymptotic expected fraction of singles.
--Dan
On 2012-11-28, at 6:49 AM, Andy Latto 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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Please forgive me if I didn't feel like reading a whole paper to find out what was meant, when the problem poster could have just told us the intended problem. --Dan On 2012-11-29, at 11:27 AM, Allan Wechsler wrote:
The PDF file Gary sent some of us explains this model carefully, and indeed, it resolves all the ambiguity in the original statement. In particular, it's different (at least on its face) from any of the interpretations Andy proposed in his first response. Furthermore, it definitely differs from my formulation, in which all the legal configurations are equally likely.
This difference is already present for N=4. There are two legal configurations. If we write a 0 for a pair of unjoined hands, and 1 for a pair of held hands, these two configurations can be written 101 and 010. In my formulation these two configurations are equally likely. One of them has two singletons and one has none, for an average of one singleton per trial. But in Strogatz's formulation, the first bond to settle in creates one of the three preliminary configurations, 100, 010, 001, with equal likelihood. 010 is saturated, but 100 and 001 both must progress to 101. So 101 is twice as likely to occur as 010, for an average of 2/3 singletons per trial.
At this point I'm perfectly ready to believe the e^(-2) result, and to agree that the 2-dimensional case is much, much harder to analyze. I wouldn't expect it to have a closed-form solution, but surely it's worth doing a big Monte Carlo trial on, say, a 100 by 100 grid, and feed the resulting average density to Simon's number recognizer.
On Thu, Nov 29, 2012 at 12:47 PM, Gary Antonick <gantonick@post.harvard.edu>wrote:
Andy, Allan, Dan -
As you noticed pretty quickly, I didn't state the problem correctly. Thanks for pointing out. I'm actually interested in sequential and not simultaneous seating.
The following is Strogatz' presentation from Joy of x. I'm wondering if a 2D version of this has been solved.
Imagine there’s a very popular new movie showing at the local theater. It’s a romantic comedy, and hundreds of couples (many more than the theater can accommodate) are lined up at the box office, desperate to get in. Once a lucky couple get their tickets, they scramble inside and choose two seats right next to each other. To keep things simple, let’s suppose they choose these seats at random, wherever there’s room. In other words, they don’t care whether they sit close to the screen or far away, on the aisle or in the middle of a row. As long as they’re together, side by side, they’re happy.
Also, let’s assume no couple will ever slide over to make room for another. Once a couple sits down, that’s it. No courtesy whatsoever. Knowing this, the box office stops selling tickets as soon as there are only single seats left. Otherwise brawls would ensue.
At first, when the theater is pretty empty, there’s no problem. Every couple can find two adjacent seats. But after a while, the only seats left are singles—solitary, uninhabitable dead spaces that a couple can’t use. In real life, people often create these buffers deliberately, either for their coats or to avoid sharing an armrest with a repulsive stranger. In this model, however, these dead spaces just happen by chance.
The question is: When there’s no room left for any more couples, what fraction of the theater’s seats are unoccupied?
On Wed, Nov 28, 2012 at 12:42 PM, Allan Wechsler <acwacw@gmail.com> wrote:
Going back to trying to make sense of the 1D problem, the number of valid configurations for N people satisfies a[0]=a[1]=a[2]=1, a[n+3]=a[n]+a[n+1]. There are about half a dozen sequences in OEIS with this "tribonacci" rule, with minor differences in offset and initial conditions.
Let b[N] be the aggregate number of singletons in all valid N-person configurations. I'm getting a recurrence b[n+3] = a[n] + b[n] + b[n+1]. Now b[0] = 0, b[1] = 1, b[2] = 0, and then the recurrence gives 2, 3, 3, 6, 7, 10, 15, 19 ... The last entry diverges from A121833, but the rule is so simple that I can't believe it's not in OEIS, so I must have miscalculated.
Anyway, the wanted expected number of singletons is lim b[n]/a[n]. Peering at the small entries I realize I must have blundered somewhere. Can somebody with more attention to give it please repeat this reasoning but do it correctly?
On Wed, Nov 28, 2012 at 3:09 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Good point, but it wasn't intentional -- I was just careless.
So, I should've said "then restrict attention to only those outcomes satisfying the conditions of the problem: That each person holds at most one hand and no two singles are adjacent."
Or, put another way: After giving each pair of adjacent hands an independent ½ probability of holding each other, restrict attention to the configurations having a maximal set of adjacent pairs of gridpoints each connected by the line segment between them, such that no line segment touches another one.
(This almost suggests a way to obtain the results for 1D.)
--Dan
On 2012-11-28, at 11:44 AM, Andy Latto wrote:
On Wed, Nov 28, 2012 at 1:49 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Whether in the 1D or 2D grid case (or for that matter in nD), one way to give this problem well-defined probabilities (that I think is in some sense the most natural way) is to first give each pair of adjacent hands an independent probability of ½ as to whether they or not they hold each other -- and then restrict attention to only those outcomes satisfying the conditions of the problem: That each person holds at most one hand.
That's a different problem, because you're ignoring the second condition of the problem; no two adjacent single people. If you restrict attention to those, you have a formulation equivalent to Allan's, I think, but different from both of mine.
Andy
I'm not sure if this agrees with the probabilities in one of Andy's two methods.
The problem becomes more symmetrical if the 1D case is a circle instead of a line (and in nD a K^n grid on an n-dimensional torus)
--
but this won't affect the asymptotic expected fraction of singles.
--Dan
On 2012-11-28, at 6:49 AM, Andy Latto 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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Allan Wechsler -
Andy Latto -
Dan Asimov -
Gary Antonick