This week, we continue our study of Impartial Games by learning about the Sprague-Grundy Theorem.
You may first choose to read the post Winning Positions if you have not already done so.
How would you solve the following?
1) The game Turning Turtles is played with a row of \(n\) turtles, each of which is right side up or upside down. On a turn, a player chooses a turtle that is upside down and flips it to be right side up. That player may then also choose any turtle to the left of the chosen turtle and flip it. For each position in Turning Turtles (there are \(2^n\) positions when playing with \(n\) turtles), determine the Nim Sum of that position, and for each winning position, determine a winning strategy from that position.
2) For those who want a coding challenge, consider the following game.
Start with a regular \(n\)-gon with \(n\) vertices. On a turn, a player may choose to remove any remaining vertex along with its two neighbours (if they have not already been removed). The last player to remove a vertex wins. For what values of \(n\) does the first player win?