Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Assume that there are n snakes. Any 2 ends (tail or head) of the "2n" available have to be picked up and tied together and this process has to be repeated infinitely.

If p/q (gcd(p,q) = 1) is the probability of you getting a single long “snake” in the end, what would be the sum of (p+q) for all 2 <= n <= 40?

share|improve this question
    
Did you mean "this process has to be repeated n-1 times" instead of infinitely? And do you only pick up loose ends, not already tied ends? –  comonad Jan 28 '11 at 12:56
    
@comonad: Usually when this problem is posed, you only pick up loose ends. You are right you stop when you run out of ends. –  Ross Millikan Jan 28 '11 at 17:19

1 Answer 1

Hint:Let P(n) be the probability of making one loop from n snakes. When you pick up two ends, they might come from the same snake (in which case you fail immediately) or they don't (in which case you tie them together and have n-1 snakes). So you should be able to make a recurrence expressing P(n) in terms of P(n-1). And P(1)=1-you will always succeed with a single snake.

Added: with two snakes, the chance of success is $\frac{2}{3}$ as you just have to avoid the other end of the first snake you pick up. For three, the chance of avoiding failure the first time is $\frac{4}{5}$ and of overall success is $\frac{2\cdot 4}{3\cdot 5}$. For $n$ snakes it is $\frac {2^{n-1}(n-1)!}{(2n-1)!!}$ where the two exclamation points are the double factorial-the product of all odd numbers up to $2n-1$.

share|improve this answer
1  
I'm curious why the downvote? –  Ross Millikan Jan 28 '11 at 14:44
    
So we know the rational number $p_n/q_n$ for every $n$. But the question involves the integers $p_n+q_n$, or at least their sum over every $n\le 40$... (And I did not downvote your answer.) –  Did Feb 27 '11 at 20:02
    
@Didier: Then you just have to reduce the fraction to lowest terms. I don't have a closed form for that, but for only 40 cases it wouldn't be hard. It is "left as an exercise" –  Ross Millikan Feb 27 '11 at 20:14
    
I'm guessing (although I'm not totally sure) that the fact that the problem is phrased in this strange way -- adding the numerators and denominators -- is purely to force an integer answer that can be checked automatically. –  Michael Lugo Feb 27 '11 at 20:31
    
@Michael: I think so. I suspect all the odd factors of the numerator divide out, but am not sure. But even 79!! calls for either high precision or clever programming not to overflow. –  Ross Millikan Feb 28 '11 at 1:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.