To Win This Numbers Game, Learn to Avoid Math Patterns

Here’s a simple number game to play on a rainy day, or while sheltering in place. You and I take turns crossing out numbers from the list {1, 2, 3, …, 9}. The winner is the last person to cross out a number without making three crossed-out numbers in a row. Let’s play! You can go first.

Suppose after four moves we’ve crossed out these numbers:

1    2    3    4    5    6    7    8    9

It’s your turn again. Notice if you cross out 4 you lose, as that makes three in a row: 3-4-5. You also lose if you cross out 7, as that makes 7-8-9. Your only safe plays are to cross out 1, 2 or 6. But no matter which number you choose, I can cross out one of the others and win by leaving you with no safe moves.

This is a simple game with some interesting math. One approach is to create gaps so your opponent has no choice but to complete a three-in-a-row pattern in the middle, like this:

1    2    3    4    5    6    7    8    9

Another approach is to play close to your opponent and force them to complete three in a row on either side, like this:

1    2    3    4    5    6    7    8    9

Regardless of how you play, one fact is mathematically certain: After six moves, someone has to have won. That’s because it’s impossible to cross out seven of the nine numbers without crossing out three in a row. (If you don’t believe me, give it a try. We’ll take this up in the exercises at the end.) In this case we say that 6 is the “upper bound” on the number of total moves that can be played in the game.

So even though we might not always know the best move to make, we know that our game can’t last more than six moves. And we can extend this further. A game using the numbers 1 through 15 can’t last more than 10 moves, and in general, if the size of the game board is divisible by 3, at most 2/3 of the numbers can be crossed out. Finding an upper bound like this is a step toward understanding our game: For example, we could use our upper bound as a guide to figuring out a winning strategy, or as a point of reference for what happens when the game board isn’t a multiple of 3. And while knowing the upper bound might not seem like much, it’s a lot more than we can say about similar games with slightly different rules.

For example, let’s change the rules to make the loser the first person to complete three in a row of any step size. This means you lose if you make 2-3-4, as in the original game, but also if you make 1-3-5 (three in a row of step size 2) or 1-4-7 (step size 3). These patterns are “arithmetic progressions”: sequences of numbers with a common step size, called the common difference.

Let’s return to our first game board and use the new rules. It’s still your turn. And you’ve lost.

1    2    3    4    5    6    7    8    9

Crossing out 1 creates 1-3-5; 2 makes 2-5-8; 4 makes 3-4-5; 6 makes 3-6-9; and 7 makes 7-8-9. There’s nothing you can do that doesn’t complete a crossed-out arithmetic progression. Notice that there’s a lot more to keep track of here. As a result, this game is much more complicated than the original. And it’s much harder to find the upper bound for the number of safe moves.

For mathematicians, the real fun is in turning a simple game about numbers into a game against math itself. Their goal is to figure out how long you can play this game before someone has to lose, on a game board of any size. In other words, given a list of numbers of any length, how many numbers can you cross out before your list must contain an arithmetic progression? The rules sound simple enough, but we don’t actually know the answer. And we know even less about other variations of this game. Let’s play a bit more and see where the mathematics takes us.

In our arithmetic progression game, a set of safe moves is essentially a “Salem-Spencer set,” a subset of the set {1, 2, 3, 4, 5, 6, 7, 8, 9} that contains no arithmetic progressions. So the upper bound is really just the biggest possible Salem-Spencer subset of our game board. But finding the right moves to get there can be tricky. Let’s see why.

We’ll start with a fresh board. No one can lose on the first two moves, so let’s just make those 3 and 5.

1    2    3    4    5    6    7    8    9

Now we have to pick a third number, and it’s time to start paying attention. Just as in our original game, we have to worry about completing a progression in between or on either side of two already selected numbers. For example, we can’t take 4, because that would make 3-4-5; we can’t take 1, because that would make 1-3-5; and we can’t take 7, as that would make 3-5-7. Since 8 is safe, let’s make that our next move.

1    2    3    4    5    6    7    8    9

Things are about to get complicated. We still have the same concerns — completing a progression between or on either side of two already selected numbers — but there are many more progressions to keep track of. Now we have to worry about making a progression with three existing pairs of crossed-out numbers.

On the one hand, we have a good idea of what to expect. For each pair, we need to avoid moves that make a progression in the middle or on either end. But things aren’t as predictable as we’d like. The 3 and 5 eliminate three of our options: 1, 4, and 7. But the 3 and the 8 don’t eliminate any, since the numbers we must avoid, −2, 5.5 and 13, aren’t even on our board. And the 5 and 8 only eliminate 2, since neither 6.5 nor 13 is an option.

So we know that each choice we make will eliminate some future options, but just how many varies depending on what we pick. This irregularity makes it difficult to count all the possibilities and determine an upper bound for all possible game boards.

Back to our game. We see that 6 is safe, so we cross it out.

1    2    3    4    5    6    7    8    9

And this is the end: There are no more safe moves. We already know 1, 2, 4 and 7 are losers, and crossing out 9 makes the arithmetic progression 3-6-9. We’ve gone as far as we can in this game.

That means the set consisting of our safe moves, {3, 5, 6, 8}, is a Salem-Spencer set. But is it maximal? We know we can’t make this particular set any bigger, but could a different strategy produce a larger set? Is there a bigger subset of {1, 2, 3, 4, 5, 6, 7, 8, 9} that contains no three-term arithmetic progressions?

There is: {1, 2, 6, 8, 9} is a set of five safe moves in our game and is thus a Salem-Spencer set. And this is maximal, because it’s known that for {1, 2, 3, 4, 5, 6, 7, 8, 9}, the maximum size of a Salem-Spencer subset is 5. But for the general set with n elements, {1, 2, 3, …, n}, we don’t always know the answer. In fact, as of now, we only know the answer for n ≤ 209.

Mathematicians would like to know the exact size of the maximal Salem-Spencer subset of {1, 2, …, n}, but in general, the best they can do is establish bounds. Even this is difficult to do, in part because of the irregularity we saw above. Crossing out a new number might eliminate a lot of options, or only a few. You can see the irregularity in the charts below, which show the size of the largest possible Salem-Spencer subset of {1, 2, 3, …, n} for various values of n.

In our game where n = 9, the largest possible Salem-Spencer set is 5. But notice if we add the number 10 to our game board. That doesn’t increase the size of the largest possible Salem-Spencer set: It’s still 5.

On the other hand, going from 12 to 13 to 14 increases the maximum size from 6 to 7 to 8. But then you’d have to add six more numbers to the set to increase the size of the maximal Salem-Spencer subset by 1.

Results like Roth’s theorem and Szemeredi’s theorem establish bounds on the sizes of these sets and their variations, often using advanced mathematics (like ergodic theory and Fourier transforms) and huge numbers. For example, the Fields medalist Timothy Gowers, in his work on the more general Szemeredi’s theorem, established an important upper bound on the size of sets that contain no arithmetic progressions of length k. But if we want to compute the upper bound for our game, where n = 9 (the size of our board) and k = 3 (the length of the arithmetic progressions we’re trying to avoid), one part of our calculation would involve evaluating $latex 2^{4096}$, a number with over 1,200 digits!

While not exactly useful for our everyday lives, bounds like these give us some mathematical control over sets we still don’t fully understand. For example, until recently we had no such bounds regarding “polynomial sequences,” generalizations of arithmetic progressions that involve addition and raising to powers. It turns out that polynomial sequences, like 2+3, 2+3², 2+3³, and so on, are even harder to track than our simple arithmetic progressions, making the game of choosing subsets free of polynomial sequences even harder to understand. But establishing an upper bound is another step toward understanding, which is the mathematical goal in every numbers game.

Exercises

1. Prove that in a game using {1, 2, 3, 4, 5} under the original rules (loser is first to cross out three in a row of step size 1), the first player has a winning strategy.

Click for Answer 1:
If the first player crosses out 3, they can always win. If in response the second player crosses out 1 or 5, the first player crosses out the other of that pair, winning. If the second player crosses out 2, the first player crosses out 5; if the second player crosses out 4, the first player crosses out 1.

2. In a game using {1, 2, 3, 4, 5, 6} under the original rules, does either player have a strategy that guarantees victory?

Click for Answer 2:
The second player has a winning strategy. Suppose the first player chooses one of the numbers from {1, 2, 3}. The second player should then select a number from that same set next to the first player’s choice. For example, if the first player chooses 3, the second player chooses 2. The first player must now choose a number from {4, 5, 6}. Whichever number they take, the second player will have a winning move. If the first player initially chooses from the set {4, 5, 6}, the same strategy works for the second player, who should then also select from {4, 5, 6}.

3. Prove that in a game using {1, 2, 3, 4, 5, 6, 7, 8, 9} under the original rules, it is impossible to play seven safe moves.

(Hint: Divide the game board into the following subsets: {1, 2, 3}, {4, 5, 6} and {7, 8, 9}.)

Click for Answer 3:
Notice that crossing out the three numbers in any of the three subsets from the hint loses the game. With six moves we could theoretically play two moves in each of the three subsets. But whichever set the seventh move goes in will make three in a row and end the game. This argument is known as the pigeonhole principle: putting seven pigeons into three holes means at least one hole must have three pigeons in it. Notice the resemblance of this argument to the winning strategy in Exercise 2.

4. Find a maximal Salem-Spencer subset of {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}.

Click for Answer 4:
One strategy is to start with the numbers at the ends, since they can never be the middle of an arithmetic progression. So we take 1 and 11, which eliminates 6 as an option. Apply the strategy again and take 2 and 10, which eliminates 3 and 9 but no other options. From the remaining {4, 5, 7, 8} it’s possible to take two more, like 4 and 5. According to the table above, 6 is the largest possible Salem-Spencer subset.

This article was reprinted in Spanish at Investigacionyciencia.es.