1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How can I prove that this is actually works? $\endgroup$ – נירייב שמואל Apr 2 at 14:00
  • $\begingroup$ I edited the question so it will be clear for you what I need to prove. $\endgroup$ – נירייב שמואל Apr 2 at 14:18
  • 1
    $\begingroup$ I've edited the answer... probably something's getting clarified ;) $\endgroup$ – metamorphy Apr 2 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.