Is there a way to simplify my thinking about the N towers of M heights game?

Question

To summarize the game, there are N towers of height M, on each turn the player can reduce a tower to a number that divides its height but doesn't equal its height, and the goal is to make your opponent have no possible moves when its his turn.

For example, if N=2,M=2 then the first player loses because the only moves he can do are to reduce one of the towers to height 1 after which the only move the other player can do is reduce the other tower to height 1 and now the first player has no moves to do.

I started writing this out, but it's getting too complicated for me to really see a "pattern" on the non-prime Ms such as 4. Is there are better way I should be thinking about this?

1 --> Lose
1 1 --> Lose
1 1 1 --> Lose
etc. 

2 --> Win
2 2 --> Lose
2 2 2 --> Win
2 2 2 2 --> Lose
etc. 

3 --> Win
3 3 --> Lose
3 3 3 --> Win
3 3 3 3 --> Lose
etc.

4 --> Win
4 4 --> Lose (see tree below)

                   4,4                        1's turn
                  /   \
                 /     \
                /       \
               /         \
              /           \
            2,4           1,4                 2's turn  
           / \  \         /  \
          /   \  \       /    \
         /     \  \     /      \
        1,4   2,2 1,2  1,1     1,2            1's turn         
       /  \    \     \           \
      /    \    \     \           \
     1,1  1,2   1,2    1,1        1,1         2's turn
          /      \
         /        \
        1,1       1,1                         1's turn

My way of calculating whether player 1 or 2 will win is like

static int Winner(int n, int m)
{
    if(m == 1)
        return 2;
    else if(IsPrime(m))
        return n % 2 == 0 ? 2 : 1;
    else
    {
       // ... ??
    }
}

EDIT: Wow, I just made a wild guess with

static int Winner(int n, int m)
{
    if(m == 1)
        return 2;
    else
        return n % 2 == 0 ? 2 : 1;
}

and it passed all the test cases of the challenge problem. So I "solved" it without understanding why.

Answer 1

The first thing to consider is that when you reduce a tower, dividing its height by one of its divisor (1 aside) is like removing one or more of its prime factors. If you represent each tower's height by the list of its prime factors, then the game just becomes a variant of Nim. On each turn, a player removes one or more of the numbers in one of these lists, and a player wins when he removes the last one(s).

Example game with 2 towers of height 6 :

Tower 1 (height 6) : 2 3  <- First player removes one
Tower 2 (height 6) : 2 3

Tower 1 (height 2) : 2
Tower 2 (height 6) : 2 3  <- Second player removes one

Tower 1 (height 2) : 2    <- First player removes one
Tower 2 (height 2) : 2

Tower 1 (height 1) : 
Tower 2 (height 2) : 2    <- Second player removes one and wins

Once you understand that, you just need to know how to win a Nim game with N heaps of M objects. And Nim has been mathematically solved for any number of initial heaps and objects.

Since, in your game, a player wins by removing the last prime factor, it is similar to the "normal play" of Nim where the player to pick the last object wins. In this case, the winning strategy is to finish every move with a nim-sum of 0, the nim-sum being the exclusive or of the number of objects in each heap. Read the Wikipedia page for more information and examples. When the game's nim-sum is not 0, it is always possible to make a move that makes it 0. It is impossible otherwise. Therefore, starting a game with a 0 nim-sum means that the first player wins, otherwise the second player wins.

In your case, if the number of towers at the start of a game is even, then the nim-sum is 0 because the towers all have the same height, and the first player wins. Otherwise, if the number of towers is odd, then the second player wins. The only exception is for a height of 1 (which would be an empty Nim game), which makes the second player win by default.

That is why your "wild guess" worked.