Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
I've not heard a name for such problems, but the permutations involved (ones with no fixed point) are called derangements. –  Chris Eagle Nov 28 '11 at 22:12
1  
Envelope matching problem ? BTW, the title made me laugh, +1 for that. –  Sasha Nov 28 '11 at 22:13

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.