# Homework Help: Nim game tree

1. Dec 6, 2015

### wololo

1. The problem statement, all variables and given/known data

2. Relevant equations
Tree data structures.
I think it might also have something to do with minimax algorithm, but it was only mentioned once and never discussed extensively in class so I doubt it is required.

3. The attempt at a solution

If both players play as well as they can, the game will end in a draw. Player 1 will always have the option of choosing to draw rather than lose.

However I can't find a function that given n sticks will tell me who will win. For 5, 10 and other multiples of 5, player 2 necessarily wins but what about the other cases? How can I find a single formula that will necessarily tell me who will win, given that they play well?

2. Dec 7, 2015

### BvU

Misunderstanding: you can't end in a draw.

3. Dec 7, 2015

### wololo

"The player who removes the last match wins, except if there is only one match left, in which case the game is a draw." All the paths that end in 1 in the game tree are draws.

4. Dec 7, 2015