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

  • 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