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 in next week’s column. If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter.
I spent last weekend at the University of Alberta talking with scientists about games. One of them was Ryan Hayward, who is a computer science professor and has devoted much of his academic career to studying a board game called Hex. Naturally, he is the author of “Hex: The Full Story.”
Here are the rules: The board is an array of hexagons. Two opposing sides of the board are black; the other two opposing sides are white. One player has the black sides and black stones; the other player has the white sides and white stones. Players alternate turns. On a turn, a player puts a stone of their color in an empty cell. The winner is whoever joins her two sides with some unbroken chain of her stones.
The game has a rich mathematical history. It was created by the Danish polymath and inventor Piet Hein and debuted in the Danish newspaper Politiken in the 1940s. It also occurred to a young John Nash — later a founding father of game theory and a Nobel Prize winner — during his grad school years at Princeton. According to The New York Times: “Soon after he arrived he invented an extremely clever game that was played with markers on hexagonal bathroom tiles. An instant fad in the common room, it was called ‘Nash’ or ‘John.’” The game also got attention years later from that great mathematics popularizer, Martin Gardner.
In the early days of the game, puzzles were created to help illustrate its deep strategy — which is underpinned by something called the Brouwer fixed-point theorem — and to popularize the game among the newspaper’s readers. So continuing in that tradition, below are three Hex puzzles — one easy, two harder — shared with me by Hayward. In each, it’s white’s turn to play and guarantee a win with the right move. Each puzzle has only one solution. I want you to find it!
Riddler Express
Riddler Classic
Solution to last week’s Riddler Express
Congratulations to 👏 JP Vrolyk 👏 of Herndon, Virginia, winner of last week’s Riddler Express!
How many numbers contain the numbers of their numbers? That was the question posed last week. For example, 22 does this — it has two 2s. The number 21322314 does it, too — it contains two 1s, three 2s, two 3s and one 4. These numbers, which act as their own “inventories,” are made up of an alternating series of tallies and numerals. If we assume that their numerals must be in ascending order, so we can’t simply rearrange one such number into another, how many such self-inventory numbers are there?
There are 109 of them.
For starters, we know that there is an answer and that the number of these special numbers is finite — that is, they can’t go on forever. It turns out, in fact, that they can’t be longer than 22 digits (otherwise the number is too complicated for it to describe itself). To count them, we could of course write a computer program, as many solvers did. But if we’re working with just a pencil and paper, we can also identify patterns. For example, let’s say that we’ve found the number 10313314 — one 0, three 1s, three 3s and one 4. Perfect! But why stop there? We can swap out that last “4” with a 5, 6, 7, 8 or 9, and our self-contained number works just as well. The same is true of 21322314, 21322315, 21322316 and so on.
The largest such number with single-digit tallies is 613223141526171819: six 1s, three 2s, two 3s, etc. The largest such number in general is 101112213141516171819: one 0, eleven 1s, two 2s, etc.
The On-Line Encyclopedia of Integer Sequences (yes, it exists) describes these as “autobiographical numbers” — they tell their own stories. And here they are in all their autobiographical glory:
22
10213223
10311233
10313314
10313315
10313316
10313317
10313318
10313319
21322314
21322315
21322316
21322317
21322318
21322319
31123314
31123315
31123316
31123317
31123318
31123319
31331415
31331416
31331417
31331418
31331419
31331516
31331517
31331518
31331519
31331617
31331618
31331619
31331718
31331719
31331819
1031223314
1031223315
1031223316
1031223317
1031223318
1031223319
3122331415
3122331416
3122331417
3122331418
3122331419
3122331516
3122331517
3122331518
3122331519
3122331617
3122331618
3122331619
3122331718
3122331719
3122331819
10413223241516
10413223241517
10413223241518
10413223241519
10413223241617
10413223241618
10413223241619
10413223241718
10413223241719
10413223241819
41322324151617
41322324151618
41322324151619
41322324151718
41322324151719
41322324151819
41322324161718
41322324161719
41322324161819
41322324171819
1051322314251617
1051322314251618
1051322314251619
1051322314251718
1051322314251719
1051322314251819
1051322325161718
1051322325161719
1051322325161819
1051322325171819
5132231425161718
5132231425161719
5132231425161819
5132231425171819
5132232516171819
106132231415261718
106132231415261719
106132231415261819
106132231426171819
106132231526171819
613223141526171819
1011112131415161718
1011112131415161719
1011112131415161819
1011112131415171819
1011112131416171819
1011112131516171819
1011112141516171819
1011113141516171819
1111213141516171819
10713223141516271819
101112213141516171819
Solution to last week’s Riddler Classic
Congratulations to 👏 Peter Ji 👏 of Madison, Wisconsin, winner of last week’s Riddler Classic!
Last week, you were playing a game with a single opponent. In front of you were a pile of pentominoes and an empty eight-by-eight grid. Taking turns, you and your opponent selected a pentomino from the pile, rotated it however you liked and placed it anywhere within the grid. The pieces weren’t allowed to overlap or extend outside the grid. The person to place the last possible piece won. Assume you went first. What was the optimal strategy? How did this game end with perfect play?
With perfect play, the player who goes first will win for sure. But you have to be perfect for a while.
Our winner this week, Peter, solved the problem with a computer program using backtracking. He described his general approach this way: If all of the second player’s possible moves lead to losing positions, the first player’s position is a winning one. If the second player has a winning move, the first player’s position is a losing one. Finally, if there are no possible moves, the current state is a winning one.
This game has also received some academic attention, including in a 1996 paper by the computer scientist Hilarie Orman. Below is one of the winning first moves that Orman studied. In general, the first player does well to restrict the possible number of responses of his opponent — a player loses if that player can’t make a move, after all. This move is one of the most restrictive, occupying much of the possible territory on the board:
However, finding the most restrictive move is not enough by itself to guarantee a win. If the first player plays in the middle, as shown below — one of the maximally restrictive moves — and the second player responds with the piece on the left, the second player can guarantee a win.
So in the absence of any neat and tidy intuition for the winning strategy, we are left to analyze a very big game indeed. There are more than 2,000 possible first moves, and there are roughly between 1,000 and 2,000 responses to that move, and so on — games range between five and 12 total moves. As a result, Orman’s program analyzed more than 20 billion different positions. But beginning with the move shown in the first diagram and playing ideally from there, the first player can navigate through that vast thicket, steering the game to a win in every case.
The rest of the winning sequence is left for you to find as you play the game. Perhaps this math will inspire you to build your own pentominoes board!
https://twitter.com/benjamindickman/status/1105487481611472896
Winning at pentominoes: If it were easy, everyone would do it.
Want more riddles?
Well, aren’t you lucky? There’s a whole book full of the best puzzles from this column and some never-before-seen head-scratchers. It’s called “The Riddler,” and it’s in stores now!
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.