Given 3 piles of chips, each of size 3,5, and 7 respectively. Two players take turn to play. When it is a player's turn, he can remove as many chips as he wants from one pile. Whoever removes the last chips wins the game.
Here is an illustration of the game with 2 players, Andhieka and Tio, where Andhieka starts first:
A B C
3 5 7 Initial configuration
1 5 7 Andhieka removes 2 chips from A
1 2 7 Tio removes 3 chips from B
1 2 4 Andhieka removes 3 chips from C
1 2 0 Tio removes 4 chips from C
1 1 0 Andhieka removes 1 chip from B
1 0 0 Tio removes 1 chip from B and begging Andhieka to stop
0 0 0 Andhieka removes 1 chip from A and wins the game.
The game can be generalized to k piles with a1,a2,...,ak chips each. The setting above is called normal play where players try to be the one who removes the last chips. Another setting, misere play, is when players try not to be the one who removes the last chips. In both type of setting, there are winning strategies for the generalized Nim game.
Let's start with normal play Nim game. The key observation to win this game is by considering the binary representation of a1,a2,…,ak. An operation called exclusive or (XOR, represented as ⊕) reveals an important property of the game. We define S such that
S=a1⊕a2⊕…⊕ak
The goal is to have all piles having zero chips, and when this happens, S=0.
From this observation, we can posit the following claims:
Claim 1:
If S is currently equals 0, whatever we do on our turn, S will change to something else than 0
Proof:
Suppose that on our turn, we manage to take away some chips from a pile such that S is changed to T=b1⊕b2⊕…⊕bk=0. Since we can only remove chips from one pile, call that pile i, the other k−1 piles will have the same number of chips after our turn. Then we have:
S⊕T=(a1⊕a2⊕…⊕ak)⊕(b1⊕b2⊕…⊕bk)
S⊕T=(a1⊕b1)⊕(a2⊕b2)⊕…⊕(ak⊕bk)
Note that (aj⊕bj)=0 for j≠i, hence
S⊕T=0⊕0⊕…⊕(ai⊕bi)⊕…⊕0
S⊕T=ai⊕bi
Note that LHS equals to 0, since S=0 and by assumption, T=0.
However, RHS cannot be 0 since ai≠bi since we removed some chips from pile i, a contradiction. Hence T cannot be 0, and the proof is complete. ◼
Claim 2:
If S is currently not equal to 0, on our turn we can remove chips to arrive at S=0
Proof:
This is proof will also reveals the strategy and therefore algorithm for players to win the game.
Denote the most significant bit of S as m. For bit m to be turned on, there must be odd numbers of piles in which the bit at position m is also turned on. This means that there will be at least 1 such pile, let the pile be i. If there are more than one pile, any one of them will do.
Define Y=ai−(S⊕ai). If we can take Y chips from pile i, then we will have piles with chips (a1,a2,…,ai−Y,…,ak) such that
S′=a1⊕a2⊕…⊕(ai−Y)⊕…⊕ak
S′=a1⊕…⊕(S⊕ai)⊕…⊕ak
Rearranging, we have
S′=S⊕S=0
which proves our claim. However, we need to show that (S⊕ai) is indeed less than ai, or else we can't take negative amount of Y chips from pile i. This is actually easy, since S⊕ai at least turns off bit m from ai, and it any bit higher than bit m untouched since m is the most significant digit of S. Therefore (S⊕ai) is guaranteed to be less than ai, which completes the proof. ◼
No comments:
Post a Comment