Game of Nim - I
An exciting puzzle asked in Quant Trader interview at Jump Trading LLC
Game of Nim is one of the most famous Game theory puzzles ever made. We start with the most basic version and will keep increasing difficulty every week!
Alice and Bob are playing a game. There are two piles with the same number of stones. The two players take turns removing stones from the game. On each turn, the player removing stones can only take stones from one pile, but they can remove as many stones from that pile as they want. If they want, they can even remove the entire pile from the game! The winner is the player who removes the final stone. Alice goes first.
Can you figure out a winning strategy for one of the two players. Which player has the winning strategy in this case? Can you describe what their strategy would be if each of the piles had 51 stones?
What if the two piles have a different number of stones in them? Who has the winning strategy if first pile has 51 and the second pile has 75 stones ?
Try to solve this problem yourself before moving on to the solution below
.
.
.
.
Solution
Part A
If the two stones have the same number of stones in them, then the second player has a winning strategy. On each move, if the first player removes some number of stones from one of the two piles, then the second player should respond by removing exactly the same number of moves from the other pile. This will prevent the first player from ever removing the last stone, so the second player will eventually win. Once the first player has removed the last stone from one of the piles, the second player will win by removing all the remaining stones from the other pile.
Part B
If there are a different number of stones in each pile, then the first player has a winning strategy. On the first player’s first move, he should remove some stones from the larger pile in order to leave the same number of stones in each pile. With this first move, he takes over the position that the second player had in exercise 4, and the same winning strategy described above will now allow the first player to win.
.
.
😃 Over to you: Were you able to solve this?
👉 If you liked this post, don’t forget to leave a like ❤️. It helps more people discover this newsletter on Substack and tells us that you appreciate solving these weekly questions. The button is located towards the bottom of this email.
👉 If you love reading this newsletter, feel free to share it with friends!