9
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What do you mean by "chooses one number $N$ from the chalkboard and erase it"? The example is not quite enlightening. $\endgroup$ – Patrick Da Silva Feb 26 '16 at 20:20
  • $\begingroup$ Your notation is unclear in that when you write $25$ you mean $2 \cdot 5=10$. Clearly the bases do not matter, they could be any primes. The numbers can be represented by the exponents, so you start with $(4,3,4)$. A move is to split a sequence into two sequences such that the sum of the two numbers in each position matches the first sequence and there is at least one position with a number greater than $0$ in both sequences. $\endgroup$ – Ross Millikan Feb 26 '16 at 20:26
  • $\begingroup$ @ Suntaek : make more efforts, your "game" is impossible to understand. a game is like a function defined by recurrence, but here you didn't describe what the $n$th state was supposed to be $\implies$ bad $\endgroup$ – reuns Feb 26 '16 at 20:36
  • $\begingroup$ @Ross Millikan I changed notation. yes. your interpretation using exponents is correct. $\endgroup$ – KGEO Feb 26 '16 at 20:37
  • $\begingroup$ Is 270000 the only case you are interested in, or do you care about general facts about this game? Also, what is the source of this problem (presumably a contest)? There's a lot to be said about the general case, but I want to make sure that there's not, say, already a paper on this game. $\endgroup$ – Mark S. Mar 13 '16 at 17:30
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I hope to post an answer with my findings in the next few days, but I think your conjecture at the end is false. I believe $(3,3,3)$ is actually a win for the second player. $\endgroup$ – Mark S. Mar 4 '16 at 19:26
1
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.