A fun number elimination game: who will win?

Bored at the airport, Alice and Bob decide to play the following mathematical game.

Alice writes the numbers 1, 2, . . . , N on a piece of paper.

Bob goes first, and he picks two numbers x and y from the list. Bob crosses out these numbers from the sequence, and he includes a new number equal to their positive difference (in other words, he puts |x – y| on the list).

Alice takes her turn and does the exact same thing with the remaining numbers on the list.

Bob and Alice continue to play, in turn, until there is only one number left.

Alice wins if the final number is odd, and Bob if even.

1. What strategy should Alice and Bob have for the game?

2. Is there a winning strategy?

Give the game a try before you read the solution below.

Solving the game for 1, 2, 3

Let’s work through an example to see how the game might play out.

Suppose Alice just writes the numbers 1, 2, and 3 in the initial list.

Bob can choose any two numbers, which means he can make any of the following three moves:

–if he chooses (1, 2) the resulting list is 1, 3

–if he chooses (1, 3) the resulting list is 2, 2

–if he chooses (2, 3) the resulting list is 1, 1

Alice will simply have to pick the two numbers that are remaining, and the results will be as follows:

–if the list was 1, 3 the resulting number is 2 (which is even so Bob wins)

–if the list was 2, 2 the resulting number is 0 (which is even so Bob wins)

–if the list was 1, 1 the resulting number is 0 (again an even number, so Bob wins)

This worked example shows Alice will lose the game regardless of how she or Bob choose to play.

But why is that?

And are there games that Alice can win?

The trick to solving the game

The trick is to notice what is happening on each turn of the game.

In the version with the numbers 1, 2, 3 worked out above, we can notice something interesting about the sum of the numbers in the list.

The original sum of all the numbers is 6, an even number.

When Bob moves, the resulting sums can either be 4–if he picks (1, 2) or (1, 3)–or the sum can be 2–if he picks (2, 3). In either case, the sum of the numbers is even.

And after Alice moves, we showed the resulting number must be even as well, which is why she loses.

This suggests a pattern: the final number, as well as every intermediate sum, will have the same parity (the property of being odd or even) as the sum of the original list.

If true, that means Alice wins if the original list has an odd sum, and Bob wins if the original list has an even sum.

But how can we prove this is true?

Proof that parity is unchanged / invariant

Suppose the original sum of the numbers is labeled S.

On Bob’s turn, he removes two numbers x > y from the list, and he writes another number (x – y).

This means Bob’s action reduces the original sum S by the following:

x + y – (x – y) = 2y

The thing to notice is that 2y is an even number, which means the parity of the sum is unchanged by a move in the game. In other words:

–If the original sum S was even, then each turn it is reduced by an even number. As an even minus an even is also an even number, this means every intermediate sum will be an even number. Hence, the final number must be even as well.

–If the original sum S was odd, then each turn it is reduced by an even number. As an odd minus an even is an odd number, this means every intermediate sum will be an odd number. Hence, the final number must be odd as well.

Answering the original questions

1. What strategy should Alice and Bob have for the game?

This is something of a trick question.

Alice and Bob have no particular strategy for play: the game is decided by the parity of the sum of the initial list.

Note that if the initial list is 1, 2, 3, . . ., N, then its sum is N(N+1)/2. The parity of this number decides who wins the game.

2. Is there a winning strategy?

Again this is a trick question as the moves are irrelevant to the outcome.

Arguably, the winning strategy is to influence the choice of the initial list, and hope the other person doesn’t notice.