Question

1. NIM game is a game with multiple piles of match sticks with the two players taking turns to remove 1 pile or part of 1 pile. The person getting the last stick wins. In the class I had shown how (1, 1) and (2, 2) are losing configurations (i.e. the person facing two piles of 2 and 2 sticks will lose). a) Prove that (3, 4) is a winning configuration. Show how the 1s player can win if she / he plays with a pile of 3 sticks and another pile of 4 sticks. Draw game tree if necessary. Is (1, 2, 3, 4) a winning configuration or losing configuration? This one means 4 piles with 1, 2, 3, and 4 sticks respectively. Explain and show the moves. b)

Answer 1

A-> (3,4) is a winning configuration .

First

3 sticks

4 sticks

The first player will take 1 stick from of size 4 pile Now both pile will have three

Now 2nd player's chance

3sticks

3sticks

The 2nd player can take any number of Sticks from any pile because , It is loosing situation same as (1,1) and (2,2)

if it takes 3 sticks ,1st player will take 3 sticks too and player 2 will loose

If it take 1 sticks , 1st will take 1 stick too and it will become (2,2) situation

same for taking 2 sticks it will become (1,1) situation.

There is another way of proving it.If xor of all piles is nonzero then it is winning condition

3 xor 4 is 7 (nonzero ) So it is winning condition

Answer - (b) -> there are 4 piles of 1,2,3,4 sticks

XOR of the is

1 xor 2 = 3

3 xor 3 = 0

0 xor 4 = 4(nonzero)

So it is also winning condition

Moves

First player moves

1

2

3

4

1st player takes 4 sticks from last pile

2nd players move

1

2

3

2nd player take whatever he wants .Lets it takes 1 stick from 2nd pile

1st player move

1

1

3

1st player takes last pile 3 sticks

2nd player move

1

1

Now its (1,1) condition for 2nd player ,He will loose and first player will win

If you have any doubt .Please feel free to ask thanks.