Dynamic Programming Winning Strategy

Question

Describing A Game: In the Game there are 2 players (player 1 and player 2) and there is a board with a number of ball in it $n$.There is also a set $A =${$A1...Am$} which hold the amount of ball each player is allowed to remove in one move.

progress of the game: each player at his turn remove $a\in A$ balls from the board.

loser: is a player who cannot remove $a\in A$ form the board. Meaning the number of balls on the board is smaller than $a,$$\forall a \in A$ .

For example $A = ${$2,3$} and $n=6$. the first player remove 3 balls then the second player remove 2 balls and we are left with one ball on the board so the second player win.

Another example $A = ${$2,3$} and $n=6$. the first player remove 2 balls then the second player remove 2 balls.then the first player remove 2 balls then the second player is left with zero balls on the board so the first player win.

I can see that for each $A$ and $n$ there are 2 option: Player one has as Winning Strategey,or Player two has as Winning Strategey.

I can see it via a tree that I draw that represent a game. which spread from the root (player 1) to the second level (player 2) based on $a,$$\forall a \in A$ and so on.

Edit: I need to prove that for each $n$ and a set $A =${$A1...Am$} there exist one of the following situation:

1. palyer 1 has a winning strategy.

2. player 2 has a winning strategy.

But I find it hard to proof (via induction).

Answer 1

I suspect that what you actually need to prove is that, for each position of the game (represented by $n$, with the set $A$ fixed), either (1) there is a winning strategy for the player to move (the first player), or (2) for each move the first player has (if any), there is a winning strategy for the other player in the resulting position. This can indeed be proven by induction on $n$. When $n=0$, there are no moves for the first player; we are in the case (2). Suppose $n>0$. There are two possibilities: either there is a move for the first player that leads to a new position $n'$ for which the case (2) takes place (with players exchanged), or there's no such a move. The first possibility corresponds to the case (1) for $n$. The second corresponds to the case (2) for $n$, because either there are no moves at all, or each move leads to a position which is not in the case (2) and therefore - by induction! - is in the case (1); in both cases the first player loses.

Back to the present game. The first player has a winning strategy with $n$ balls initially (on the board) if and only if there exists $a\in A$ such that the (second) player doesn't have a winning strategy with $n-a$ balls initially. In other words, let $f(n)\in\{0,1\}$ represent the existence of a winning strategy for the first player with $n$ balls initially (where $1$ means "exists"); if we "conveniently" assume $f(n)=1$ for $n<0$, then $$f(n)=\neg\bigwedge_{a\in A}f(n-a)\quad\text{for } n\geqslant 0$$ (where $\neg$ is logical "not" and $\wedge$ is logical "and"). For your example $A=\{2,3\}$, you get $$(f(0),f(1),f(2),\ldots)=(\color{blue}{0,0,1,1,1},0,0,1,1,1,\ldots)$$ (a periodic sequence with the period shown in blue).