Divisor nim

Yesterday in math club I had the students play a game which I dimly remember seeing somewhere but forget where. Since I don’t know what it is really called, I’m calling it “divisor nim”. Here’s how it works:

  1. The players pick a positive integer.
  2. The two players work together to write down all the divisors of the chosen integer (being sure to include 1 and the integer itself).
  3. The players now alternate moves as follows: on a player’s turn, she must choose one of the divisors d, and then cross out that divisor as well as all of the other listed numbers which are divisible by d.
  4. On subsequent turns, players may only choose numbers which are not yet crossed out.
  5. Whoever is forced to choose 1 (because it is the only number left) is the loser!

For example, suppose the chosen number is 12. We write down the divisors of 12:

1, 2, 3, 4, 6, 12.

Now suppose the first player chooses 4 (actually, this is a bad move; I’ll let you figure out why); they then cross out 4 and 12, since 12 is divisible by 4. The game now looks like

1, 2, 3,  4 , 6,  12 .

Now it’s the other player’s turn; suppose they pick 3 (this is actually a bad move too…!), so they cross out 3 and 6. Now the game looks like

1, 2,  3 ,  4 ,  6 ,  12 .

The first player now crosses out 2, and the second player is forced to choose 1, so the first player wins.

The kids thought this was a lot of fun and it leads to all kinds of interesting discussions. First, of course, you have to figure out how to write down all the divisors of the starting number (how do you know when you’ve listed them all? what are some systematic strategies for listing the divisors?). Then you can talk about strategies for playing the game. I might talk about some of these things in some future posts. For now I will just note that this actually has some deep connections to the theory of posets (we are basically just using each integer as an abbreviation for its poset of divisors). Although I’ve played around with it a bit I don’t yet know of a general strategy — although any particular starting integer necessarily gives a winning strategy for ONE of the two players, and it’s not too hard to figure it out by working backwards. More on this later, I suppose.

In the meantime, have fun playing!

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in games, number theory, pattern and tagged , , . Bookmark the permalink.

2 Responses to Divisor nim

  1. Michael Lugo says:

    For numbers with only two distinct prime factors (like 12, with prime factors 2 and 3) this is a disguised version of Chomp.

  2. Joshua Zucker says:

    There’s a simple strategy-stealing argument that shows the 1st player always has a forced win (well, except when the game starts with just the number 1).

    However, like most strategy stealing arguments, it doesn’t tell you anything about HOW to win.

Comments are closed.