Answered

Westonci.ca is the premier destination for reliable answers to your questions, provided by a community of experts. Discover a wealth of knowledge from experts across different disciplines on our comprehensive Q&A platform. Get detailed and accurate answers to your questions from a dedicated community of experts on our Q&A platform.

Alice and Bob play a game by taking turns removing 1 or 2 stones from a pile that initially has n stones. The person that removes the last stone wins the game. Alice plays always first.
(a) Prove by induction that if n is a multiple of 3 then Bob has a wining strategy.
(b) Prove that if n is not a multiple of 3 then Alice has a wining strategy.

Sagot :

Answer:

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.

We hope our answers were helpful. Return anytime for more information and answers to any other questions you may have. We hope you found what you were looking for. Feel free to revisit us for more answers and updated information. Find reliable answers at Westonci.ca. Visit us again for the latest updates and expert advice.