2
$\begingroup$

I am trying to solve this question from Project Euler for past few days: Divisor game. The problem is as follows:

Two players are playing a game. There are $k$ piles of stones. When it is his turn a player has to choose a pile and replace it by two piles of stones under the following two conditions:
1.Both new piles must have a number of stones more than $1$ and less than the number of stones of the original pile.
2.The number of stones of each of the new piles must be a divisor of the number of stones of the original pile.
The first player unable to make a valid move loses.

Let $f(n,k)$ be the number of winning positions/configurations for the first player, assuming perfect/optimal play, when the game is played with $k$ piles each having between $2$ and $n$ stones (inclusively). Then find $f(10^7,10^{12}).$

What I tried

  • The first thought upon seeing the number of piles to be $10^{12}$, is that somehow matrix exponentiation is involved, with a linear recurrence being obtained on the number of piles $k$ for some fixed $n$.
  • The second thing which can be observed is that if I have $k-1$ piles of stones with each pile having stones between $2$ and $n$. And this configuration is denoted by $S_{k-1}$, then if I have two numbers $a=q_1^{r_1}q_2^{r_2}...p_x^{r_x}$ and $b=s_1^{t_1}s_2^{t_2}...s_y^{t_y}$ ( where I have written the prime factorization of $a$ and $b$ ) such that $r_1+r_2..+r_x=t_1+t_2..+t_y$ then either both the configurations $S_{k-1}a$ and $S_{k-1}b$ are loosing configurations or both are winning configurations ( where $S_{k-1}a$ means I have added a pile with $a$ stones to the configuration $S_{k-1}$ ).
  • Based on the the above two points I tried the following approach. Let $L_{k-1}$ and $W_{k-1}$ be the number of loosing and winning configurations respectively, where each configuration has $k$ piles, with each pile having between $2$ and $n$ stones ( inclusive ). Also let $P$ and $C$ represent a prime and a composite number respectively, between $2$ and $n$ ( inclusive ). Then it is easy to note the following:

  • $L_{k-1}P$ is a losing configuration with $k$ piles, last pile having $P$ stones.

  • $W_{k-1}P$ is a winning configuration with $k$ piles, last pile having $P$ stones.

  • $L_{k-1}C$ is a winning configuration . The reason is: as $C$ is a composite number it has a prime divisor $p$. The first player chooses the last pile ( $k$th pile ) having $C$ stones and replaces it with two piles each having $p$ stones. Now its the second players chance and he is left with configuration $L_{k-1}$ which is loosing configuration ( the second player can't choose the two newly form piles as they cannot be broken down further as they have prime number of stones ).

  • The problem comes here as $W_{k-1}C$ can be a winning or a loosing configuration. For example let $k=2$ and $n=10$ then it can be seen that a single pile having $4$ stones is a winning configuration. And also it is easy to see that $\{4,4\}$ is a loosing configuration whereas $\{4,8\}$ is a winning configuration ( where $\{4,8\}$ means two piles, first having $4$ stones and second having $8$ stones). So I am unable to move forward in this case.

I still suspect it is a matrix exponentiation question. But I guess it cannot be done just keeping variables $W_{k-1}$ and $L_{k-1}$. How do I proceed ?


PS: As this problem is from project Euler I would appreciate only hints.

$\endgroup$
  • $\begingroup$ In an optimal play each configuration is winning or losing. By optimal play it means if a player has a strategy that he will win no matter what steps the other player takes, then this configuration is winning for first player. $\endgroup$ – sashas May 15 '16 at 17:28
  • $\begingroup$ I do not see those matrices, it looks like dynamic programming with counting cases instead of evaluating them. I have not tried to solve it yet (as I an reading description now) but the very first thing that comes to mind is to evaluate the end game up to start counting similar cases (the order does not matter) and since the only winning count matters, those are the only evaluated, but after actual trial I may revoke this (it seems feasible and fast now). Something like reverse game tree. And yeah, the reduce in branching is something I am after right now. $\endgroup$ – Evil May 15 '16 at 17:34
  • $\begingroup$ As you can see if I am able to obtain linear recurrence on $k$ I can apply matrix exponentiation. As it it just solving the recurrence quickly ( if linear ). But as I have pointed out I am unable to obtain a recurrence for the last case. $\endgroup$ – sashas May 15 '16 at 17:37
  • $\begingroup$ Did you solved it for given value? Have you consider combinatorics, counting results? Primes are helpful but when you solve for one ply, you still have to think about combining results with other plies, and I do not have any idea about the question you give, I do not know what matrices should represent and how would you think of recurence, when parity of plies changes the result e.g. winning for $2$ plies is losing for $3$. I can help you with different approach as I do not see working scheme for this one. $\endgroup$ – Evil May 16 '16 at 4:15
  • $\begingroup$ If you reduce all possible plies sizes into possible outputs (0 moves, 1 move, [0, 1, 2] moves etc.) you end up with numbers that you havevto combine into winning strategy, the obvious part is discarding no_moves and taking 1_moves, what next? Every time you can split into unknown outcome, you have to give a pair to counteract (if I split 8 into 4, 4 it is good for me because those are two moves, so you also want to have such oportunity, if you don't I take 2,2 and win. This is dynamic programming to build such $number~of~moves$ table (and build only once per number) and then count combined $\endgroup$ – Evil May 16 '16 at 6:29
2
$\begingroup$

AS I asked for hints only, apart from the hints I have provided one can solve the question with grundy numbers.

$\endgroup$
  • $\begingroup$ Yeah, it seems legit from all Nim kinds of games and afaik this kind of subproblems are called nimbles. It's a pity though, one could achieve very similar results from scratch (I checked that), but this falls to reinventing the wheel. So it seems that the problem is solved, working theory behind is found and probably no more answers will come, so maybe you should accept? $\endgroup$ – Evil May 16 '16 at 21:49

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.