Step-by-step explanation:
(a) We will prove by induction that if n is a multiple of 3 then Bob has a winning strategy.
Let n=3
It is given that Alice always plays first.
Then, for the first move, Alice has a choice of removing 1 or 2 stones.
Case 1:
Alice removes 1 stone. Then it is now Bob's turn. There are 2 stones left. Bob has the choice of removing 1 or 2 stones. Then Bob's winning strategy should be to remove 2 stones. Then Bob removes the last stone and wins.
Case 2:
Alice removes 2 stones. Then it is Bob's turn. There is exactly 1 stone left, which Bob removes in his turn. Since he removes the last stone, he wins.
Thus, in either case, for n=3, Bob has a winning strategy. (A)
Now, let us assume that Bob has a winning strategy for n=3p.
We will now check if Bob has a winning strategy for n=3p+3
It is given that Alice plays first.
Case 1:
Alice starts the game by removing 1 stone. Then, Bob has a choice of removing 1 or 2 stones. If he chooses to remove 2 stones, then the number of stones left is 3p+3-3=3p and it is now Alice's turn to play. This is exactly the game when n=3p and we have already assumed that Bob has a winning strategy for n=3p. Thus, in this case Bob has a winning strategy.
Case 2:
Alice starts the game by removing 2 stones. Then, Bob has a choice of removing 1 or 2 stones. If he chooses to remove 1 stone, then the number of stones left is 3p+3-3=3p and it is now Alice's turn to play. This is again exactly the game when n=3p and we have already assumed that Bob has a winning strategy for n=3p. Thus, in this case also, Bob has a winning strategy.
Thus, in either case Bob has a winning strategy for n=3p+3 if he has a winning strategy for n=3p. (B)
Thus, from (A) & (B), using induction, we can say that Bob has a winning strategy if n is a multiple of 3.
(b) We will now prove that if n is not a multiple of 3, then Alice has a winning strategy.
If n is not a multiple of 3, then n can have either of the forms of 3m+1 or 3m+2, m ∈ W.
We will prove the given fact for both the forms simultaneously
Let m=0, i.e., n=1 or n=2
Since Alice starts first, she removes 1 stone, if n=1 or 2 stones if n=2 and thus wins. Thus Alice has a winning strategy if m=0. (A)
Let us assume that Alice has a winning strategy for m=k, i.e., for n=3k+1 & n=3k+2
Now, we will check if Alice has a winning strategy for m=k+1, i.e., for n=3(k+1)+1=3k+4 or n=3(k+1)+2=3k+5
Let n=3k+4
Since Alice plays first, she has a choice to remove 1 or 2 stones.
Note that, if Alice removes 2 stones and in turn Bob removes 2 stones, then the number of stones becomes a multiple of 3 such that it is Alice's turn to play. In that case, Bob will have a winning strategy as shown in the previous part.
Then, Alice should remove 1 stone. Then, it is now Bob's turn and he has a choice of removing 1 or 2 stones.
Case 1:
Bob removes 1 stone. Then there are 3k+4-1-1=3k+2 stones remaining and it is Alice's turn. This is identical to the game where n=3k+2. We have already assumed that Alice has a winning strategy in this case.
Case 2:
Bob removes 2 stones. Then there are 3k+4-1-2=3k+1 stones remaining and it is Alice's turn. This is identical to the game where n=3k+1. We have already assumed that Alice has a winning strategy in this case.
Thus, in either case, Alice has a winning strategy.
Let n=3k+5
Since Alice plays first, she has a choice to remove 1 or 2 stones.
Note that, if Alice removes 1 stone and in turn Bob removes 1 stone, then the number of stones becomes a multiple of 3 such that it is Alice's turn to play. In that case, Bob will have a winning strategy as shown in the previous part.
Then, Alice should remove 2 stones. Then, it is now Bob's turn and he has a choice of removing 1 or 2 stones.
Case 1:
Bob removes 1 stone. Then there are 3k+5-2-1=3k+2 stones remaining and it is Alice's turn. This is identical to the game where n=3k+2. We have already assumed that Alice has a winning strategy in this case.
Case 2:
Bob removes 2 stones. Then there are 3k+5-2-2=3k+1 stones remaining and it is Alice's turn. This is identical to the game where n=3k+1. We have already assumed that Alice has a winning strategy in this case.
Thus, in either case, Alice has a winning strategy.
Then, we can say that Alice has a winning strategy for m=k+1 if she has a winning strategy for m=k. (B)
Then, by induction, from (A) & (B), we can say that if n is not a multiple of 3, then Alice has a winning strategy.
