In class, we discussed the game of NIM. This game begins with a placement of n r

Question

In class, we discussed the game of NIM. This game begins with a placement of n rows of matches on a table. Each row i has mi matches. Players take turns selecting a row of matches and removing any or all of the matches in that row. Whoever claims the final match from the table wins the game. This game has a winning strategy based on writing the count for each row in binary and lining up the binary numbers (by place value) in columns. We note that a table is favorable if there is a column with an odd number of ones in it, and the table is unfavorable if all columns have an even number of ones. Example: Suppose we start off with three rows of matches of 7, 8 and 9. Since the third row from the right and the second row from the right, each have odd numbers of ones, the table is favorable. Prove that, for any favorable table, there exists a move that makes the table unfavorable. Prove also that, for any unfavorable table, any move makes the table favorable for one's opponent. Write the algorithm that on input of favorable table output the row and the number of matches to remove from the row, to make the table unfavorable. Give a winning strategy for this game.

Explanation / Answer

a) We always move towards making the XOR sum of all values equal to zero.

Since there are some columns with odd number of ones.

We can choose the one of those numbers with leftmost bit = 1, and reduce it in a such a way ( remove 1 bits ) that it makes all columns even. See example below.



b) 7 = 0111

8 = 1000

9 = 1001

A winning move would be reduce 7 to 0001 which is 1 so that all columns are made even.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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