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]

5 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).

Leave a Reply

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