This week the #puzzle is: A Loopy Holiday Gift Exchange #probabilities #coding #montecarlo #combinatorics

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?

And for extra credit:

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

A Loopy Holiday Gift Exchange

Intermission

Oh, look at that, we have a repeat.

Highlight to reveal (possibly incorrect) solution:

Program

My thoughts:

• If we had no bounds, there would be 5! = 120 ways to distribute the names.
• The 1st bound is, that permutations where a person draws their own name are discarded. This also means the surviving permutations have no cycles of length 1. (Terminology and example calculations: Wikipedia .)
• The 2nd bound is, that we want to compare permutations with a cycle of length 5 to those without, to calculate a probability.
• How many permutations without cycles of length 1?
  • A permutation like that might consist of 2 cycles, 1 of length 2, 1 of length 3.
    • There are C(5,2) * 1! * 2! ways this can be done.
    • C(5,2) different ways to choose the 2 names for the 2 cycle.
    • 1! = 1 way to permutate them, so that no person draws their own name.
    • The remaining names can be permutated in 2! = 2 ways.
    • C(5,2) * 1! * 2!
    • = 5*4/2*1 * 1 * 2
    • = 10 * 2
    • = 20
  • The bound means no cycle of length 4, because then the other cycle would have length 1.
  • A valid permutation might have a cycle of length 5.
    • There are C(5,5) * 4! ways this can be done.
    • C(5,5) = 1 — we have to choose all the names.
    • 4! = 24 ways to permutate these names, without a person drawing their own name.
  • In all 20 + 24 = 44 ways to permutate the names, and 24 ways to achieve a 5 cycle.
  • 24/44 = 0.545454545.

A monte carlo program roughly confirms this number.

And for extra credit:

Desmos

I expand the program to look at other N’s. An analysis in Desmos suggests, that the formula should be 2.75 * N^-1. If N = 5, this is 0.55. (Might 2.75 actually be e = 2.72? Hard to tell.)