Secret Santa: A Probabilistic Approach to Gift Giving

Welcome to the first email in the Logic Lounge newsletter series.

Every weekday, I’ll send a problem like the one below straight to your inbox at 7 am PST. When you solve it, please email your solution to [email protected]. Each problem that you solve gains you one point on our GitHub leaderboard (with potential for prizes in the future). Submissions close the next day at 6:59 am PST.

Without further ado, here’s today’s problem:

Dr. Rational is hosting a Secret Santa party for 10 friends. Each partygoer is randomly assigned another partygoer to secretly give a gift to. When it's gift-giving time, Dr. Rational starts the cycle by sitting in a large sofa. His gift-giver, Captain Clarity, places the gift behind Dr. Rational. Once Dr. Rational correctly guesses that Captain Clarity gave the gift, it's Captain Clarity's turn.

Starting from Dr. Rational, what is the probability that traversing down the chain of gift recipients will mean each partygoer receives a gift and Dr. Rational is the last person to give a gift? What would the probability be for N friends?

Hint: think of it like a directed graph, as seen below

Again, please submit your answers as a proper fraction to [email protected].

Happy solving,

Angad Singh