# The Seven Dwarves (of Snow White fame)

The seven dwarves have seven beds in a dormitory room. One night, Sleepy is so tired that he falls asleep on the first bed that he sees. This has happened before, so the other dwarves follow a standard procedure as they enter the dormitory room later that night: if a dwarf can sleep in his own bed, he does so, but if not, he selects a random bed and uses that one. On the night in question, Grumpy is the fourth dwarf to enter the room to go to bed. What's the probability that he sleeps in his own bed?

• Is this a homework problem? A challenge to the community at large? What have you tried? – Aaron Jan 29 '12 at 20:58
• My answer here: math.stackexchange.com/questions/5595/taking-seats-on-a-plane should help – user940 Jan 29 '12 at 21:19
• @Byron: See my answer for a more intuitive explanation of your formula from the earlier question. – Brian M. Scott Jan 29 '12 at 23:22

Suppose that there are $n$ dwarfs, $D_1,\dots,D_n$, and they enter in reverse order (i.e., $D_n$ first and $D_1$ last). I claim that the probability that $D_k$ gets his own bed is $\frac{k}{k+1}$ for every $k<n$; in the present problem $k=4$, so the answer is $\frac45$.

When $D_k$ enters the room, there are $k$ beds still free. Since each dwarf except $D_n$ takes his own bed if it’s available, the beds belonging to $D_{k+1},\dots,D_{n-1}$ must all be occupied, and the free beds must be $k$ of the $k+1$ beds belonging to $D_1,\dots,D_k$, and $D_n$. When a dwarf picks a bed at random, the beds are in effect indistinguishable, so each of the $k+1$ beds belonging to these $k+1$ dwarfs is equally likely to be the one that’s already occupied. In particular, the probability that $D_k$’s bed is already occupied is $\frac1{k+1}$, so the probability that he gets his own bed is $\frac{k}{k+1}$.

• Thanks, that is a lot better than my solution! – user940 Jan 29 '12 at 23:52
• @Byron: But without yours, I’d not have thought to look for a slicker derivation! – Brian M. Scott Jan 30 '12 at 3:04

At each point in time, consider $W =$ the number of beds that (a) belong to a still-awake dwarf, and (b) are already occupied. $W$ is always either $1$ or $0$, and once it reaches $W=0$ it never goes back to $W=1$. On ther other hand $W$ goes from $1$ to $0$ exactly when a dwarf finds his own bed taken and happens to choose the one rightfully belonging to the first dwarf.

When $W=1$, then because of symmetry the wrongly-occupied bed is uniformly distributed among those belonging to still-awake dwarfs. So if we can compute the probability of $W=1$ before the fourth dwarf enters, that probability multiplied by $\frac{1}{4}$ is the probablity the fourth dwarf will have to choose a different bed.

Let $P_n$ be the probablity that $W=1$ when there are still $n$ dwarfs awake.

We then have $P_6=\frac{6}{7}$ because the first dwarf chooses randomly.

Now $P_5 = P_6\times (1-\frac{1}{6^2})$, because $W$ only decreases if the next dwarf can't get his own bed (which happens with probability $\frac{1}{6}$) and he randomly chooses (for a second factor of $\frac{1}{6}$) the bed that could make $W$ decrease.

Similarly $P_4 = P_5 \times (1-\frac{1}{5^2})$.

At this time the fourth dwarf enters, and the probability that his bed is already taken is $P_4 \times \frac{1}{4}$.

You do the arithmetic.