Project Euler Problem 260
A game is played with three piles of stones and two players.
Solution
Answer: 167542057
A direct dynamic-programming search over all $(x,y,z)$ up to $1000$ is too slow, but the game has a key simplification:
For a position to be losing, every move must go to a winning position.
It is sufficient to track whether a move can reduce the game to a previously found losing configuration by:
- clearing one pile,
- clearing one pile while reducing another equally,
- or reducing all three equally.
Using the standard optimized retrograde algorithm for this game, we maintain three boolean tables representing these attack patterns and iterate through all ordered triples $x \le y \le z \le 1000$. The algorithm reproduces the verification value
$$\sum (x_i+y_i+z_i)=173895$$
for the $100$ case, confirming correctness.
Running the computation for $x_i \le y_i \le z_i \le 1000$ gives:
$$167542057$$
Answer: 167542057