Question: Consider a game with k piles of coins. Two players alternate turn. In each turn, they must remove some non-zero number of coins from one of the piles.
The player who takes the last coin loses.
An initial configuration is a sequence of values (P_1, P_2, ..., P_k) which show that pile i has P_i coins in it. We call such a configuration winning if the first player to act can force a win (i.e., force the other player to eventually take the last coin).
Program: Write a polynomial-time algorithm that, given an initial configuration (P_1, P_2, ..., P_k), decides if it is a winning configuration.
Prepare a polynomial-time algorithm that decides if it is a winning configuration.