Penny Pinching

This week’s Riddler Classic is indeed a classic! Here it goes (paraphrased to make it a bit more general):

The game starts with $n$ pennies, which I then divide into two piles any way I like. Then we alternate taking turns, with you first, until someone wins the game. For each turn, a player may take any number of pennies he or she likes from either pile, or instead take the same number of pennies from both piles. Each player must also take at least one penny every turn. The winner of the game is the one who takes the last penny.

If we both play optimally, what starting numbers of pennies guarantee that you can win the game?

Here is my solution:
[Show Solution]

Optimal HORSE

This week’s Riddler Classic is about how to optimally play HORSE — the playground shot-making game. Here is the problem.

Two players have taken to the basketball court for a friendly game of HORSE. The game is played according to its typical playground rules, but here’s how it works, if you’ve never had the pleasure: Alice goes first, taking a shot from wherever she’d like. If the shot goes in, Bob is obligated to try to make the exact same shot. If he misses, he gets the letter H and it’s Alice’s turn to shoot again from wherever she’d like. If he makes the first shot, he doesn’t get a letter but it’s again Alice’s turn to shoot from wherever she’d like. If Alice misses her first shot, she doesn’t get a letter but Bob gets to select any shot he’d like, in an effort to obligate Alice. Every missed obligated shot earns the player another letter in the sequence H-O-R-S-E, and the first player to spell HORSE loses.

Now, Alice and Bob are equally good shooters, and they are both perfectly aware of their skills. That is, they can each select fine-tuned shots such that they have any specific chance they’d like of going in. They could choose to take a 99 percent layup, for example, or a 50 percent midrange jumper, or a 2 percent half-court bomb.

If Alice and Bob are both perfect strategists, what type of shot should Alice take to begin the game?

What types of shots should each player take at each state of the game — a given set of letters and a given player’s turn?

Here is how I solved the problem:
[Show Solution]

and here is the solution:
[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]

The Dodgeball duel

This is a game theory problem from the Riddler. Three dodgeball players, who survives?

Three expert dodgeballers engage in a duel — er, a “truel” — where they all pick up a ball simultaneously and attempt to hit one of the others. Any survivors then immediately start over, attempting to hit each other again. They are equally fast but unequally accurate. Name them Abbott, Bob and Costello. Each has an accuracy of a, b and c, respectively. That is, if Abbott aims at something, he hits it with probability a, Bob with probability b and Costello with probability c. The abilities of each player are known by the others. Let’s say Abbott is a perfect shot: a = 1. Suppose the players follow an optimal strategy, with the goal being survival. Which player, for every possible combination of Bob and Costello’s abilities (b and c), is favored to survive this truel?

Here is my solution:
[Show Solution]

Toddler poker

In a previous post, I took a look at “baby poker”, a game involving two players rolling a six-sided die. The higher number wins, but players may elect to raise, call, or fold depending on their number (which only they can see). In this post, I’ll take a look at the continuous version of the problem (also appeared in a recent Riddler post!) Here is the full text of the problem:

Toddler poker is played by two players. Each is dealt a “card,” which is actually a number randomly chosen uniformly from the interval [0,1]. (It could be 0.1, or 0.9234781, or 1/π, and so on.) The game starts with each player anteing \$1. Player A can then either “call,” in which case both numbers are shown and the player with the higher number wins the \$2 on the table, or “raise,” betting one more dollar. If A raises, B then has the option to either “call” by matching A’s second dollar, after which the higher number wins the \$4 on the table, or “fold,” in which case A wins but B is out only his original \$1. No other plays are made.

What is the optimal strategy for each player? Under those strategies, how much is a game of toddler poker worth to Player A?

Extra credit: What if the value of the raise is \$k — i.e., players stand to profit \$k instead of \$2 after the raise?

Here is my derivation:
[Show Solution]

If you’d like the tl;dr instead:
[Show Solution]

Baby poker

Another game theory problem from the Riddler. This game is a simplified version of poker, but captures some interesting behaviors!

Baby poker is played by two players, each holding a single die in a cup. The game starts with each player anteing \$1. Then both shake their die, roll it, and look at their own die only. Player A can then either “call,” in which case both dice are shown and the player with the higher number wins the \$2 on the table, or Player A can “raise,” betting one more dollar. If A raises, then B has the option to either “call” by matching A’s second dollar, after which the higher number wins the \$4 on the table, or B can “fold,” in which case A wins but B is out only his original \$1. No other plays are made, and if the dice match, a called pot is split equally.

What is the optimal strategy for each player? Under those strategies, how much is a game of baby poker worth to Player A? In other words, how much should A pay B beforehand to make it a fair game?

If you’re interested in the derivation (and maybe learning about some game theory along the way), you can read my full solution here:
[Show Solution]

This alternate solution was proposed by a commenter named Chris. Same answer, but a simpler argument!
[Show Solution]

If you’d just like to know the answer along with a brief explanation, here is the tl;dr version:
[Show Solution]

The war game

This Riddler puzzle is about game theory… War or peace?

Two countries are eyeing each other’s gold. At the beginning of the game, the “strength” of each country’s army is drawn from a continuous uniform distribution and lies somewhere between 0 (very weak) and 1 (very strong). Each country knows its own strength but not that of its opponent. The countries observe their own strength and then simultaneously announce “peace” or “war.”

If both announce “peace,” then they each stay quietly in their own territory, with their own gold, which is worth \$1 trillion (so each “wins” \$1 trillion). If at least one announces “war,” then they go to war, and the country with the stronger army wins the other’s gold. (That is, the stronger country wins \$2 trillion, and the other wins \$0.)

What is the optimal strategy of each country (declaring “peace” or “war”) given its strength?

Extra credit: What if the countries don’t announce at the same time and instead one announces first and the other second? What if the value of winning the war were \$5 trillion rather than \$2 trillion?

Here is my solution for the first part, where both countries declare their intentions simultaneously.
[Show Solution]

Here is my solution for the second part, where the countries declare their intentions sequentially.
[Show Solution]