For a given positive integer n, we define and play the following game. There are two players in this game, Alice and Bob. Starting from Alice, they choose either 1, 2, or 3 consecutive integers in turn from the set {1, 2, . . . , n}, which should start from the smallest integer that is not called yet. The player who chooses the last integer n loses this game, so the opponent wins the game. Example. When n = 6, Alice first chooses 1, 2 and 3. In the next turn, Bob chooses 4 and 5. So Alice should choose the last number 6. This makes Alice lose the game, and makes Bob win. Now consider the following:

(a) Show that if n = 4k + 1, Bob has a winning strategy, in other words, there is a strategy for Bob where he can always win, using mathematical induction on k N = {0, 1, 2, . . . }. (

b) Show that if it is not the case that n 4 1, then Alice has a winning strategy. You might want to use (a).

(c) What if we change the rule so that the player who chooses the last number wins the game? When does Alice have a winning strategy? How about Bob? Prove your claim.