Dynamic Programming in the Hat Check Puzzle

Problem Introduction

Imagine this: You and three friends attend a fancy party. Everyone checks their hats with an attendant. As the party ends, you all rush to leave. The attendant, having lost all the claim tickets, randomly returns hats to the four of you.

What is the probability that absolutely no one receives their own hat? What if there were 10 people? 100 people? This is the famous hat check problem (also known as the problème des rencontres).

The puzzle has surprised mathematicians for centuries because the probability converges to a specific constant—approximately 36.8%—regardless of how many people attend.

Why It Matters

The hat check problem appears in:

• Quantitative finance interviews: Hedge funds use this to test probability reasoning

• Cryptography: Understanding derangements helps analyze permutation-based ciphers

• Randomized algorithm testing: Verifying that shuffling algorithms produce uniformly random permutations

• Looking to step up your coding interview prep? Check out our Tutoring Page for personalized 1-on-1 coaching.

Step-by-Step Breakdown

Step 1: Understanding the Problem as a Probability

Let H(N) be the number of ways to return hats so no one gets their own hat. The total number of ways to return hats (without restrictions) is N! (N factorial).

Therefore, the probability P(N) that no one gets their own hat is:

P(N) = H(N) / N!

Our job is to compute H(N) efficiently, then calculate the probability.

Step 2: Visualizing with a Small Example

This diagram shows the branching nature. Hat 1 can go to any of the other 3 people. The path then branches based on where Hat 2 goes.

Step 3: Establishing Base Cases

Let's manually compute small values to build intuition:

N = 1: One person, one hat. The only possible return gives the person their own hat. No valid returns. H(1) = 0. Probability = 0/1 = 0.

N = 2: Two people (A and B), two hats (a and b). Valid returns: A gets b, B gets a. One valid arrangement. H(2) = 1. Probability = 1/2 = 0.5.

N = 3: List all 6 permutations of [A,B,C] with hats [a,b,c]:

• [a,b,c] → all correct (invalid)

• [a,c,b] → A correct (invalid)

• [b,a,c] → C correct (invalid)

• [b,c,a] → no one correct (valid)

• [c,a,b] → no one correct (valid)

• [c,b,a] → B correct (invalid)

H(3) = 2. Probability = 2/6 ≈ 0.3333.

N = 4: Without listing all 24 permutations, we can compute H(4) = 9. Probability = 9/24 = 0.375.

Notice the probabilities: 0, 0.5, 0.333, 0.375. They seem to converge around 0.3679.

Step 4: Deriving the Recurrence Relation

Let H(N) be the number of hat returns with no fixed points.

Step 1: Where does Hat 1 go? Hat 1 belongs to Person 1. It cannot go to Person 1. So it goes to Person k, where k ∈ {2, 3, ..., N}. That's (N - 1) possibilities.

Step 2: Where does Hat k go? Now consider Hat k (the hat belonging to Person k). Two scenarios:

Scenario A: Hat k goes to Person 1

• Hat 1 is with Person k, Hat k is with Person 1

• These two hats have been swapped

• The remaining (N - 2) hats must be returned to their owners with no one getting their own hat

• Number of ways: H(N - 2)

Scenario B: Hat k does NOT go to Person 1

• Hat 1 is with Person k

• Hat k must go to someone else (not Person 1)

• This effectively creates a derangement problem for the remaining (N - 1) hats, where Hat k cannot go to Person 1

• Number of ways: H(N - 1)

Step 3: Combine
For each of the (N - 1) choices for where Hat 1 goes, we have H(N - 1) + H(N - 2) arrangements for the remaining hats.

H(N) = (N - 1) × [H(N - 1) + H(N - 2)]

Check against our manual calculations:

• H(3) = 2 × (H(2) + H(1)) = 2 × (1 + 0) = 2 ✓

• H(4) = 3 × (H(3) + H(2)) = 3 × (2 + 1) = 9 ✓

Step 5: Naive Recursive Implementation

def hat_check_recursive(n: int) -> int:
    """
    Naive recursive solution for the hat check problem.
    
    Time: O(2^n) - Exponential
    Space: O(n) - Recursion stack
    
    This works for n <= 30 but becomes impractical beyond that.
    """
    if n == 1:
        return 0
    if n == 2:
        return 1
    
    return (n - 1) * (hat_check_recursive(n - 1) + 
                      hat_check_recursive(n - 2))

def hat_check_probability_recursive(n: int) -> float:
    """Calculate probability using the recursive method."""
    from math import factorial
    return hat_check_recursive(n) / factorial(n)

print(f"P(5) = {hat_check_probability_recursive(5):.6f}")  # 0.366667

The problem: The recursive tree for H(40) would have approximately 2^40 ≈ 1 trillion nodes. Impossible.

Step 6: Top-Down DP with Memoization

def hat_check_top_down(n: int, memo: dict = None) -> int:
    """
    Top-down dynamic programming with memoization.
    
    Time: O(n)
    Space: O(n) - Memo dictionary + recursion stack
    """
    if memo is None:
        memo = {}
    
    if n == 1:
        return 0
    if n == 2:
        return 1
    if n in memo:
        return memo[n]
    
    memo[n] = (n - 1) * (hat_check_top_down(n - 1, memo) + 
                         hat_check_top_down(n - 2, memo))
    return memo[n]

def analyze_hat_check(n: int) -> None:
    """Analyze the hat check problem for n people."""
    arrangements = hat_check_top_down(n)
    total = math.factorial(n)
    probability = arrangements / total
    
    print(f"N = {n}")
    print(f"Valid arrangements: {arrangements:,}")
    print(f"Total arrangements: {total:,}")
    print(f"Probability: {probability:.6f}")
    print(f"1/e: {1/math.e:.6f}")
    print("---")

# Example
analyze_hat_check(10)
# Output: Valid arrangements: 1,334,961
# Probability: 0.367879
# 1/e: 0.367879

Observation: By N = 10, the probability matches 1/e to 6 decimal places.

Step 7: Bottom-Up DP with Tabulation

def hat_check_bottom_up(n: int) -> int:
    """
    Bottom-up dynamic programming using tabulation.
    
    Time: O(n)
    Space: O(n) - Full DP array
    
    This approach is more efficient than top-down for very large n
    because it avoids recursion overhead.
    """
    if n == 1:
        return 0
    if n == 2:
        return 1
    
    dp = [0] * (n + 1)
    dp[1] = 0
    dp[2] = 1
    
    for i in range(3, n + 1):
        dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2])
    
    return dp[n]

Why tabulation is useful: The iterative structure allows us to easily observe the convergence of H(N)/N! to 1/e. We can also compute probabilities for much larger N without recursion limits.

Step 8: Space-Optimized Solution

def hat_check_optimized(n: int) -> int:
    """
    Space-optimized bottom-up solution.
    
    Time: O(n)
    Space: O(1) - Only two variables
    
    This is the optimal solution for exact counting.
    """
    if n == 1:
        return 0
    if n == 2:
        return 1
    
    prev2 = 0  # H(1)
    prev1 = 1  # H(2)
    
    for i in range(3, n + 1):
        current = (i - 1) * (prev1 + prev2)
        prev2 = prev1
        prev1 = current
    
    return prev1

def hat_check_probability_optimized(n: int) -> float:
    """Calculate probability using optimized method."""
    from math import factorial
    return hat_check_optimized(n) / factorial(n)

# Demonstrate convergence
for n in [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20]:
    prob = hat_check_probability_optimized(n)
    print(f"N={n:2d}: P = {prob:.8f} | Difference from 1/e = {abs(prob - 1/math.e):.8f}")

Output:

N= 1: P = 0.00000000 | Difference = 0.36787944
N= 2: P = 0.50000000 | Difference = 0.13212056
N= 3: P = 0.33333333 | Difference = 0.03454611
N= 4: P = 0.37500000 | Difference = 0.00712056
N= 5: P = 0.36666667 | Difference = 0.00121277
N= 6: P = 0.36805556 | Difference = 0.00017612
N= 7: P = 0.36785714 | Difference = 0.00002230
N= 8: P = 0.36788194 | Difference = 0.00000250
N= 9: P = 0.36787919 | Difference = 0.00000025
N=10: P = 0.36787946 | Difference = 0.00000002

Ready to crush your next technical interview?
Visit our Order Page now to grab our exclusive Dynamic Programming bootcamp courses!

Common Mistakes

Mistake 1: Treating the Hat Check as a Standard Probability Problem

Many beginners assume all permutations are equally likely to be derangements. While true, they then incorrectly compute probabilities using approximations without understanding the exact count.

Mistake 2: Forgetting That H(1) = 0

A surprising number of people think H(1) = 1. But with one person and one hat, the only possible return gives the person their own hat. That's not a valid derangement.

Mistake 3: Assuming Independence

Some try to compute the probability as product of individual probabilities: (N-1)/N × (N-2)/(N-1) × ... This gives 1/N, which is wrong. Events are not independent.

Mistake 4: Using Floating-Point for Large N

When computing H(N) / N! for large N, both numbers become astronomically large. H(100) has about 158 digits. Use Python's decimal module or compute the probability via the inclusion-exclusion formula:

P(N) = Σ_{k=0 to N} (-1)^k / k!

Frequently Asked Questions

Q1: Does the hat check probability always approach 1/e from alternating sides?

A: Yes. For odd N, the probability is slightly below 1/e. For even N, slightly above 1/e. This alternating convergence is a property of the inclusion-exclusion series.

Q2: How is the hat check problem used in finance interviews?

A: Interviewers use it to test: (1) ability to set up recurrence relations, (2) understanding of dynamic programming, and (3) knowledge of probability convergence. It's a medium-difficulty problem that separates candidates.

Q3: Can the hat check problem be solved with a closed formula?

A: Yes. The number of derangements is given by: !N = N! × Σ_{k=0 to N} ((-1)^k / k!). This is known as the subfactorial formula.

Q4: Why does the attendant losing tickets make this a derangement problem?

A: Without tickets, the attendant returns hats randomly. Each return permutation is equally likely. We want permutations with zero fixed points—that's a derangement.

Conclusion

The hat check puzzle beautifully illustrates how a simple probability question leads to deep combinatorial mathematics. You've seen how the recurrence H(N) = (N-1) × (H(N-1) + H(N-2)) emerges from logical reasoning about swaps and derangements.

More importantly, you've learned that the probability converges to 1/e ≈ 36.79% for any reasonably large group. This constant appears throughout mathematics—in the hat check problem, in the number of permutations with no fixed points, and in the expected number of fixed points in a random permutation.

The dynamic programming techniques you've practiced here—top-down memoization, bottom-up tabulation, and space optimization—are transferable to countless other problems. 

Keep this hat check solution in your toolkit for your next interview.

Take Your Skills to the Next Level!

Want to master Advanced Dynamic Programming alongside FAANG engineers? Our platform has everything you need.

👉 Visit Our Tutoring Page  to book a session today.

👉 Check Our Order Page  for direct access to our full DP coursework!

 

Explore more articles

• Counting Derangements: Main Guide

• Solving the Secret Santa Problem

• Exam Seating Rearrangements using DP