Derangements: A Riddle About Misallocated Hats

2 January 2019

Shiri Avni

    Table of Contents:

This post is aimed at showing non-programmers or novice progammers how knowing a little bid of code can help you tackle interesting riddles.

Riddle Overview

There is a classic hats riddle that goes like this:

people attend a party, and they each bring a single hat with them. When they enter the party, they leave their hat at the reception. At the end of the party, the guests go to pick up their hats, but the receptionist was tired/drunk/mischievous and gave each person a random hat instead. What is the probability that none of the guests receive their original hat back?

Take a moment to try to think of the answer. To illustrate the dependencies of the probabilities between guests, let’s consider a small party with guests Anna, Bob, Carla, and Dan ().

Let’s assume that Anna picks up a hat from the reception first. The probability that Anna does not receive her original hat is , which in this case is . Let’s say that Anna receives Bob’s hat, so the hats left at the reception are now Anna’s, Carla’s, and Dan’s.

If Bob is the second guest to pick up a hat, then the probability that Bob does not receive his original hat is , because all the remaining hats at the reception are not his. On the other hand, if Carla is the second person to pick up a hat, then since Bob’s hat is already taken, then Carla only has a chance of picking a hat that is not hers. So as we an see, there are dependencies between the guests and this complicates the solution.

Analytic Solution

The combinatorial solution to this problem is interesting, and you are welcome to read up on it here. The striking result is that as , the probability that no person receives his/her own back approaches a constant value of . This is not at all obvious, and I would have initially guessed that the final expression for this probability involves in such a way that it cannot be factored out.

Simulation

What I would like to do in the rest of this post is illustrate how coding can quickly help you approach problems such as these even if you don’t know the necessary math to solve the problem directly. Namely, we will take a “large” value of and simulate the reception problem times. By keeping track of how many times we obtain a valid solution (in which no guest receives his/her own hat), we can approximate the probability as .

From this point onwards, I will assume that you are familiar with basic Python and NumPy arrays.

We will label the guests and create an array such that if the -th guest receives the -th’s guest’s hat in return. In this way, valid solutions are those such that for all .

import numpy as np

num_guests = 10000
num_trials = 10000

num_successful_trials = 0
helper_arr = np.arange(num_guests) #in this array, a[i]=i for all i

for i in range(num_trials):
    trial = np.random.permutation(num_guests)
    if np.sum(helper_arr == trial) == 0: #no guest receives hat back
        num_successful_trials+=1

probability = round(num_successful_trials/num_trials, 5) #round to 5 digits
print("Probability: ", probability)

The probability value we get changes between runs, but the value satisfies for all the runs I tried. Considering that , we’re quite close!

Conclusion

In many cases, simulating mathematical models can help you get some intuition about the qualities of a solution. In our case here, changing the code’s parameters to larger values of (e.g. 50,000) still results in similar probabilities, which provides evidence for the limiting probability not being dependent on at all.

In other cases in which you may have come up with a numeric formula for a problem, simulating the models can help you check that you didn’t make an error in deriving your formula - as the simulation should give you approximately the same value as that predicted by the formula you derived.

Relevant Posts:

Using Code to Sift Through Your Facebook History