How much can you pull out of a hat?

This week’s Riddler Classic is a strategy game about maximizing payout. What is the optimal strategy?

You start with just the number 1 written on a slip of paper in a hat. Initially, there are no other slips of paper in the hat. You will draw from the hat 100 times, and each time you draw, you have a choice: If the number on the slip of paper you draw is k, then you can either receive k dollars or add k higher numbers to the hat.

For example, if the hat were to contain slips with the numbers 1 through 6 and you drew a 4, you could either receive $4 or receive no money but add four more slips numbered 7, 8, 9 and 10 into the hat. In either case, the slip with the number 4 would then be returned to the hat.

If you play this game perfectly — that is, to maximize the total amount of money you’ll receive after all 100 rounds — how much money would you expect to receive on average?

My solution:
[Show Solution]

Making the fastest track

This week’s Riddler Classic is a problem about minimum-time optimization.

While passing the time at home one evening, you decide to set up a marble race course. No Teflon is spared, resulting in a track that is effectively frictionless. The start and end of the track are 1 meter apart, and both positions are 10 centimeters off the floor. It’s up to you to design a speedy track. But the track must always be at floor level or higher — please don’t dig a tunnel through your floorboards. What’s the fastest track you can design, and how long will it take the marble to complete the course?

My solution:
[Show Solution]

Ellipse packing

You’ve heard of circle packing… Well this week’s Riddler Classic is about ellipse packing!

This week, try packing three ellipses with a major axis of length 2 and a minor axis of length 1 into a larger ellipse with the same aspect ratio. What is the smallest such larger ellipse you can find? Specifically, how long is its major axis?

Extra credit: Instead of three smaller ellipses, what about other numbers of ellipses?

My solution:
[Show Solution]

N Bottles of Beer

This week’s Riddler Classic is puzzle about the world’s most annoying song.

You and your friends are singing the traditional song, “99 Bottles of Beer.” With each verse, you count down the number of bottles. The first verse contains the lyrics “99 bottles of beer,” the second verse contains the lyrics “98 bottles of beer,” and so on. The last verse contains the lyrics “1 bottle of beer.” There’s just one problem. When completing any given verse, your group of friends has a tendency to forget which verse they’re on. When this happens, you finish the verse you are currently singing and then go back to the beginning of the song (with 99 bottles) on the next verse. For each verse, suppose you have a 1 percent chance of forgetting which verse you are currently singing. On average, how many total verses will you sing in the song?

Extra credit: Instead of “99 Bottles of Beer,” suppose you and your friends are singing “N Bottles of Beer,” where N is some very, very large number. And suppose your collective probability of forgetting where you are in the song is 1/N for each verse. If it takes you an average of K verses to finish the song, what value does the ratio of K/N approach?

My solution:
[Show Solution]

Riddler Football Playoffs

This week’s Riddler Classic is a probability question inspired by the ongoing World Cup.

The Riddler Football Playoff (RFP) consists of four teams. Each team is assigned a random real number between 0 and 1, representing the “quality” of the team. If team $A$ has quality $a$ and team $B$ has quality $b$, then the probability that team $A$ will defeat team $B$ in a game is $\frac{a}{a+b}$.

In the semifinal games of the playoff, the team with the highest quality (the “1 seed”) plays the team with the lowest quality (the “4 seed”), while the other two teams play each other as well. The two teams that win their respective semifinal games then play each other in the final.

On average, what is the quality of the RFP champion?

My solution:
[Show Solution]

Randomly cutting a sandwich

This week’s Riddler Classic is geometry puzzle about randomly slicing a square sandwich.

I have made a square sandwich, and now it’s time to slice it. But rather than making a standard horizontal or diagonal cut, I instead pick two random points along the perimeter of the sandwich and make a straight cut from one point to the other. (These points can be on the same side.)

What is the probability that the smaller resulting piece has an area that is at least one-quarter of the whole area?

My solution:
[Show Solution]

Fall color peak

This week’s Riddler Classic is a seasonal puzzle about leaves changing color.

The trees change color in a rather particular way. Each tree independently begins changing color at a random time between the autumnal equinox and the winter solstice. Then, at a random later time for each tree — between when that tree’s leaves began changing color and the winter solstice — the leaves of that tree will all fall off at once. At a certain time of year, the fraction of trees with changing leaves will peak. What is this maximal fraction?

My solution:
[Show Solution]

Another way to solve the problem, courtesy of Matthew Wallace:
[Show Solution]

Loteria

This week’s Riddler Classic is about Lotería, also known as Mexican bingo!

A thousand people are playing Lotería, also known as Mexican bingo. The game consists of a deck of 54 cards, each with a unique picture. Each player has a board with 16 of the 54 pictures, arranged in a 4-by-4 grid. The boards are randomly generated, such that each board has 16 distinct pictures that are equally likely to be any of the 54.

During the game, one card from the deck is drawn at a time, and anyone whose board includes that card’s picture marks it on their board. A player wins by marking four pictures that form one of four patterns, as exemplified below: any entire row, any entire column, the four corners of the grid and any 2-by-2 square.

Four four-by-four grids are shown. In the first grid, the third row has four blue markers. In the second grid, the second column has four blue markers. In the third grid, the four corner squares are marked. And in the fourth grid, the two middle squares in the third and fourth columns are marked, forming a smaller two-by-two square.

After the fourth card has been drawn, there are no winners. What is the probability that there will be exactly one winner when the fifth card is drawn?

My solution:
[Show Solution]

Shared birthdays

This week’s Riddler Classic is a challenging counting problem about shared birthdays.

Suppose people walk into a room, one at a time. Their birthdays happen to be randomly distributed throughout the 365 days of the year (and no one was born on a leap day). The moment two people in the room have the same birthday, no more people enter the room and everyone inside celebrates by eating cake, regardless of whether that common birthday happens to be today.

On average, what is the expected number of people in the room when they eat cake?

Extra credit: Suppose everyone eats cake the moment three people in the room have the same birthday. On average, what is this expected number of people?

My solution:
[Show Solution]

Perfect pizza sharing

This week’s Riddler Classic is about how to cut a pizza to achieve precise area ratios between the slices.

Dean made a pizza to share with his three friends. Among the four of them, they each wanted a different amount of pizza. In particular, the ratio of their appetites was 1:2:3:4. Therefore, Dean wants to make two complete, straight cuts (i.e., chords) across the pizza, resulting in four pieces whose areas have a 1:2:3:4 ratio.

Where should Dean make the two slices?

Extra credit: Suppose Dean splits the pizza with more friends. If six people are sharing the pizza and Dean cuts along three chords that intersect at a single point, how close to a 1:2:3:4:5:6 ratio among the areas can he achieve? What if there are eight people sharing the pizza?

My solution:
[Show Solution]

To jump straight to the results:
[Show Solution]