Here is a homework problem I can't understand the solution to. Can anyone help me understand why they are using "mod 4"? Can someone help me understand this strong induction example? Thanks everyone!
Consider this variation of the game of Nim. The game begins with n matches. Two players take turns removing matches, one, two, or three at a time. The player removing the last match loses. Use strong induction to show that if each player plays the best strategy possible, the first player wins if n = 4j, 4j + 2, or 4j + 3 for some nonnegative integer j and the second player wins in the remaining case when n = 4j + 1 for some nonnegative integer j.
Basis step: There are four base cases. If n = 1 = 4•0+1, then clearly the second player wins. If there are two, three, or four matches (n = 4•0+2, n = 4•0+3, or n = 4•1), then the first player can win by removing all but one match.
Inductive step: Assume the strong inductive hypothesis, that in games with k or fewer matches, the first player can win if k ≡ 0, 2, or 3 (mod 4) and the second player can win if k ≡ 1 (mod 4). Suppose we have a game with k+1 matches, with k ≥ 4. If k+1 ≡ 0 (mod 4), then the first player can remove three matches, leaving k − 2 matches for the other player. Because k −2 ≡ 1 (mod 4), by the inductive hypothesis, this is a game that the second player at that point (who is the first player in our game) can win.
Similarly, if k + 1 ≡ 2 (mod 4), then the first player can remove one match; and if k + 1 ≡ 3 (mod 4), then the first player can remove two matches. Finally, if k +1 ≡ 1 (mod 4), then the first player must leave k, k − 1, or k − 2 matches for the other player. Because k ≡ 0 (mod 4), k − 1 ≡ 3 (mod 4), and k − 2 ≡ 2 (mod 4), by the inductive hypothesis, this is a game that the first player at that point (who is the second player in our game) can win.