Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. There are two types: Riddler Express for those of you who want something bite-size, and Riddler Classic for those of you in the slow-puzzle movement. Submit a correct answer for either,1 and you may get a shoutout (chosen at random) in next week’s column. If you need a hint, you can try asking me nicely on Twitter.
Riddler Express
From the language columnist Ben Zimmer, a new year puzzle:
Sometime in the 21st century, the following conversation takes place:
“Don’t throw out that calendar! You could reuse it in the future, when the days and dates on the calendar match up again.”
“OK, but that won’t happen for a long time. Forty years, in fact.”
“You’re right! In fact, this calendar has never had a 40-year gap before.”
What year is it?
Riddler Classic
A board game puzzle, adapted from a Martin Gardner classic:
The game Hip is played by two players using an N-by-N checkerboard. Player 1 starts with \(N^2/2\) white checkers and Player 2 with the same number of black checkers. They take turns placing their checkers on any of the board’s empty squares. A player loses if any four of his or her checkers form a square of any size, tilted to any angle. (The game is purportedly named, of course, for hipsters’ aversion to squares.)
What is the largest board such that this game can end in a draw? What does that draw look like?
Solution to last week’s Riddler Express
Congratulations to 👏 Pankaj Jain 👏 of Los Altos, California, winner of last week’s Express puzzle!
On snowy afternoons, you like to play a type of solitaire game. You deal out cards from a randomly shuffled standard deck, face up, into a pile. With each card you deal, you say the faces of the cards, in order: ace, two, three, up to king, then starting over at ace. If you get through the deck without what you say ever matching what you deal, you win. What are the chances that you win? They’re about 1.6 percent.
Editor’s note (Jan. 13, 10:33 a.m.): The original solution, which remains below, has since been corrected. The answer is roughly the same — about 1.6 percent — but the underlying logic and exact numbers are not. To get the solution below, there was an incorrect assumption that the types of cards were dealt independently over the course of the game. But they are not. You can read more details here.
In a standard deck, there are four cards of each rank — four aces, four twos, four threes and so on. So when you randomize the deck by shuffling it, there is a 4/52 (or 1/13) chance that you will place a card in a position that will match what you eventually speak aloud. Put another way, before you start the game, there is a 12/13 chance that any card will not match what you will speak aloud. In order to win, you have to get through the deck with zero matches, so you need to “win” these 12/13 shots 52 times in a row. The chances of that are \((12/13)^{52} \approx 0.01557\), or about 1.6 percent. Good luck!
Solution to last week’s Riddler Classic
Congratulations to 👏 Evan Taylor 👏 of Ann Arbor, Michigan, winner of last week’s Classic puzzle!
In the game of baby poker, two players, A and B, each ante $1 and roll a die. Player A, knowing only his die roll, can then “call,” forcing a showdown of die rolls. The player with the higher number wins the $2 on the table. Or Player A can “raise,” betting an additional $1. In that case, Player B, knowing only her die roll, can call, matching the dollar and forcing a showdown for the total $4, or fold, losing only her original dollar to A. What are the optimal strategies for both players in this simplified form of poker?
It turns out some bluffing is optimal!
Intuitively, Player A should raise when his die roll is high, and merely call when his die roll is low. Likewise, Player B should call when her die roll is high, and fold when it’s low. However, A also does well to introduce some uncertainty into the game, by occasionally raising when he rolls a low number.
Specifically, here’s A’s optimal strategy: Always raise with a 5 or a 6. Always call with a 2, 3 or 4. And with a 1 — the lowest roll — raise (bluff!) 2/3 of the time and call 1/3 of the time. B’s optimal strategy isn’t unique (there are a number of strategies that all do equally well) but here’s one: Always call with a 4, 5 or 6. Call 1/3 of the time with a 2 or 3. Always fold with a 1.
How did we get there? The puzzle’s submitter, Dan Calistrate, walks us through it:
To solve the game we need to write down its strategic form, which is the matrix of average payoffs for each pair of possible pure strategies for Player A and Player B. A pure strategy for A is a subset of the set {1, 2, 3, 4, 5, 6} — the possible outcomes for his dice — with which he will raise. A pure strategy for Player B is a subset of {1, 2, 3, 4, 5, 6} for which she will call A’s raise (assuming that A raises). Because there are 2^6 = 64 subsets of {1, 2, 3, 4, 5, 6}, the full game matrix is 64-by-64.2We can, however, reduce the number of pure strategies for A to 32, because it is easy to prove that A should always raise when holding a 6 (any strategy where he doesn’t is always ill-advised, or “dominated” in game theory terms). Furthermore, we can reduce the number of pure strategies for Player B by noticing that a pure strategy where she calls with X but not with Y, where Y>X, is never as good as switching the strategy between X and Y (call with Y but not with X). In other words, there is no benefit to bluffing for Player B. Also, B will always call when holding a 6. This means that the only reasonable pure strategies for B are where she calls with X or higher, where X is 1, 2, 3, 4, 5 or 6.
So, given all that, the game matrix is now reduced to a 32-by-6 size. That matrix is shown below. (For simplicity, the entries are all multiplied by 36 — the number of possible combinations of the two dice — in order to show how much A can expect to win over all possible scenarios.) Each entry corresponds to a pair of strategies for A and B, and it’s calculated by simply adding all the 36 outcomes (one for each pair of dice outcomes) under the corresponding pair of strategies. Being a zero-sum game, the optimal mixed strategies and the value of the game can be found by using a minimax algorithm or, more easily, by simply dropping the matrix into an online matrix game calculator.
The pure strategies making up the optimal strategies, along with the optimal probabilities, are displayed along the top and the left sides of the matrix.
It pays to be Player A in a game of baby poker. He has a roughly 9.3-cent advantage.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.