Strings and knots
A friend of mine at work recently asked me the following problem, which was supposedly given as an interview question (not at my company):
Suppose n strings (physical strings, not character arrays!) are placed in a bowl so that we only see the ends of each string, and do not know which ends belong to the same string. Next we proceed by picking two ends at random and tying them together, and continue to do so until all the ends are tied. On average, how many loops will you end up with?
As an example of how it might work: if n=2, then there are 4 string ends left hanging out of the bowl. When we pick the first two ends and tie them together, either we are making a loop out of a single string, or we are tying two different strings together. Next we tie the last ends together (there are only two ends left so there is no choice). If our first knot was a self-knot that made a loop out of a single string, then there will end up being two loops in total. But if our first knot was between two different strings, then the remaining ends joined will result in a single long loop containing both strings. So the average in this case is somewhere between 1 and 2 (it's a fraction).
I will not give away the answer just yet! If anyone would like to know, just post a comment, and I'll put it up.
Update: I've written up the answer. If you've thought at least a little bit about the problem, then you have permission to check out the answer :)
Suppose n strings (physical strings, not character arrays!) are placed in a bowl so that we only see the ends of each string, and do not know which ends belong to the same string. Next we proceed by picking two ends at random and tying them together, and continue to do so until all the ends are tied. On average, how many loops will you end up with?
As an example of how it might work: if n=2, then there are 4 string ends left hanging out of the bowl. When we pick the first two ends and tie them together, either we are making a loop out of a single string, or we are tying two different strings together. Next we tie the last ends together (there are only two ends left so there is no choice). If our first knot was a self-knot that made a loop out of a single string, then there will end up being two loops in total. But if our first knot was between two different strings, then the remaining ends joined will result in a single long loop containing both strings. So the average in this case is somewhere between 1 and 2 (it's a fraction).
I will not give away the answer just yet! If anyone would like to know, just post a comment, and I'll put it up.
Update: I've written up the answer. If you've thought at least a little bit about the problem, then you have permission to check out the answer :)
posted by Tyler | 11:54 PM
6 Comments:
So let me see,
The probability of tying the first string to itself would be 1/(2n-1) and the probability of tying it to one of the other strings would be (2n-2)/(2n-1). Where n is the number of strings.
So then the probability for the next attachment would be 1/(2s-3) to complete a loop and (2s-4)/(2s-3) that you would not complete it, and then so on n number of times where the last one would be 1/(2n-(2n-1)) and (2n-2n)/(2n-(2n-1)) or, 1 and 0.
After all, you must end with at least one loop in the end.
But I have this thought in my head that says, well if n is infinitely big, then the probability of ever tying any string to itself drops to the asymptotic 0, (sort of like the probability in going any one direction in a circle) and so you theoretically would never attach one string to itself, and so you would have only one loop.
I haven't had a math class in a while, so I have no idea if there were huge flaws in my thinking. What is the right answer?
I changed n to s, because of I was thinking of strings. =]
I know in my comment that I did not take into account if n was a smaller number, but I just thought about it and remembered that you said that for n=2 that it was a fraction between 1 and 2, and then since I had just decided, as n approaches infinity, it goes to 1, would that mean that the probability, on average, as n got bigger and bigger would drop down to the asymptote (being 1)?
hmmm....I don't think I really took into account the probability that the next strings had already been tied to one of the previous ones....hmmm...I think that would change it...but then that would lower the chances of making a loop even more...
(was just thinking about it again)
That's a stupid question! Just pour some meat sauce over it and eat the damn spaghetti!
Hey, Tyler. What's up? It looks like you found a job with Google. Congrats! That's awesome. If you make it out to the Left Coast for a Google conference or something, let me know.
Hey there, anonymous and osuprg! Anonymous, you came very close to the solution in your first comment, but you didn't quite give a finished answer. In any instance of this problem, n is always finite, so you should really solidify any formula you look at before taking the asymptotics. In other words, be careful about taking limits too soon!
osuprg, excellent solution ;) I think I have managed to track down your email and I'll be sending you a message shortly!
Everybody, if you've thought about this problem a little bit, then you've earned a look at the answer!
Post a Comment
<< Home