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]

Baking the optimal cake

This Riddler puzzle asks about finding the maximum-volume shape subject to constraints.

A mathematician who has a birthday coming up asks his students to make him a cake. He is very particular and asks his students to make him a three-layer cake that fits under a hollow glass cone he has on his desk. He requires that the cake fill up the maximum amount of volume under the cone as possible and that the layers of the cake have straight vertical sides. What are the thicknesses of the three layers of the cake in terms of the height of the glass cone? What percentage of the cone’s volume does the cake fill?

Here is my solution.
[Show Solution]

Here, I go into more detail about bounding the optimal cake volume as the number of layers becomes large.
[Show Solution]

Should the grizzly eat the salmon?

This Riddler puzzle concerns a random process and sequential decision-making.

A grizzly bear stands in the shallows of a river during salmon spawning season. Precisely once every hour, a fish swims within its reach. The bear can either catch the fish and eat it, or let it swim past to safety. This grizzly is, as many grizzlies are, persnickety. It’ll only eat fish that are at least as big as every fish it ate before.

Each fish weighs some amount, randomly and uniformly distributed between 0 and 1 kilogram. (Each fish’s weight is independent of the others, and the skilled bear can tell how much each weighs just by looking at it.) The bear wants to maximize its intake of salmon, as measured in kilograms. Suppose the bear’s fishing expedition is two hours long. Under what circumstances should it eat the first fish within its reach? What if the expedition is three hours long?

Here is my solution:
[Show Solution]

Random walk with endpoints

The Riddler post for today is about a bar game where you flip a coin and move forward or backward depending on the result. Here is the problem:

Consider a hot new bar game. It’s played with a coin, between you and a friend, on a number line stretching from negative infinity to positive infinity. (It’s a very, very long bar.) You are assigned a winning number, the negative integer -X, and your friend is assigned his own winning number, a positive integer, +Y. A marker is placed at zero on the number line. Then the coin is repeatedly flipped. Every time the coin lands heads, the marker is moved one integer in a positive direction. Every time the coin lands tails, the marker moves one integer in a negative direction. You win if the coin reaches -X first, while your friend wins if the coin reaches +Y first. (Winner keeps the coin.)

How long can you expect to sit, flipping a coin, at the bar? Put another way, what is the expected number of coin flips in a complete game?

Here is my solution:
[Show Solution]

and here is a much slicker solution, courtesy of Daniel Ross:
[Show Solution]

The blue-eyed islanders

Today’s Riddler problem is another classic. The current incarnation of the puzzle is about error-prone mathematicians, while the classic version is about blue-eyed islanders.

A university has 10 mathematicians, each one so proud that, if she learns that she made a mistake in a paper, no matter how long ago the mistake was made, she resigns the next Friday. To avoid resignations, when one of them detects a mistake in the work of another, she tells everyone else but doesn’t inform the mistake-maker. All of them have made mistakes, so each one thinks only she is perfect. One Wednesday, a super-mathematician, whom all respect and believe, comes to visit. She looks at all the papers and says: “Someone here has made a mistake.”

What happens then? Why?

Here is the solution:
[Show Solution]

The puzzle of the pirate booty

Today’s puzzle was posed on the Riddler blog, but it’s actually a classic among problem-solving enthusiasts, and is commonly known as the pirate game. Here is the formulation used in the Riddler:

Ten Perfectly Rational Pirate Logicians (PRPLs) find 10 (indivisible) gold pieces and wish to distribute the booty among themselves.

The pirates each have a unique rank, from the captain on down. The captain puts forth the first plan to divide up the gold, whereupon the pirates (including the captain) vote. If at least half the pirates vote for the plan, it is enacted, and the gold is distributed accordingly. If the plan gets fewer than half the votes, however, the captain is killed, the second-in-command is promoted, and the process starts over. (They’re mutinous, these PRPLs.)

Pirates always vote by the following rules, with the earliest rule taking precedence in a conflict:

  1. Self-preservation: A pirate values his life above all else.
  2. Greed: A pirate seeks as much gold as possible.
  3. Bloodthirst: Failing a threat to his life or bounty, a pirate always votes to kill.

Under this system, how do the PRPLs divide up their gold?

Extra credit: Solve the generalized problem where there are P pirates and G gold pieces.

Here is the solution to the main problem:
[Show Solution]

And here is a solution to the general case:
[Show Solution]

If this sort of problem interests you, I recommend taking a crack at the riddle of the blue-eyed islanders, or the unfaithful husbands. More information here as well.