I'm having a problem with writing on paper things that I came up with. There's a Misere nim game with n stones, two players, every player can take 1, 2, 3 or 4 stones in one round, the one to remove the last stone loses. Nobody makes mistakes, find n at which the second player wins (has winning strategy) and prove it by induction. So I've got to the point that the pattern for 2nd player win is 5k+1 stones but I have no idea how to write it. Is it possible to do this with P(0), P(k), P(k+1)? Or you have to do the induction only using words? Or maybe it is way more advanced than the regular way? Thanks in advance.
[Math] Misere nim, 2nd player winning strategy proof by induction
combinatorial-game-theorydiscrete mathematicsinduction
Best Answer
HINT: For your induction step, show that if $5k+1$ is a win for the second player, then $5k+2,5k+3,5k+4$, and $5k+5$ are wins for the first player, and $5k+6=5(k+1)+1$ is a win for the second player. You do the first part of this by explaining how the first player wins from $5k+2,5k+3,5k+4$, and $5k+5$; you do the second part by showing that no matter what the first player does from $5k+6$, the second player has a winning response.