Puzzle - Drunk guests at a convention I am trying to solve Question 1.31 from "Heard on the Street":
$N$ guests are invited to a convention in a hotel, and each of them is assigned a room. Later on, they attend a dinner leaving their keys at the reception, and get drunk. When the dinner is over, the reception returns to each of them a randomly chosen key. What is the probability that at least one guest gets back her previously assigned key?
I came up with a solution but it is wrong. I call $X$ the number of guests who get back their own key. I let
$$
P(X\geq1)=1-P(X=0),
$$
and compute $P(X=0)$ as the number of ways to wrongly assign the keys $(n-1)!$ over the total number of possible distributions of the keys $n!$. 
Finally i get:
$$
P(X\geq1)=1-P(X=0)=1-\frac{(n-1)!}{n!}=1-\frac 1N.
$$
I cannot understand why it is wrong. Would you please tell me where I am messing up?
 A: Thinking from first principles: you begin with $n$ guests and $n$ possible keys. Pick the first guest; the probability of giving him a wrong key is $\frac{n-1}{n}$. You do so, and this leaves $n-1$ guests and $n-1$ keys, but beware! One of those guests can never get his key back, because the key has gone with the first guess. If we make him the second guest, he gets a wrong key with probability $1$, not $\frac{n-2}{n-1}$ which is the implicit assumption you are making.
Things complicate further now, because the second guest might have taken the first guest's keys (with probability $\frac{1}{n-1}$), reducing the rest to the $n-2$ guests problem, or he may have not, which means there is now a third guest who can never get his key back...
As suggested in @lulu's comment, what you want is called a derangement, a permutation of elements such that no element remains unmoved. The number of derangements of $n$ elements is given by
\begin{equation}
n!\sum_{i=0}^{n}\frac{(-1)^i}{i!},
\end{equation}
so the probability $P(X=0)$ you seek is
\begin{equation}
\sum_{i=0}^{n}\frac{(-1)^i}{i!},
\end{equation}
and thus $P(X\geq 1)$ is 
\begin{equation}
\sum_{i=1}^{n}\frac{(-1)^{i+1}}{i!}.
\end{equation}
Hope this helps!
