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] Can you eat all the chocolates? This week’s Riddler Classic is a neat puzzle about eating chocolates. I have 10 chocolates in a bag: Two are milk chocolate, while the other eight are dark chocolate. One at a time, I randomly pull chocolates from the bag and eat them — that is, until I pick a chocolate of the other kind. When I get to the other type of chocolate, I put it back in the bag and start drawing again with the remaining chocolates. I keep going until I have eaten all 10 chocolates. For example, if I first pull out a dark chocolate, I will eat it. (I’ll always eat the first chocolate I pull out.) If I pull out a second dark chocolate, I will eat that as well. If the third one is milk chocolate, I will not eat it (yet), and instead place it back in the bag. Then I will start again, eating the first chocolate I pull out. What are the chances that the last chocolate I eat is milk chocolate? Here is my original solution: [Show Solution] And here is a far more elegant solution, courtesy of @rahmdphd on Twitter. [Show Solution] Flawless war his week’s Riddler Classic has to do with the card game “War”. Here is the problem, paraphrased: War is a two-player game in which a standard deck of cards is first shuffled and then divided into two piles with 26 cards each; one pile for each player. In every turn of the game, both players flip over and reveal the top card of their deck. The player whose card has a higher rank wins the turn and places both cards on the bottom of their pile. Assuming a deck is randomly shuffled before every game, how many games of War would you expect to play until you had a game that lasted just 26 turns (with no ties; a flawless victory)? Here is my solution: [Show Solution] Thanos snaps This week’s Riddler Express problem is a nod to the recently released finale to the Avengers saga. No spoilers! Thanos, the all-powerful supervillain, can snap his fingers and destroy half of all the beings in the universe. But what if there were 63 Thanoses, each snapping his fingers one after the other? Out of 7.5 billion people on Earth, how many can we expect would survive? If there were N Thanoses, what would the survival fraction be? 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]

The number line game

This Riddler puzzle is a game theory problem: how should each player play the game to maximize their own winnings?

Ariel, Beatrice and Cassandra — three brilliant game theorists — were bored at a game theory conference (shocking, we know) and devised the following game to pass the time. They drew a number line and placed \$1 on the 1, \$2 on the 2, \$3 on the 3 and so on to \$10 on the 10.

Each player has a personalized token. They take turns — Ariel first, Beatrice second and Cassandra third — placing their tokens on one of the money stacks (only one token is allowed per space). Once the tokens are all placed, each player gets to take every stack that her token is on or is closest to. If a stack is midway between two tokens, the players split that cash.

How will this game play out? How much is it worth to go first?

A grab bag of extra credits: What if the game were played not on a number line but on a clock, with values of \$1 to \$12? What if Desdemona, Eleanor and so on joined the original game? What if the tokens could be placed anywhere on the number line, not just the stacks?

Here are the details of how I approached the problem:
[Show Solution]

[Show Solution]

A coin-flipping game

This Riddler puzzle involves a particular coin-flipping game. Here is the problem:

I may flip a potentially infinite number of times, always needing to flip a series of N heads in a row to win, where N is T + 1 and T is the number of cumulative tails tossed. I win when I flip the required number of heads in a row.

What are my chances of winning this game? (A computer program could calculate the probability to any degree of precision, but is there a more elegant mathematical expression for the probability of winning?)

Here is my solution:
[Show Solution]

Hanging a picture frame

The following problems appeared in The Riddler. It’s a problem about knots! Or rather, not-knots.

Imagine a framed picture suspended by a cord that’s hanging on two nails. If the picture were hung “normally,” you’d expect the removal of one nail to leave the picture hanging from the other (albeit a bit askew). But how can you hang a picture on two nails so that if you remove either nail the picture will crash to the floor?

What about three nails? What about four nails? What about on two red nails and two blue nails such that the picture falls if both red nails are removed and if both blue nails are removed but remains hanging if one of each color is removed?

Here is my solution for the case of two nails:
[Show Solution]

Here is my solution for the cases of three and four nails:
[Show Solution]

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]

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]