In the Math Corner of my December Diary I borrowed another one of Dr Peter Winkler's, a culinary one. This is from back in July. You can sign up for a weekly brainteaser from Dr Winkler at mindbenders.momath.org.
The 100 ends of 50 strands of cooked spaghetti are paired at random and tied together. How many pasta loops should you expect to result from this process, on average?
The key here is to recognize that you start with 100 spaghetti-ends and each tying operation reduces the number of spaghetti-ends by two. The operation results in a new loop only if the first end you pick up is matched to the other end of the same strand.
At step k there are 100 − 2(k−1) ends, thus 100 − 2(k−1) − 1 = 101 − 2k other ends you could tie any given end to.
In other words, there are 101 − 2k choices of which only one makes a loop; the others just make two strands into one longer one.
It follows that the probability of forming a loop at step k is 1/(101 − 2k).
If X(k) is the number of loops (one or zero) formed at step k, then the expected (that is, average) value of X(k) is 1/(101 − 2k).
Since the final number of loops is X(1) + … + X(50) we conclude that on the average the final loop count is
1/99 + 1/97 + 1/95 + … + 1/3 + 1/1, which is about 2.93777485; less than three loops!