This week’s puzzle is another collaboration between Fiddler on the Proof and Science News, where four math puzzles that are related were posted earlier this morning. The third and fourth among these are also appearing here as this week’s Fiddler and Extra Credit. Now—on to those puzzles!
You are participating in a holiday gift exchange with your classmates. You each write down your own name on a slip of paper and fold it up. Then, all the students place their names into a single hat. Next, students pull a random name from the hat, one at a time. If at any point someone pulls their own name from the hat, the whole class starts over, with everyone returning the names to the hat.
Once the whole process is complete, each student purchases a gift for the classmate whose name they pulled. Gifts are handed out at a big holiday party at the end of the year.
At this party, you observe that there are “loops” of gift-giving within the class. For example, student A might have gotten a gift for B, who got a gift for C, who got a gift for D, who got a gift for A. In this case, A, B, C and D would form a loop of length four. Another way to have a loop of length four is if student A got a gift for C, who got a gift for B, who got a gift for D, who got a gift for A. And of course, there are other ways.
If there are a total of five students in the class, how likely is it that they form a single loop that includes the entire class?
The number of derrangements, that is, the permutations of $N$ items where none of them are in the correct location converges very quickly to $\frac{N!}{e}$.
For $N=5$, there are $44$ derrangements.
For the loops, $A$ cannot be first. And WLOG, every other student will receive a gift from A the same number of times in the solution set.
If there are N students in the class, where N is some large number, how likely is it that they form a single loop that includes the entire class, in terms of N? (For full credit, your answer should be proportional to N raised to some negative power.)
The numerator seems to be $(N-1)!$, as the first can gift anyone but themself, the second can gift anyone but themself and the first, etc.
The denominator was noted above!