Snakes and Probabilistic Enigma 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?

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