I was assigned a fun, but also quite hard problem for my computer science class - I have to write a java program that computes the maximum number of turns in an optimal game of Nim.
In case you are not familiar with the game, you can read about it here.
In this case, we are only interested in winning positions for player A - we do not care about scenarios where player B is victorious. The idea is quite simple: We have N heaps with n1, n2, ... nn elements. Player A wants to remove m elements from a heap of his liking in such a way that the nim sum (n1 ⊕ n2 ⊕ ... ⊕ nn) equals 0. After that player B makes his move (which can never result in nim sum being 0 for the second time in a row). Then player A repeats the process of removing elements from one of the heaps in such manner that nim sum is set to 0. This back and forth will eventually result in player A taking the last element of the final non-empty heap and thus winning.
I have to calculate the maximum possible number of turns it takes for player A to win. There are 2 important rules that must always be satisfied:
- Player A will always try make the best possible move,
- If player B finds himself in a lost situation, he will try to prolong the game for as long as possible.
Through my time analyzing this problem, I've come to the following assumptions:
- The best move for player A is to always remove the maximum possible number of elements that he can, while still passing the nim sum of 0 to player B,
- The best way for player B to prolong the game is to remove 1 element at the time,
- Player B should always remove a single element from a heap with the most elements left at the time of his move.
I'd love to hear your corrections, opinions and observations regarding these 3 statements, as I have no mathematical proof for them, they are based solely on some program testing and observation.
