Consider the following game. Initially a heap of n matches is placed on the tabl

Question

Consider the following game. Initially a heap of n matches is placed on the table between two players. Each player in turn may either (a) split any heap on the table into two unequal heaps, or (b) remove one or two matches from any heap on the table. He may not do both. He may only split one heap, and if he chooses to remove two matches, they must both come from the same heap. The player who removes the last match wins.

For example, suppose that during play we arrive at the position (5, 4); that is, there are two heaps on the table, one of 5 matches, the other of 4. The player whose turn it is may move to (4, 3, 2) or (4, 4, 1) by splitting the heap of 5, to (5, 3, 1) by splitting the heap of 4 (but not to (5, 2, 2), since the new heaps must be unequal), or to (4, 4), (4, 3), (5, 3) or (5, 2) by taking one or two matches from either of the heaps.

Sketch the graph of the game for n = 5. If both play correctly, does the first or the second player win?

Explanation / Answer

Heaps are also called piles, and the objects are called stones.

The nim sum a Xor b of two non-negative integers a and b is defined as follows. Represent a and b as sums of distinct powers of two. Cancel powers of two appearing twice, and add up the remaining numbers. Nim-sum is also known as XOR by computer scientists.

For example, 3 Xor 5 can be computed as follows. We have 3=2^1+2^0 and 5=2^2+2^0 . We cancel 2^0 for appearing twice, and add up the remaining 2^1+2^2 , giving 3 Xor 5

It can be shown that Xor is associative, thus making the nim-sum of several numbers a1 Xor a2 Xor a3...Xor an defined.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.