Puzzles

Math puzzle: A Loopy Holiday Gift Exchange

By Zach Wissner-Gross

You are participating in a holiday gift exchange with a few 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.

  1. If there are a total of three students in the class, how likely is it that they form a single loop that includes the entire class (that is, a loop of length three)?
  2. If there are a total of four students in the class, how likely is it that they form a single loop that includes the entire class?
  3. 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?
  4. 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?

Looking for answers? Go to sciencenews.org/puzzle-answers. We’d love to hear your thoughts. Email us at puzzles@sciencenews.org.