Andi's Factor Game

Two weeks ago, my friend Andi messaged me about a mathematical game she had invented.  She was so excited to share it.  She had coded up a "proof of concept" version in html, and had come up with a mathematical proof about its winning strategies.  She was enthusiastic about its potential to make math fun even for non-math people, and full of ideas for next steps.

Then two days ago, I learned that Andi died.  It seems that this game is one of the last things she put into the world.  Although I didn't know her as well as I might have, her excitement about sharing this game seems to typify the passion and determination with which she approached all her projects.  Andi was an uncompromising advocate for social justice with a poetic eye and a keen sense of humor. Also, she was a transgender woman; I say this because visibility matters and because I believe she would not want this aspect of her identity to be erased.

The best way I can personally think of to honor Andi's memory is to share her final game with the world.  Like any well-designed game, it is easy to play but difficult to master. The rules are deceptively simple:

1. A large whole number, called the Magic Number, is specified and known to both players (it could be randomly generated by computer, for example). All factors of the Magic Number are listed out, including 1 and the number itself.
2. Two players take turns choosing factors of the Magic Number. Every time one player chooses a factor, that factor and all multiples of it are crossed out. Once a factor has been crossed out, neither player can choose it.
3. Whoever chooses 1 loses. In other words, the goal is to eliminate the factors in such a way that the other player is forced to choose 1.

For example, let's say the Magic Number is 12.  The factors of 12 are 1, 2, 3, 4, 6, and 12.  These are all the numbers that can be chosen.

Say player 1 choses 12 itself.  Then 12 is eliminated, so the "board" looks like this:

1 2 3 4 6 12

Now player 2 chooses 3.  So 3 and all multiples of 3 are crossed out:

1 2 3 4 6 12

Next player 1 chooses 2.  So 2 and all multiples of 2 are crossed out:

1 2 3 4 6 12

Only the number 1 is left. Player 2 is forced to choose 1, so Player 1 wins.

To visualize what's happening in this game, it helps to draw a diagram like this:

Every time you a player picks a number, that number and all numbers downstream of it are eliminated. (Here "downstream" refers to the direction the arrows are pointing, which is visually upwards.)  So, if 2 is picked, that eliminates 2, 4, 6, and 12. 

To mathematicians, a diagram like this is called a lattice. The game-play for a given Magic Number is determined by the structure of the lattice, which in turn is determined by the Magic Number's prime factorization, as you can see in this lattice for 120.

But enough theory, go ahead and play!  Here's a link to the "proof of concept" version that Andi coded up.  You play against the computer, who goes first.  To try again with a different Magic Number, click "New Game". You can put in whatever Magic Number you choose, or have the computer randomly pick one.

Did you win? No, you didn't. But don't feel bad: Andi proved that, with optimal play, Player 1 will always win the game.

It's a proof by contradiction.  Assume, for the sake of contradiction, that for some particular Magic Number, Player 2 has a winning strategy. In other words, Player 2 has a winning response to any first move that Player 1 might make.  In particular, if Player 1 chooses the Magic Number itself, Player 2 must be able to choose some other number—call it n—which puts them in a winning position.  But then Player 1 could have chosen n as their first move, which would have put Player 1 in this same winning position.  This contradicts our assumption that Player 2 has a winning response to any first move of Player 1.  Therefore, by contradiction, Player 1 must win if both sides play perfectly.

The interesting thing about this proof is that it's non-constructive. It says that there exists a winning strategy for Player 1, but gives no indication of what this winning strategy might be!

Andi designed her code to search through all possible game outcomes for a winning one. While this guarantees that the computer always wins, it doesn't give much insight into how one ought to play, or why certain strategies might work better than others.

There are many interesting open questions here: Can the winning strategy be described concisely? Is there a polynomial-time algorithm to find the winning strategy for a given Magic Number? And can the game be generalized to other kinds of lattices?

Andi's final gift to the world is a good one.  Her code is available on GitHub; please use it and build on it if you are inspired. I hope she is remembered for this and for everything else she put out into the world.

I'll close with this mathematical meditation, which was one of Andi's last Facebook posts:

The set of rational numbers is continuous, in the sense that between any two distinct rational numbers, there exist more distinct rational numbers. If you only look at the rationals, you'll miss uncountably many reals. If you insist on defining reals in terms of rationals, you'll need to take rationals to their limits.

Rest in Power.