# Dynamic Programming Winning Strategy

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).

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).