World's most popular travel blog for travel bloggers.

[Solved]: Reccurrence for the game of pile of stones

, ,
Problem Detail:

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.

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