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.

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?

share|improve this question
1  
Is this a homework problem? A challenge to the community at large? What have you tried? –  Aaron Jan 29 '12 at 20:58
1  
My answer here: math.stackexchange.com/questions/5595/taking-seats-on-a-plane should help –  Byron Schmuland 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
add comment

2 Answers

up vote 3 down vote accepted

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}$.

share|improve this answer
    
Thanks, that is a lot better than my solution! –  Byron Schmuland 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
add comment

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.

share|improve this answer
add comment

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.