Definitive diffidence

This week’s Riddler Classic is an interesting back-and forth game trying to guess whose number is larger.

Martina and Olivia each secretly generate their own random real number, selected uniformly between 0 and 1. Starting with Martina, they take turns declaring (so the other can hear) who they think probably has the greater number until the first moment they agree. Throughout this process, their respective numbers do not change. So for example, their dialogue might go as follows:

Martina: My number is probably bigger.

Olivia: My number is probably bigger.

Martina: My number is probably bigger.

Olivia: My number is probably bigger.

Martina: Olivia’s number is probably bigger.

They are playing as a team, hoping to maximize the chances they correctly predict who has the greater number.

For any given round with randomly generated numbers, what is the probability that the person they agree on really does have the bigger number?

Extra credit: Martina and Olivia change the rules so that they stop when Olivia first says that she agrees with Martina. That is, if Martina says on her turn that she agrees with Olivia, that is not a condition for stopping. Again, if they play to maximizing their chances, what is the probability that the person they agree on really does have the bigger number?

Here is my solution
[Show Solution]

Outthink the Sphinx

This week’s Riddler Classic is a tricky puzzle that combines logic and game theory.

You will be asked four seemingly arbitrary true-or-false questions by the Sphinx on a topic about which you know absolutely nothing. Before the first question is asked, you have exactly $1. For each question, you can bet any non-negative amount of money that you will answer correctly. That is, you can bet any real number (including fractions of pennies) between zero and the current amount of money you have. After each of your answers, the Sphinx reveals the correct answer. If you are right, you gain the amount of money you bet; if you are wrong, you lose the money you bet.

However, there’s a catch. (Isn’t there always, with the Sphinx?) The answer will never be the same for three questions in a row.

With this information in hand, what is the maximum amount of money you can be sure that you’ll win, no matter what the answers wind up being?

Extra credit: This riddle can be generalized so that the Sphinx asks N questions, such that the answer is never the same for Q questions in a row. What are your maximum guaranteed winnings in terms of N and Q?

If you’re just looking for the answer, here it is:
[Show Solution]

Here is a more detailed write-up of the solution:
[Show Solution]

Quarter flipping on a spinning table

This week’s Riddler Classic is a simple-sounding problem about statistics. But it’s not so simple! Here is a paraphrased version of the problem:

There is a square table with a quarter on each corner. The table is behind a curtain and thus out of your view. Your goal is to get all of the quarters to be heads up — if at any time all of the quarters are heads up, you will immediately be told and win.

The only way you can affect the quarters is to tell the person behind the curtain to flip over as many quarters as you would like and in the corners you specify. (For example, “Flip over the top left quarter and bottom right quarter,” or, “Flip over all of the quarters.”) Flipping over a quarter will always change it from heads to tails or tails to heads. However, after each command, the table is spun randomly to a new orientation (that you don’t know), and you must give another instruction before it is spun again.

Can you find a series of steps that guarantees you will have all of the quarters heads up in a finite number of moves?

Here is my solution:
[Show Solution]

Smudged secret messages

This Riddler is a twist on a classic problem: decoding equations! Here is the paraphrased problem:

The goal is to decode two equations. In each of them, every different letter stands for a different digit. But there is a minor problem in both equations. In the first equation, letters accidentally were smudged and are now unreadable. (These are represented with dashes below.) But we know that all 10 digits, 0 through 9, appear in the equation.

What digits belong to what letters, and what are the dashes? In the second equation, one of the letters in the equation is wrong. But we don’t know which one. Which is it?

Here is my detailed solution:
[Show Solution]

If you’re just interested in the answers, here they are:
[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]

The honest prince

This Riddler puzzle is about randomly generating convex quadrilaterals.

You’re the most eligible bachelorette in the kingdom, and you’ve decided to marry a prince. The king has invited you to his castle so that you may choose from among his three sons. The eldest prince is honest and always tells the truth. The youngest prince is dishonest and always lies. The middle prince is mischievous and tells the truth sometimes and lies the rest of the time. Because you will be forever married to one of the princes, you want to marry the eldest (truth-teller) or the youngest (liar) because at least you know where you stand with each. But there’s a problem: You can’t tell the princes apart just by looking, and the king will grant you only one yes-or-no question that you may address to only one of the brothers.

What yes-or-no question can you ask that will ensure that you do not marry the middle prince?

Here is my solution:
[Show Solution]

Space race

This Riddler puzzle is about a game involving filling up the space on a square table using coins.

Two players are seated at a square table. The first player places a coin on the table, the second places a coin on the table, and they carry on placing coins one after another, with the only condition being that the coins are not allowed to touch. The winner is the person who places the final coin on the table, meaning that he or she fills the last remaining space between the other coins.

The table has to be larger than a single coin, and all the coins placed must be identically sized. If the players play optimally, is one of the two players guaranteed to win? If so, what is the winning strategy?

Need a hint?
[Show Solution]

Here is my solution:
[Show Solution]

Tangled wires

This Riddler puzzle is about tangled wires. Can you figure out how to untangle them?

There are N wires leading from the top of a bell tower down to the ground floor. But as wires tend to do, these have become hopelessly tangled. Good thing the wires on the top floor are all labeled, from 1 to N. The wires on the bottom, however, are not. (In retrospect, somebody probably should have anticipated a tangle or two.)

You need to figure out which ground-floor wire’s end corresponds to which top-floor wire’s end. (The bulk of the wiring is hidden behind a wall, so you can’t simply untangle them.) On the ground floor, you can tie two wire ends together, and you can tie as many of these pairs as you like. You can then walk to the top floor and use a circuit detector to check whether any two of the wires at the top of the tower are connected or not. What is the smallest number of trips to the top of the tower you need to take in order to correctly label all the wires on the bottom?

Here is my solution.
[Show Solution]

Adversarial map coloring

This Riddler problem considers the classical map-coloring problem with an adversarial twist! One player draws countries and the other player colors them.

Allison and Bob decide to play a map-coloring game. Each turn, Allison draws a simple closed curve on a piece of paper, and Bob must then color the interior of the “country” that curve creates with one of his many crayons. If the new country borders any pre-existing countries, Bob must color the new country with a color that is different from the ones he used for the bordering ones.

Allison wins the game when she forces Bob to use a sixth color. If they both play optimally, how many countries will Allison have to draw to win?

Here is my solution:
[Show Solution]

How many bananas can the camel carry?

This Riddler puzzle is a simple twist on a classic.

You have a camel and 3,000 bananas. You would like to sell your bananas at the bazaar 1,000 miles away. Your loyal camel can carry at most 1,000 bananas at a time. However, it has an insatiable appetite and quite the nose for bananas — if you have bananas with you, it will demand one banana per mile traveled. In the absence of bananas on his back, it will happily walk as far as needed to get more bananas, loyal beast that it is. What should you do to get the largest number of bananas to the bazaar? What is that number?

Here is my solution.
[Show Solution]