Unmasking the Secret Santas

This Riddler puzzle is about the popular Secret Santa gift exchange game. Can we guess who our Secret Santa is?

The 41 FiveThirtyEight staff members have decided to send gifts to each other as part of a Secret Santa program. Each person is randomly assigned one of the other 40 people on the masthead to give a gift to, and they can’t give to themselves. After the Secret Santa is over, everybody naturally wants to find out who gave them their gift. So, each of them decides to ask up to 20 people who they were a Secret Santa for. If they can’t find the person who gave them the gift within 20 tries, they give up. (Twenty co-workers is a lot of co-workers to talk to, after all.) Each person asks and answers individually — they don’t tell who anyone else’s Secret Santa is. Also, nobody asks any question other than “Who were you Secret Santa for?”

If each person asks questions optimally, giving themselves the best chance to unmask their Secret Santa, what is the probability that everyone finds out who their Secret Santa was? And what is this optimal strategy? (Asking randomly won’t work, because only half the people will find their Secret Santa that way on average, and there’s about a 1-in-2 trillion chance that everyone will know.)

Here is my solution:
[Show Solution]

14 thoughts on “Unmasking the Secret Santas”

  1. Nice job, however I get:
    For n=1, P=0, and for n=2, P=5/11. I didn’t check the others.
    Are you using D(0)=1?

    1. You’re absolutely right. I used D(0)=0 by accident. I updated my post and plot. I decided to keep P=1 for the cases n=1 and n=2 because you can deduce your Secret Santa perfectly in these cases even if you don’t ask the correct co-worker (see my explanation in the updated post).

  2. I think your evaluation is missing the k=2n+1 term. n=2 should still evaluate to 100%, as link length of 5 is fully determined from first 3 permutations.

  3. It seems that you have solved a different problem than asked, though likely the one that was intended.

    “If each person asks questions optimally, giving themselves the best chance to unmask their Secret Santa…” (the original problem) is not the same as, “If each person asks questions optimally, so as to give the entire group the best chance to unmask all of the Secret Santas…” (the question you answered).

    To find our own Secret Santa we can do better than guessing randomly… proving we have an optimal strategy is difficult, however.

    – JZGYK

    1. I agree — since we were asked about the probability that everybody wins, I was assuming this was the quantity to be maximized.

      If we interpret the question literally and each individual greedily attempts to maximize the chance that they will find their own Secret Santa, I don’t think you can do any better than guessing randomly (assuming $n > 2$). If you think it’s possible to do better than randomly guessing, I’d love to hear your thoughts!

      This is another reason I interpreted the question the way I did; because the literal interpretation, as far as I could tell, led to random guessing as the only possible choice and this isn’t an interesting scenario!

      1. If you use the “follow the Santa” strategy, there is a 31.8% chance that everybody finds their Secret Santa, but there is actually a 48.8% chance that any one individual will find their Secret Santa. Therefore this strategy doesn’t beat random guessing, where the chance of winning is 50% for each individual. I think I’ll update my solution and include some of these comments.

        1. There is another interpretation that leads to a perfect (but clearly unintended) strategy. Even though nobody can share the results of their questioning, if everyone in the office conspires to ask exactly one question, (and they each ask their own target), then by the end of the day each person will know who their secret Santa is because their secret Santa was the only one to ask them anything.

      2. I came to the same results as everyone else: 31.8% for everybody using “Follow The Santa [FTS]”, 48.8% for me individually if I use FTS and 50% if I “guess randomly”. I note here that I only count a “win” if someone actually says, “I am your Secret Santa.”; there is always the possibility of guessing correctly if no one names me.

        What struck me as odd about this was: “If I am guessing randomly, I might Follow The Santa by pure chance.” But this would give me a less than the 50% chance of winning that I would get if I guessed randomly. So what if I guess randomly but re-guess if I FTS? By throwing out the “bad” (less than 50%) approach of FTS, what is left must be something greater than 50%.

        An example:
        n = 3 is the first interesting case so let’s start there. There are 1854 derangements and the individual finds their Secret Santa 774/1854 = 41.75% of the time.

        Consider an anti-Follow The Santa strategy ([aFTS]). We are player #1 and we ask the lowest numbered player who has not yet been named. That is, if we were the Secret Santa for player #4 then the lowest numbered player who has not yet been named is player #2 and we ask them who they bought for. If they say player #3 then we have named players #1, #2, #3, and #4 so the lowest numbered player who has not yet been named is #5, etc..

        After 1 question, 3-FTS has 264 winning cases, 3-Rnd has 309 and 3-aFTS has 318.
        After 2 questions, 3-FTS has 534 winning cases, 3-Rnd has 618 and 3-aFTS has 654.
        After 3 questions, 3-FTS has 774 winning cases, 3-Rnd has 927 and 3-aFTS has 1038.

        Assuming I have made no mistakes, 3-FTS = 41.8%, 3-Rnd = 50.0% and 3-aFTS = 56.0%

        Proving that this is the optimal individual strategy is another thing entirely.

        – JZGYK

        On an unrelated note, whenever I try to use the less than or greater than symbols, your site misinterprets them.

        1. ah neat — I guess I was assuming the staff members weren’t allowed to cooperate ahead of time (by agreeing on a specific ordering, for example). Looks like this sort of cooperation can lead to better-than-guessing strategies, as you pointed out!

          Math symbols (and arbitrary equations, in general) can be displayed by using a dollar sign before and after the equation (LaTeX code). I think the issue with $<$ and $>$ is that these symbols are interpreted as html tags.

          1. No collusion is required and I can get this result as the sole Santa-seeker. The results are unchanged if I make a list or if I simply choose randomly from people who are not named. But I don’t know that this is optimal in general, or even close.

            – JZGYK

  4. Nice writeup!

    If you want to avoid using enormous numbers (say, because you are using a spreadsheet for the computations, or any finite-precision language), the number of derangements with a cycle of length $k>n/2$, $\binom{n}{k} (k-1)! D_{n-k}$, can be rewritten as $n!\frac{(k-1)!}{k!}\frac{D_{n-k}}{(n-k)!}=\frac{n!}{k}\frac{D_{n-k}}{(n-k)!}$, and the proportion of such derangements out of all possible derangements of size $n$ is $\frac{1}{k}\frac{n!}{D_n}\frac{D_{n-k}}{(n-k)!}$. So, the proportion of derangements on 41 items with a cycle of length (exactly) 22 is $\frac{1}{22} \frac{41!}{D_{41}} \frac{D_{19}}{19!} \approx 0.045455$.

    The function $\frac{D_n}{n!}$ converges to $1/e$ quickly. The exact formula is $\frac{D_n}{n!} = \sum_{i=0}^n \frac{(-1)^i}{i!}$, and, if we accept the approximation $\frac{41!}{D_{41}} = e$ (the difference is far below machine precision), we can sum up the contributions of each of the different cycle lengths for $k=22,\ldots,41$ and get that the total proportion of derangements with a cycle of length at least 22 is approximately $0.681665$. Therefore, the probability that our strategy succeeds is approximately $0.318335$, which matches your approximation to the exact ratio you found.

Leave a Reply

Your email address will not be published. Required fields are marked *