Factorization game, can we find winning strategy?

Question

I'm thinking about a game theory problem related to factorization. Here it is,

Q: two players A and B are playing this factorization game. At very first, we have a natural number $270000=2^4\times 3^3\times 5^4$ on a chalkboard.

in their own turn, each player chooses one number $N$ from the chalkboard and erase it, and then write down new two natural numbers $X$ and $Y$ satisfying

(1) $N=X\times Y$ (2) $gcd(X,Y)>1$ (So, they are "NOT" coprime)

a player loses if he cannot do this process in his turn.

So, in this game, possible states at $k$-th turn are actually sequence of natural numbers $a_1,a_2,\dots,a_k$ with $a_i>1$ and $a_1\times a_2\dots \times a_k=270000$

EXAMPLE of this game)
A's turn-$2^{4}\times3^{3}\times5^{4}$
B's turn-$2^2\times3\times5^2,2^2\times3^2\times5^2$
A's turn-$2^2\times3\times5^2,2\times3\times5,2\times3\times5$
B's turn-$2\times5,2\times3\times5,2\times3\times5,2\times3\times5$
So B loses in above case.

Actually, in this game, the first player(So, A) has winning strategy.
What is this winning strategy for A?

-Attempted approach: I tried to find what is "winning position" and "losing position" for this combinatorial game. but classifying these positions were not so obvious.

What is A's winning strategy? Thanks for any help in advance.

Answer 1

This is nim in disguise. I suggest you represent a pile by a sequence of the exponents of the primes, so $270000$ would be represented by $(4,3,4)$ You can then sort the starting numbers in order, as $(4,4,3)$ would play exactly the same. A legal move is replacing a sequence with two sequences such that: the sum of the corresponding positions in the new sequences matches the number in the original sequence and at least one position of the new sequences is greater than zero in both. For example, from $(4,3,4)$ you can move to $(2,3,4)+(2,0,0)$ or to $(3,2,1)+(1,1,3)$ or to $(4,1,2)+(0,2,2)$, but not to $(4,3,0)+(0,0,4)$. You are trying to find the nim values of various positions.

I would start with single position sequences, so the original number is a prime power. $(1)$ is a losing position, so is $*0$. $(2)$ is clearly $*1$ as you have to move to $(1)+(1)$. $(3)$ is losing, so is $*0$. $(4)$ is $*1$ because you can only move to $*0$. From $(5)$ you can only move to $*1$, so it is $*0$ and losing. A single even pile is winning as you can move to two piles half the size, then mirror your opponent's play, so is $*0$. A single odd pile is losing and is $*1$.

I claim that as first player I can win any game of the form $(a,b)$ with $a\gt 1, b \gt 1$. The point is that an entry of $0$ in a sequence is equivalent to an entry of $1$ as neither can be divided and neither can provide the matching entry. I will move to either $(a,1)+(0,b-1)$ or to $(a-1,1)+(1,b-1)$, whichever makes the large numbers have the same parity. Then I either leave $*0+*0$ or $*1+*1$, both of which are $*0$ and losing for my opponent.

I believe a similar argument can be made for longer sequences, but have not fleshed it out. You can kill off one of the entries of the sequence by leaving $0$ or $1$ in that location in one of the daughter sequences and one of them will win.

Answer 2

It seems from your question that you might only be interested in the case of $270000$. One winning move in $270000=2^{4}\times3^{3}\times5^{4}$ is for $A$ to split it into $1350,200$ $=\left(2^{1}\times3^{3}\times5^{2}\right),\left(2^{3}\times3^{0}\times5^{2}\right)$. After that, any splitting $B$ does in one of those factors can be mirrored (splitting a power of $3$ instead of $2$ or vice versa) in the other, and future moves by $B$ can be mirrored as well (the subfactor of $2$ in $1350$ doesn't affect anything since it can never be split).

For example, if $B$ moves in the $200$ component to $\left(2^{1}\times3^{0}\times5^{0}\right),\left(2^{2}\times3^{0}\times5^{2}\right)$ then $A$ can move in the $1350$ component to $\left(2^{1}\times3^{1}\times5^{0}\right),\left(2^{0}\times3^{2}\times5^{2}\right)$. Since $A$ can always mirror a move by $B$, $A$ won't be left in a position without a move.

There are other winning moves for $A$ like $27000,10$ and $7500,36$, but it is more difficult to prove that they are winning, since there is no longer a straightforward mirroring strategy to follow.

If you were asking about the general case of an arbitrary starting number, things get a bit tricky (and please clarify in your question). Ross Millikan's answer contains a strategy for the first player to win when they can in the one and two prime case, but this doesn't generalize well. In particular, $27000=2^{3}\times3^{3}\times5^{3}$ is a losing position (though this is not obvious). It may be essentially the only nontrivial losing position, but I have not quite proved this yet. (I've been working on typing up my results in the general case, but they will be several pages long and I'm not sure an MSE answer is the best venue.)