Monday Puzzle: Alice and Bob race to 1 million

This is a fun game in which Alice and Bob race to 1 million in a mathematical sense.

Alice and Bob start with the number 1. Alice multiplies 1 by any whole number from 2 to 9. Bob then multiplies the result by any whole number from 2 to 9, and the game continues with each person moving in turn.

The winner is the first person to reach 1 million or more.

Who will win this game? What is the strategy?

Give it a try before reading the answer below.

The game of Nim

The puzzle is a variation of a game you have probably played before called Nim.

Nim usually is presented as follows: there are two piles of objects (like matchsticks), and each person can remove a certain number of objects (like 1, 2, etc) from each pile. Often the person who picks the last object is the loser of the game.

Nim is a completely solvable game, and I will refer you to this article or this one for details on Nim.

The way to solve Nim is to use backwards induction, precisely the same method that can solve today’s puzzle.

Backwards induction

My first attempt to solve this game demonstrated a common mistake in solving this type of puzzle. My initial attempt was to simulate the game and look for a pattern in how Bob might be able to force a certain product. This is not wrong necessarily, but it is a lot harder to see the pattern.

I then realized the game should be solved in reverse using backwards induction. The thought process is like this.

Let’s imagine that we win the game, and that we are the player that sends the total beyond 1 million. The questoin is this: if we were able to bring the total above 1 million, what possible move could have gotten us there? That is, what number did we use to multiply the previous total by, and what previous totals would have allowed us to win?

Clearly one possibility is 500,000. If we were presented with that number, we could multiply it by 2 and get to 1 million. In fact, if we were presented with any total 500,000 or higher, then we could win by multiplying by 2. This shows that if we receive a number 500,000 or higher, then we can win the game. We can thus say that any number 500,000 or higher is a winnable number.

We can then ask, what other numbers are winnable numbers? In the game, we are allowed to pick any whole number from 2 to 9. Since the highest number we can pick is 9, we will use this to find the lowest number that will let us win. We can calculate that 111,112 times 9 is just over 1 million.

Therefore, any number from 111,112 to 999,999 is a winnable number.

Repeat the logic to solve the game

Now comes the interesting part. We know that if we being a turn with any of those winnable numbers, WE win the game. The question is: what numbers came before that? What numbers, for which our opponent begins a turn, would force them to bring the total to a winnable number for us?

One example readily comes to mind: 111,111. If our opponent started with this number, the only options are to multiply it by a number from 2 to 9. The lowest total that will result is 222,222 and the highest total is 999,999. Regardless of what the opponent does, the resulting number is a winnable number for us. We can say therefore that 111,111 is a losable number.

What other numbers are losable numbers? We are looking for a range of numbers that will force someone to produce a result in a winnable number range. As each player has to multiply by a minimum of 2, we can find the lower range. We can calculate that 55,556 is half of 111,112.

Therefore, any number from 55,556 to 111,111 is a losable number.

Generalizing the process

We can continue reasoning. If we know the numbers 55,556 to 111,111 are losing numbers, what number range would allow a player to bring an opponent into the losable number range? These numbers would therefore also be winnable numbers.

As we reasoned above, to calculate winnable numbers we divide the lower bound by 9, and to calculate losable numbers we divide the lower bound by 2. (We need to round up after any division since the game will only have integers)

We find the following ranges are winnable and losable:

111,112 to 999,999 –> winnable
55,556 to 111,111 –> losable
6,173 to 55,555 –> winnable
3,087 to 6,172 –> losable
343 to 3,086 –> winnable
172 to 342 –> losable
20 to 171 –> winnable
10 to 19 –> losable
2 to 9 –> winnable
1 –> losable

Here is a pictorial representation of the backwards induction process.

Solution: Alice should always lose

Alice begins the game with 1 which we reasoned above was a losable number. When she presents any of the numbers 2 to 9 to Bob, he can force the total into the losing range of 10 to 18. Whatever Alice does, Bob can continue to control the resulting total so that he will win.

That’s not to say that Bob will win definitely win the game. With sloppy play, Bob can make a mistake and let Alice win.

For instance, suppose Alice starts with 9. If Bob multiplies that total by 9 to get to 72, then he has given Alice a winnable number which would allow her to control the game.

In some ways I like this multiplicative version of Nim more than the usual additive game.

Try it with your friends some time using a calculator on your cell phone–obviously let your friend go first. They’ll never know what hit them.