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]

And here are the answers:
[Show Solution]

A coin-flipping game

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

I flip a coin. If it’s heads, I’ve won the game. If it’s tails, then I have to flip again, now needing to get two heads in a row to win. If, on my second toss, I get another tails instead of a heads, then I now need three heads in a row to win. If, instead, I get a heads on my second toss (having flipped a tails on the first toss) then I still need to get a second heads to have two heads in a row and win, but if my next toss is a tails (having thus tossed tails-heads-tails), I now need to flip three heads in a row to win, and so on. The more tails you’ve tossed, the more heads in a row you’ll need to win this game.

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]

Rope timing

This Riddler problem is all about timing:

Suppose you have four ropes and a lighter. Each rope burns at a nonconstant rate but takes exactly one hour to burn completely from one end to the other. You can only light the ropes at either of their ends but can decide when to light each end as you see fit. If you’re strategic in how you burn the ropes, how many specific lengths of time can you measure? (For example, if you had one rope, you could measure two lengths of time: one hour, by simply burning the entire rope from one end, and half an hour, by burning the rope from both ends and marking when the flames meet.)

Extra credit: What if you had N ropes?

Here is my solution:
[Show Solution]

Note: my solution is incomplete (see comments below!)

Microorganism multiplication

This Riddler is about microorganisms multiplying. Will they thrive or will the species go extinct?

At the beginning of time, there is a single microorganism. Each day, every member of this species either splits into two copies of itself or dies. If the probability of multiplication is p, what are the chances that this species goes extinct?

Here is my solution:
[Show Solution]

Here is a more technical (and more correct!) solution adapted from a comment by Bojan.
[Show Solution]