4
$\begingroup$

In one of my math courses in university, we studied a problem where a number of people show up to a party, wearing hats. Each left with the wrong hat. I am pretty sure that there was some specific name for this problem.

What is the problem called? I would like to use this to calculate some Secret Santa matchings, so that nobody gets matched with themselves.

  • 1
    [Envelope matching problem](http://forums.oreilly.com/topic/2590-classic-envelope-matching-problem/) ? BTW, the title made me laugh, +1 for that.2011-11-28

2 Answers 2

4

This sounds like the problème des rencontres or the derangement problem:

How many permutations $\pi\in\mathfrak{S}_n$ have no fixed points, that is, $\pi(i)\ne i$ for all $i\in [n]$?

I've also heard it called the hat-check problem.

The above quotation is from Richard Stanley, Enumerative combinatorics 1, p. 67. He analyzes the problem using the principle of inclusion and exclusion and attributes its first solution to Montmort.

2

D.J.S. Robinson calls one such problem the hat problem.