Game Description : the game is between 2 players and start with a pile of 'n' balls and A = {a1,a2,...,ak} ⊆ {1,....,n} .

Course of the game : each player, in his turn, picks a ∈ A
balls from the pile.

the loosing player : the player that can't play on his turn, player cant play on his turn when the number of balls in the pile is smaller from the minimum number in A.

the Task : we have to prove that to every show of the problem n,A = {a1,...,ak} only one one of the following happens : 1) the first player (the player play first) has a winning strategy . 2) the second player has an winning strategy. the winning strategy of the winner is not depend on the choices of the looser.

My Idea : I have tried to prove it with complete induction, but i'm stuck in the step.

I've assumed that for every show of the game with k<n balls the assert is holds and tried to show it holds for a game with 'n' balls.

so, the first case is that the first player can choose a ∈ A balls such that the number of balls left in the pile is less then the minimum number in A and hence player 2 cant perform his turn and player 1 allways wins.

otherwise, for any number of balls a ∈ A that player 1 took from the pile, player 2 can perform his turn. in this case the induction assertion holds (because the number of balls is less then 'n' in the pile now) and player 1 or player 2 (exactly one of them) has winning strategy. i'm stuck here. I don't know how to show that for every a ∈ A that player1 picks the player with the winning strategy will be the same one. for example if player 1 picks a1=4 from A and the induction assert find that player2 is the the player that has a winning strategy, it will return the same answear when player1 chooses a2=5 from A.

Thank you very much for your help!


1 Answer 1


The crucial point is that the game is impartial, that the options from a given position are the same for both players. That allows you to categorize each number as an $N$ position, won by the next player or a $P$ position, won by the previous player. Now $n$ is an $N$ position iff you can move to a $P$ position.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .