Where will the seven dwarfs sleep tonight?

The following problem appeared in The Riddler. It’s an interesting recursive problem.

Each of the seven dwarfs sleeps in his own bed in a shared dormitory. Every night, they retire to bed one at a time, always in the same sequential order, with the youngest dwarf retiring first and the oldest retiring last. On a particular evening, the youngest dwarf is in a jolly mood. He decides not to go to his own bed but rather to choose one at random from among the other six beds. As each of the other dwarfs retires, he chooses his own bed if it is not occupied, and otherwise chooses another unoccupied bed at random.

  1. What is the probability that the oldest dwarf sleeps in his own bed?
  2. What is the expected number of dwarfs who do not sleep in their own beds?

Here is my solution.
[Show Solution]

8 thoughts on “Where will the seven dwarfs sleep tonight?”

  1. Nicely done! One possible correction: “So, curiously, with a very large number of dwarfs, each dwarf’s probability of sleeping in their own bed is roughly one half!” Isn’t it only the eldest’s probability that tends towards 1/2? The second youngest’s, for instance, tends to one, the second eldest’s tends towards 2/3, the third eldest’s towards 3/4, . . . (The divergence from these values is entirely due to our prohibiting the youngest from randomly landing in his own bed.
    https://hectorpefo.github.io/2018-01-06-Strange-Beds/ )

    1. Yes, you’re right. What I was thinking in my head was that the kth eldest dwarf’s probability also tends to 1/2, so in a sense “all dwarfs” have a probability that tends to 1/2. It depends on how you track dwarfs as you increase their number. e.g. if you increase the number of dwarfs by adding more younger ones then every dwarf has a probability that tends to 1/2. I’ll change the text to clarify.

      Thanks for sharing your write-up as well!

      1. I’m not sure we’re on the same page yet. One (to me) surprising thing about this puzzle is that, even for large n, the probabilities for the eldest and the second-eldest remain quite different (tending towards 1/2 and 2/3, respectively). Nearly all of the decay in probability from near 1 to near 1/2 happens in the last few dwarfs.

        1. You’re absolutely right. I made a careless error simplifying fractions… I updated my solution yet again. I agree, it’s quite interesting that things change so dramatically when it comes to the last few dwarfs!

  2. Interesting problem. I need a little bit to think about this.

    Part 2 looks suspiciously like a coupon collecting result, though superficially I don’t really see the linkage — i.e. this one is expected number of ‘hits’ while the coupon result is expected time until absorption.

    Interesting that the problem includes an $\frac{n}{n-1}$ ‘correction’ though, which is reminiscent of the two different ways to calculate Variance — population or sample, and of course doesn’t matter asymptotically (or, for that matter, for moderately large n).

    1. Suppose that the youngest dwarf chooses one of the $n$ beds (including his own bed) at random (the lost boarding pass case). Then Part 2 of the problem has as answer $\sum_{j=1}^{n-1} 1/j$ and the problem looks very much like the following birthday-candle problem. It’s your birthday and you are now $n$ years old. You get a birthday cake with $n$ burning candles. If you blow when there are still $k$ candles burning, then $j$ burning candles will remain, each with probability $1/(k+1)$ for $j=0,1,\ldots, k-1$. What is the expected number of times you must below until there are no burning candles anymore? The answer is $\sum_{k=1}^{n} 1/k$. How to make the ‘translation’ to the problem of the dwarfs?

  3. The probability that the oldest dwarf sleeps in his own bed is (n-2)/(2n-2), n = number of dwarfs.
    The result of the formula for 3 dwarfs is (3-2)/(2*3-2)=1/4.
    The list of all possibilities for 3 dwarfs looks like:
    2 1 3, 3 1 2, 3 2 1.
    According to this the probability amounts to 1/3 .
    Can you please help me and clarify the situation.
    Kind regards,

    1. Hi Walter,
      Your list of all possible sleeping arrangements is correct, but your error is in assuming that each of these sleeping arrangements is equally likely to occur. That’s not the case! In fact, we have:
      2 1 3 occurs 1/4 of the time
      3 1 2 occurs 1/4 of the time
      3 2 1 occurs 1/2 of the time
      The reason is that the first dwarf picks bed 3 half the time (? ? 1), but whenever the first dwarf does this, the second dwarf always picks bed 2 and so we always end up with (3 2 1). This means this arrangement occurs 1/2 of the time.
      If the first dwarf picks bed 2 instead (? 1 ?), then the other two cases, (2 1 3) and (3 1 2) are equally likely to occur, so they each have probability 1/4.

Leave a Reply

Your email address will not be published. Required fields are marked *