Another use of invariants is in analyzing strategies for pla

Another use of invariants is in analyzing strategies for playing games. Suppose a necklace with n 1 links is part of a huge treasure. Two players play a game to see who gets the treasure. Players alternate turns. In each turn, a player can remove one or two links from the necklace. The winner of the treasure is the player who removes the last link. Let Alice be the player with the first turn and Bob the player with the second turn.

(a) (5 points) Prove by induction on n that Alice can always win if n is not divisible by three. What invariant (property of the remaining links) does Alice preserve in order to win?

(b) (5 bonus1 points) Now suppose that each player must remove one link or two originally adjacent links in their turn. Prove that Bob can always win if n 3. What invariant does Bob preserve in order to win?

Solution

a) Since n is not divisible by 3, let us assume that n=3k+1 or n=3k+2

When Alice takes the first chance, she should pick either 1 or 2 depending on n. If n=3k+1, Alice should pick 1 and if n = 3k+2, Alice should pick 2.

After that, let us assume that Bob picks x links where x = 1 or 2.

Alice should pick 3-x. If Alice does this for all the subsequent moves, she will always win the game.

Proof by induction

for k = 0

n = 3k+1 or 3k+2,

Therefore, Alice picks 1 or 2 and wins

for k = 1

n = 3k+1 or 3k+2, = 4 or 5

Therefore, Alice picks 1 or 2 based on n as mentioned above and then Bob picks x. Then Alice picks 3-x. Alice wins.

Assuming for some k, Alice wins.

For k+1, n = 3(k+1)+1 or n = 3(k+1)+2

Therefore, n = 3k+1 +3 or 3k+2 +3

Where for the extra 3, Bob picks x(1 or 2) and Alice picks 3-x and wins.

Hence, proved.

b) It is not clear what is the relation of n with 3. Some mistake in the question. Update this and I\'ll provide the answer for this part as well.