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]

Cracking the safe

The following problem appeared in The Riddler and it’s about finding the right code sequence to crack open a safe.

A safe has three locks, each of which is unlocked by a card, like a hotel room door. Each lock (call them 1, 2 and 3) and can be opened using one of three key cards (A, B or C). To open the safe, each of the cards must be inserted into a lock slot and then someone must press a button labeled “Attempt To Open.”

The locks function independently. If the correct key card is inserted into a lock when the button is pressed, that lock will change state — going from locked to unlocked or unlocked to locked. If an incorrect key card is inserted in a lock when the attempt button is pressed, nothing happens — that lock will either remain locked or remain unlocked. The safe will open when all three locks are unlocked. Other than the safe opening, there is no way to know whether one, two or all three of the locks are locked.

Your job as master safecracker is to open the locked safe as efficiently as possible. What is the minimum number of button-press attempts that will guarantee that the safe opens, and what sequence of attempts should you use?

Here is my solution.
[Show Solution]

A tetrahedron puzzle

This post is about a 3D geometry Riddler puzzle involving spheres and tetrahedra! Here is the problem:

We want to create a new gift for fall, and we have a lot of spheres, of radius 1, left over from last year’s fidget sphere craze, and we’d like to sell them in sets of four. We also have a lot of extra tetrahedral packaging from last month’s Pyramid Fest. What’s the smallest tetrahedron into which we can pack four spheres?

Here is my solution:
[Show Solution]

Is this bathroom occupied?

After a brief hiatus from Riddling, I’m back! This Riddler problem is about probability and bathroom vacancy.

There is a bathroom in your office building that has only one toilet. There is a small sign stuck to the outside of the door that you can slide from “Vacant” to “Occupied” so that no one else will try the door handle (theoretically) when you are inside. Unfortunately, people often forget to slide the sign to “Occupied” when entering, and they often forget to slide it to “Vacant” when exiting.

Assume that 1/3 of bathroom users don’t notice the sign upon entering or exiting. Therefore, whatever the sign reads before their visit, it still reads the same thing during and after their visit. Another 1/3 of the users notice the sign upon entering and make sure that it says “Occupied” as they enter. However, they forget to slide it to “Vacant” when they exit. The remaining 1/3 of the users are very conscientious: They make sure the sign reads “Occupied” when they enter, and then they slide it to “Vacant” when they exit. Finally, assume that the bathroom is occupied exactly half of the time, all day, every day.

Two questions about this workplace situation:

1. If you go to the bathroom and see that the sign on the door reads “Occupied,” what is the probability that the bathroom is actually occupied?
2. If the sign reads “Vacant,” what is the probability that the bathroom actually is vacant?
Extra credit: What happens as the percentage of conscientious bathroom users changes?

Here is how I solved the problem:
[Show Solution]

Squaring the square

This Riddler puzzle is about tiling a square using smaller squares.

You are handed a piece of paper containing the 13-by-13 square shown below, and you must divide it into some smaller square pieces. If you are only allowed to cut along the lines, what is the smallest number of squares you can divide this larger square into? (You could, for example, divide it into one 12-by-12 square and 25 one-by-one squares for a total of 26 squares, but you can do much better.)

Here is how I solved the problem:
[Show Solution]

And here is the tl;dr, just the solutions!
[Show Solution]

The lucky derby

In the spirit of the Kentucky Derby, this Riddler puzzle is about a peculiar type of horse race.

The bugle sounds, and 20 horses make their way to the starting gate for the first annual Lucky Derby. These horses, all trained at the mysterious Riddler Stables, are special. Each second, every Riddler-trained horse takes one step. Each step is exactly one meter long. But what these horses exhibit in precision, they lack in sense of direction. Most of the time, their steps are forward (toward the finish line) but the rest of the time they are backward (away from the finish line). As an avid fan of the Lucky Derby, you’ve done exhaustive research on these 20 competitors. You know that Horse One goes forward 52 percent of the time, Horse Two 54 percent of the time, Horse Three 56 percent, and so on, up to the favorite filly, Horse Twenty, who steps forward 90 percent of the time. The horses’ steps are taken independently of one another, and the finish line is 200 meters from the starting gate.

Handicap this race and place your bets! In other words, what are the odds (a percentage is fine) that each horse wins?

Here is my full derivation (long!):
[Show Solution]

For the tl;dr, the answer is:
[Show Solution]

Colorful balls puzzle

This Riddler puzzle about an interesting game involving picking colored balls out of a box. How long will the game last?

You play a game with four balls: One ball is red, one is blue, one is green and one is yellow. They are placed in a box. You draw a ball out of the box at random and note its color. Without replacing the first ball, you draw a second ball and then paint it to match the color of the first. Replace both balls, and repeat the process. The game ends when all four balls have become the same color. What is the expected number of turns to finish the game?

Extra credit: What if there are more balls and more colors?

Here is my solution to the first part (four balls):
[Show Solution]

Here is my solution to the general case with $N$ balls:
[Show Solution]

Pick a card!

This Riddler puzzle is about a card game where the goal is to find the largest card.

From a shuffled deck of 100 cards that are numbered 1 to 100, you are dealt 10 cards face down. You turn the cards over one by one. After each card, you must decide whether to end the game. If you end the game on the highest card in the hand you were dealt, you win; otherwise, you lose.

What is the strategy that optimizes your chances of winning? How does the strategy change as the sizes of the deck and the hand are changed?

Here is my solution:
[Show Solution]

A supreme court puzzle

This timely Riddler puzzle is about filling supreme court vacancies…

Imagine that U.S. Supreme Court nominees are only confirmed if the same party holds the presidency and the Senate. What is the expected number of vacancies on the bench in the long run?

You can assume the following:

  • You start with an empty, nine-person bench.
  • There are two parties, and each has a 50 percent chance of winning the presidency and a 50 percent chance of winning the Senate in each election.
  • The outcomes of Senate elections and presidential elections are independent.
  • The length of time for which a justice serves is uniformly distributed between zero and 40 years.

Here is my solution:
[Show Solution]

The troll and the dwarves

This Riddler puzzle is a classic! Can you save the dwarves from the troll?

A giant troll captures 10 dwarves and locks them up in his cave. That night, he tells them that in the morning he will decide their fate according to the following rules:

  1. The 10 dwarves will be lined up from shortest to tallest so each dwarf can see all the shorter dwarves in front of him, but cannot see the taller dwarves behind him.
  2. A white or black dot will be randomly put on top of each dwarf’s head so that no dwarf can see his own dot but they can all see the tops of the heads of all the shorter dwarves.
  3. Starting with the tallest, each dwarf will be asked the color of his dot.
  4. If the dwarf answers incorrectly, the troll will kill the dwarf.
  5. If the dwarf answers correctly, he will be magically, instantly transported to his home far away.
  6. Each dwarf present can hear the previous answers, but cannot hear whether a dwarf is killed or magically freed.

The dwarves have the night to plan how best to answer. What strategy should be used so the fewest dwarves die, and what is the maximum number of dwarves that can be saved with this strategy?

Extra credit: What if there are only five dwarves?

Here is my solution:
[Show Solution]