Problem of the Week #1 Solution

First, a reminder of the problem:

Problem: The number 10²⁰⁰⁷ is written on the blackboard. Anne and Berit play a two-player game in which players alternate performing one of the following operations:

1. Replace any number x on the blackboard with two integers a, b > 1 such that ab = x.

2. Erase one or both of any two equal numbers on the blackboard.

The person who first cannot perform any operations loses the game.
Who has the winning strategy if Anne moves first, and why?

Solution: We’ll show that Anne has the winning strategy by using the idea of mirroring moves. Mirroring moves is a nice technique for producing winning strategies in games. Let’s start with a simple classic example.

Consider a game in which players alternate placing knights on a standard chessboard, with the requirement that each new knight be placed on a square that is not under attack from a knight already on the board. There’s a simple strategy that gives the win to the second player. Draw a line down the middle of the board, horizontally or vertically. Then after each move made by the first player, the second player takes the square played on by the first player, reflects it across the line in the middle of the board, and plays a knight on that reflected square.

The reflected square is always a legal play. Note first that given the simple strategy, after the second player’s move, the board is always symmetric about the dividing line. So when the first player plays on a square, since that square isn’t attacked by any knight on the board, its mirror image square across the dividing line also isn’t attacked by any knight on the board.

That’s almost enough to show that the mirror image square is safe for the second player. But it’s not quite enough. The mirror image square isn’t attacked by any knight that was on the board before the first player made their move. But what if it’s attacked by the knight that the first player just added? (Remember that that knight temporarily breaks the symmetry of the board.)

But it’s not hard to see that this can’t happen. Because of the shape of knight moves, no knight can attack the square that’s reflected across the middle line from it, since that square is in a straight line from it. (That’s why we use knights in this game. The same strategy wouldn’t work for rooks or queens, which would attack the square mirrored from them.) So the mirror image square must be safe, and the second player can play there.

This means that the second player always has a move available after the first player plays. No matter where the first player plays, the second player can play in the mirror imaged square from there. Since the second player always has a move after the first player plays, the second player can’t be stuck without a move, and so can’t be the one who loses the game. Thus it must be the first player who eventually loses.

OK, so much for the simple example. Now let’s turn to the question of how mirroring moves helps in our problem. The first thing to note is that mirror moves usually lead to a winning strategy for the second player. That’s because the winner is the one that does the mirroring, and to do the mirroring, you need to follow someone else’s move, so that you can mirror it.

To make mirroring moves work to the advantage of the first player, what we need is an approach on which the first player initially makes a move that splits the game into two subgames. Then the second player can play in one of those games, and the first player will from then on mirror the second by playing in whichever game the first player didn’t play in. (Notice that in our initial knight example, we didn’t a move to split the game into two subgames. We just put an imaginary line down the middle of the board.)

The first player’s initial move, then, should be to replace 10²⁰⁰⁷ with the two numbers 2²⁰⁰⁷ and 5²⁰⁰⁷. This makes two subgames – call them the 2 game and the 5 game. The second player then has to play in one of the two subgames. If the second player plays in the 2 game, the first player makes the corresponding move in the 5 game, and if the second player plays in the 5 game, the first player makes the corresponding move in the 2 game.

Two things remain to be sorted out:

1. What counts as “the corresponding move”? A move is either (i) replacing a number with a pair of its factors, or (ii) removing one or two of two identical numbers. But within the 2 game, every number that can appear is a power of 2, so we can just identify numbers by what power of 2 they are. And within the 5 game, every number that can appear is a power of 5, so we can just identify numbers by what power of 5 they are. So if the second player replaces some 2^a with 2^b and 2^c, where b + c = a, then the first player replaces 5^a with 5^b and 5^c. (Because the two games will always be symmetric prior to the second player’s move, if 2^a occurs in the 2 game, then 5^a occurs in the 5 game.) And if the second player removes one or two occurrences of 2^a, then the first player removes the same number of occurrences of 5^a. (And vice versa, if the second player plays in the 5 game.)

2. Do the two games really remain symmetric? The only danger here is that some move is made that affects both games. As long as each move affects only one game, then the first player’s mirroring move will always restore symmetry. The first sort of move – replacing a number with a pair of its factors – always affects only one game. Any factors of numbers in the 2 game are again factors of 2, and remain in the 2 game. Any factors of numbers in the 5 game are again factors of 5, and remain in the 5 game. For the second sort of move – removing repeated numbers – to affect both games, we’d need a number that appeared in both games. But there is no number (other than 1, which can’t appear in the game) which is both a power of 2 and a power of 5. So numbers can’t be repeated across the games.

So the first player can always mirror the second player’s move. That means the first player can’t be left without a move, and so the first player can’t lose the game. Thus the first player has a winning strategy.