Question: Two players starts with the number N and play in turns. In each turn the player chooses a prime power p^m>1, which divides N and updates N to be N/(p^m). The player who sets N to be 1 - wins. What are all the winning moves from the initial state of N=1,506,009,006,001,500,000,000 ?
Answer:
N = 1,506,009,006,001,500,000,000 = (2^8)*3*(5^9)*(7^4)*(11^4)*(13^4) (Prime Factorization of N)
Assuming that A and B are the players.The problem reduces to find winning strategy for players A & B with a set of numbers (exponents of prime factors of N in the question) written as a set (8,1,9,4,4,4) = N, where any individual member of set can be reduced whole or part in an individual move (eg: N/p^m can again be factorized and written as a set, which will reduce the exponent of "p" in resultant number by "m") and the first person to reach (0,0,0,0,0,0) wins the game.
If we assume that player A is the first mover, then A can execute a strategy which guarantees his win. (or First mover can win the game if the player plays with the following strategy)
Strategy -
Step 1: A's first move - Divide N by 13^4 (or equivalently can divide by 7^4 or 11^4 as first move)
Step 2: Express the exponents of each of prime factors of the resultant number in binary format. For any move by B to reduce the primary factor of any of the number (by division), A could divide by a calculated factor of the number (N) so that XOR sum of the binary representation of all the exponents of factors of the resultant number is 0000 (XOR sum without carry -> 1+1 = 0, 0+0 = 0, 1+0 = 1, 0+1 = 1 eg: 1+1+1+1 = (1+1)+(1+1) = 0+0 = 0)
Reasoning for the logic: The final desired state of winning position can be represented by 0000 (Winning position). As a first mover, A divides by a calculated number so that the XOR of sum of binary representation of the prime exponents of the resultant number is 0000. Whenever it is A's turn to play, he makes sure that whatever move B makes, player B can never win because he is disturbing a winning position 0000 (set by A in previous move). It can be proved that A can always find moves to move to a winning position (here 0000 represented as the XOR sum of binary representation of individual prime exponents) whatever move B plays. And B can only move to a "non winning" position by his play.
Step 3: Continue Step 2 until B is forced to execute (0,0,0,0,1,1)->(0,0,0,0,0,1) (or any related non winning move) from where A can divide the resultant N by the lone prime factor to win the game
Demonstration:
All winning moves can be listed with this logic. But I feel that it is only necessary to state the winning logic for any move by the second player. A possible demonstration of the game is represented below resulting in A winning the game is STEP 5. N0 is the initial number. Ni(A,B) is the result of the i th step of A or B respectively. The above result is quite general and can result in winning solution for any generalized such game.
Note: The solution was inspired from an article on NIM game from the book "Adventures in problem solving" by Shailesh Shirali, published by University Press, India
| Steps | Player A | Player B |
| 1 | N1A=N0/13^4 | N1B=N1A/7^2 (B divides by 49) |
| 2 | N2A = N1B/9^2 (Then A divide by 81) | N2B = N2A/2^7 (B divides by 128) |
| 3 | N3A=N2B/5^9 (Then A divides by 195,312,5) | N3B=N3A/7^2 (B divides by 49) |
| 4 | N4A = N3B/9^2 (Then A divides by 81) | N4B=N4A/3 (B is forced to divide either by 2 or 3 which she does by 3) |
| 5 | N5A=N4B/2 = 1 and A wins the game (Then A divides by the remaining lone factor 2 and wins the game) | |
