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!
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:
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!
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 firstname.lastname@example.org.