Players A and B play the following game. Two integers, m and n, are written on the board. On each turn, a player selects one of the numbers on the board, erases it, and writes down a positive divisor of that number as long as it is different from any of the other numbers written on the board. For example, if 10 and 17 are written on the board, you can erase 10 and write 2 in it's place.
Suppose m = 2^40, n = 3^51. Assume that A goes first. Determine which player is always able to win the game, and explain the winning strategy.
My logic:
One can always write 1 as a divisor, as it divides both numbers and, in essence, is a legal move. Due to the restriction of only being able to write down a number if it is different from all the others, we can express the changing nature of the given numbers, m and n, as such:
if m = 2^40, you can write 2^39, 2^37, 2^34, and so on. The powers decrease by an increasing amount.
If we reduce each number, m and n, by this rule of decreasing powers, we end up with 2^4 and 3^6. Having used all previous divisors such as 2 and 3, we can no longer go on and the game pretty much ends there. Therefore, (16, 729) is a winning position, where 16 refers to the m value, and 729 refers to the n value.
I don't know where to go on from there. I would appreciate some help with this question.
Thank you!
This is an impartial game, which means it is Nim in some disguise. You have to discover how big the heaps are. You have already found that for a prime power, $p^n$, the heap is of size $n-1$. Now you have to think about how big a heap that has more than one prime factor is. A good start is what is the maximum number of moves if the pile starts with $12=2^2\cdot 3$?