A single heap nim game

Question

Consider a game where two players remove sticks from a heap. The players move alternately, and the player who removes the last stick wins the game.

A set P = {p1,p2,…,pk} determines the allowed moves. For example, if P = {1,3,4}, a player may remove 1, 3 or 4 sticks.

Your task is find out for each number of sticks 1 , 2 ,…, n if the first player has a winning or losing position.

How to solve this question. Thank You for help.

Answer 1

I'll give you two hints. Firstly, A losing position means there exists a move for your opponent to win in a single move, or to bring you to a losing position in a single move. Observe that if you are currently in a winning position, you can put yourself in a winning position within one move.

Secondly, you should label winning positions starting from the very first stick until the last, e.g. since stick $i$ is a winning / losing position for the starting player, stick $i + p$ must be a winning / losing position for starting/second player.

P.S. The game might deadlock for $p_1 > n$, where $n$ is the number of remaining sticks and $p_1 < p_2 < ...$.