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.
