Where Will The Seven Dwarfs Sleep Tonight?

Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. There are two types: Riddler Express for those of you who want something bite-size and Riddler Classic for those of you in the slow-puzzle movement. Submit a correct answer for either,¹ and you may get a shoutout in next week’s column. If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter.

Riddler Express

From Al Zimmermann, two shapely puzzles:

A kite shape is inscribed in a circle, as shown below.² What is the kite’s area?

A rectangle is drawn inside a quarter circle, as shown below.³ What is the rectangle’s area?

Submit your answer

Riddler Classic

From Henk Tijms, adapted from his book “Probability: A Lively Introduction,” it’s bedtime for dwarfs:

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?

Submit your answer

Solution to the previous Riddler Express

Congratulations to 👏 Evan Taylor 👏 of Chicago, winner of the previous Riddler Express!

Your challenge was to deal 10 five-card poker hands from a standard 52-card deck such that when you were finished, you had one hand of each type: a royal flush, a straight flush, a four of a kind, and so on down to a lowly high card. This is easy enough to do, but the question was: How many ways are there to do it?

There are (very roughly) \(8\cdot 10^{20}\) ways. That’s an 8 followed by 20 zeros. This sounds like a lot but, for scale, there are \(6.5\cdot 10^{46}\) total ways to deal out the 10 hands.

To begin accounting for all of these possibilities, you should start with the best hands because there are fewer of them.

• A royal flush is an ace, king, queen, jack and 10 all of a single suit. There are only four ways to deal such a hand — one for each of the four suits.
• Next, a straight flush is five cards in a row all of the same suit. Those cards could start with a low card from an ace to a nine and be in one of four suits, giving 9×4=36 ways.
• A four of a kind could be all four of any single rank of card, plus any other fifth card. There are 13 ranks and 48 cards left over, for 13×48=624 ways.
• You can keep going this way until you get to a high card — and there are 1,302,540 ways to deal that lowly hand.

Multiplying all of those numbers of possible hands together (4×36×624×3,744×5,108×10,200×54,912×123,552×1,098,240×1,302,540) gives a number on the order of \(1.7\cdot 10^{38}\).

However, this number is surely a gross overcount, as our winner Evan explained. Most of these combinations will not satisfy the conditions of the problem because the cards in the hands will overlap — you can’t use the ace of spades twice, for example. But we can account for this, too. If we consider 10 random hands taken from a single full deck of 52 cards, the probability that none of them have overlapping cards is

\begin{equation*}\frac{52\cdot 51\cdot 50\cdot \ldots\cdot 3}{52^{10}\cdot 51^{10}\cdot 50^{10}\cdot 49^{10}\cdot 48^{10}}\approx 4.8\cdot 10^{-18}\end{equation*}

In other words, we start in the numerator with all the possible ways to order 50 cards from a single deck, and divide that by the number of ways to deal out five cards from each of 10 decks. That tells us, essentially, what percentage of all possible sets of 10 hands do not include any repeated cards. The probability of overlaps in our game will depend on the specific interactions of the cards in the types of hands that we need — how our need for a full house interacts with our need for two pair, and so on. But the ratio above is a good start in calculating how inflated that \(1.7\cdot 10^{38}\) estimate is. So if we multiply that initial count by this tiny probability, we can get rid of the portion that has overlapping cards. That gives about \(8\cdot 10^{20}\) possibilities. This isn’t precise — the combinatorics needed to arrive at a precise answer would take up a lot of time and space and wouldn’t buy us much insight in return — but it’s a good approximation.

Solution to last week’s Riddler Classic

Congratulations to 👏 Clint Young 👏 of Yonkers, New York, winner of the previous Riddler Classic!

You were presented with a game of chance called Left, Right, Center. In this game, everyone sits in a circle and starts with some number of $1 bills. You take turns, in order around the circle, rolling three dice. For each die, if it comes up 1 or 2, you give a dollar to the person on your left. If it comes up 3 or 4, you give a dollar to the person on your right. And if it comes up 5 or 6, you put a dollar in the center. The game ends as soon as only a single person has any money left. How long is the game expected to last for six players each starting with three $1 bills? For X players each starting with Y $1 bills?

The game with six players and three bills will take about 24 turns. For X players and Y bills, you can expect it to take about 2×(X–2)×Y turns. Some might say that’s an eternity for such a trivial game.

There were some specific points in the rules that I neglected to explicitly address in the original question. To arrive at the answer above, you can assume the following: First, if a player has no dollars, then her turn is skipped. Second, if a player has one or two dollars, then the player rolls only one or two dice, respectively.

While there are pure mathematical structures that would allow us to analyze this game — Markov processes, specifically — the analysis is arguably easier and more interesting if we approach it as a programming problem. It’s a very algorithmic game, after all, and quite suitable as a computational learning exercise. The basic programmatic idea is to define the mathematical objects called “players,” each one of which has some number of bills associated with it. Then have your program simulate the rolls of the dice, player by player. Depending on the dice’s outcome (i.e. your program’s random-number generator) you will deduct from the bill count of the player whose turn it was and increment the count of the player on his left or right. Have the program continue this process, player by player, stopping when only one has bills remaining. Also have the program keep track of how many turns it has simulated. When the game is over, make a note of the number of turns. Run this program many times — say, 100,000 — averaging the turn counts for each run, and you’ve arrived at a good estimate of the expected length of this game.

Our winner submitted the Python code he used to solve the problem, as did solver Ryan Semmler, so you can see a couple examples.

Finally, here’s a rough guide, per the formula above, to how many turns this game will take if you decide to break out the dice and dollar bills at your next happy hour:

Want to submit a riddle?

Email me at oliver.roeder@fivethirtyeight.com.