Cutting a ruler into pieces

This week’s Riddler Classic is a paradoxical question about cutting a ruler into smaller pieces.

Recently, there was an issue with the production of foot-long rulers. It seems that each ruler was accidentally sliced at three random points along the ruler, resulting in four pieces. Looking on the bright side, that means there are now four times as many rulers — they just happen to have different lengths. On average, how long are the pieces that contain the 6-inch mark?

With four cuts, each piece will be on average 3 inches long, but that can’t be the answer, can it?

Here is my solution:
[Show Solution]

Flip to freedom

This week’s Riddler Classic is a problem about coin flipping. The text of the original problem is quite long, so I will paraphrase it here:

There are $n$ prisoners, each with access to a random number generator (generates uniform random numbers in $[0,1]$) and a fair coin. Each prisoner is given the opportunity to flip their coin once if they so choose. If all of the flipped coins come up Heads, all prisoners are released. But if any of the flipped coins come up Tails, or if no coins are flipped at all, the prisoners are not released. If the prisoners cannot communicate in any way and do not know who is flipping their coin or not, how can they maximize their chances of being released?

Here is my solution:
[Show Solution]

Mismatched socks

This week’s Riddler Classic is a problem familiar to many…

I have $n$ pairs of socks in a drawer. Each pair is distinct from another and consists of two matching socks. Alas, I’m negligent when it comes to folding my laundry, and so the socks are not folded into pairs. This morning, fumbling around in the dark, I pull the socks out of the drawer, randomly and one at a time, until I have a matching pair of socks among the ones I’ve removed from the drawer.

On average, how many socks will I pull out of the drawer in order to get my first matching pair?

Here is my solution:
[Show Solution]

Gift card puzzle

Here is a puzzle from the Riddler about gift cards:

You’ve won two gift cards, each loaded with 50 free drinks from your favorite coffee shop. The cards look identical, and because you’re not one for record-keeping, you randomly pick one of the cards to pay with each time you get a drink. One day, the clerk tells you that he can’t accept the card you presented to him because it doesn’t have any drink credits left on it.

What is the probability that the other card still has free drinks on it? How many free drinks can you expect are still available?

Here is my solution:
[Show Solution]

Elf music

This holiday-themed Riddler problem is about probability:

In Santa’s workshop, elves make toys during a shift each day. On the overhead radio, Christmas music plays, with a program randomly selecting songs from a large playlist.

During any given shift, the elves hear 100 songs. A cranky elf named Cranky has taken to throwing snowballs at everyone if he hears the same song twice. This has happened during about half of the shifts. One day, a mathematically inclined elf named Mathy tires of Cranky’s sodden outbursts. So Mathy decides to use what he knows to figure out how large Santa’s playlist actually is.

Help Mathy out: How large is Santa’s playlist?

Here is my solution:
[Show Solution]

Sniff out the spies

This interesting problem appeared on the Riddler blog. Here it goes:

There are N agents and K of them are spies. Your job is to identify all the spies. You can send a given number of agents to a “retreat” on a remote island. If all K spies are present at the retreat, they will meet to strategize. If even one spy is missing, this spy meeting will not take place. The only information you get from a retreat is whether or not the spy meeting happened. You can send as many agents as you like to the retreat, and the retreat can happen as many times as needed. You know the values of N and K.

What’s the minimum number of retreats needed to guarantee you can identify all K spies? If each retreat costs \$1,000 per person, what is the total cost to identify all K spies?

To begin with, let’s assume you know that N = 1,024 and K = 17.

Here is my solution for $K=1$:
[Show Solution]

And here is a partial solution for $K \gt 1$:
[Show Solution]

Paths to work

This Riddler puzzle is a classic problem: how many lattice paths connect two points on a grid? Here is a paraphrased version of the problem.

The streets of Riddler City are laid out in a perfect grid. You walk to work each morning and back home each evening. Restless and inquisitive mathematician that you are, you prefer to walk a different path along the streets each time. How many different paths are there? (Assume you don’t take paths that are longer than required). Your home is M blocks west and N blocks south of the office.

Here is my solution:
[Show Solution]

Finding the doctored coin

This Riddler puzzle is about repeatedly flipping coins!

On the table in front of you are two coins. They look and feel identical, but you know one of them has been doctored. The fair coin comes up heads half the time while the doctored coin comes up heads 60 percent of the time. How many flips — you must flip both coins at once, one with each hand — would you need to give yourself a 95 percent chance of correctly identifying the doctored coin?

Extra credit: What if, instead of 60 percent, the doctored coin came up heads some P percent of the time? How does that affect the speed with which you can correctly detect it?

Here is my solution.
[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]

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]