ABC News
Get Perplexed With Some Games Of Hex

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:

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!

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.

## Footnotes

1. Important small print: For you to be eligible, I need to receive your correct answer before 11:59 p.m. Eastern time on Sunday. Have a great weekend!

Oliver Roeder was a senior writer for FiveThirtyEight. He holds a Ph.D. in economics from the University of Texas at Austin, where he studied game theory and political competition.