Suppose we begin with two piles of stones with two stones in the first pile and

Question

Suppose we begin with two piles of stones with two stones in the first pile and two stones in the second pile. On each turn, a player chooses a pile and removes any number of stones from it. The person that removes the last stone wins the game. (i) As shown and described in Example 5 of Section 7.5 on page 574, write the vertices of the graph for this stone removal game, and describe all the edges. Hint: There will be 9 vertices, (a,b). (ii) Identify the kernel, the set of good nodes for the graph.

Explanation / Answer

It is clear that if there are only one, two, or three stones left (on your turn), you can win the game by taking all of them. If, however, there are exactly four stones you will lose, because no matter how many you take, you will leave one, two, or three and your opponent will win by taking the remainder. If there are five, six, or seven stones you can win by taking just enough to leave four stones. If there are eight stones you will again lose, because you must leave five, six, or seven. Etc. Here is the win/loss information for take one-two-or-three for up to 21 stones. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 L W W W L W W W L W W W L W W W L W W W L W In general, if there are a multiple of four stones you lose. Otherwise you win (by taking enough stones to leave a multiple of four for your opponent). So we see the pattern LWWW, which is repeated. Thus, 21 stones is a win: take one stone. Def 1.2 Let a1, a2, . . . , ak be k distinct natural numbers (nonzero). Then (a1, . . . , ak)-NIM is the following game. 1

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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