3
$\begingroup$

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?

  • 0
    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?2011-01-28
  • 0
    @comonad: Usually when this problem is posed, you only pick up loose ends. You are right you stop when you run out of ends.2011-01-28

1 Answers 1

2

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$.

  • 1
    I'm curious why the downvote?2011-01-28
  • 0
    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.)2011-02-27
  • 0
    @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"2011-02-27
  • 0
    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.2011-02-27
  • 0
    @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.2011-02-28