Problem 2 of 5. Misere Empty and Divide. There are two boxes. Initially, one box

Question

Problem 2 of 5. Misere Empty and Divide. There are two boxes. Initially, one box contains chips and the other contains n chips. Such a position is denoted by (m, n), where m 0 and n > 0. The two players alternate moving. A move consists of emptying one of the boxes, and dividing the contents of the other between the two boxes with at least one chip in each box. There is a unique terminal position, namely 1. Last player to move loses. Show that the only P-positions are of the form (3k 1,1), (1,3k 1), or (3k 1,3 - 1), where ko, 1>-0 ae arbitrary natural unbers

Explanation / Answer

Write down all positions for this game with two piles containing up to 7 pebbles,

and decide whether they are W or L positions for the player about to move.

Make a guess about the general form of all W and L positions, and check that

your guess is correct via the methods discussed in class.

Solution:

Start with a list of all positions in this game up with piles up to 7

pebbles. Note that we don’t list positions where one pile has 0 pebbles, because

in this game it’s impossible to arrive at such a position.

(1,1)

(1,2)

(2,2)

(1,3)

(2,3)

(3,3)

(1,4)

(2,4)

(3,4)

(4,4)

(1,5)

(2,5)

(3,5)

(4,5)

(5,5)

(1,6)

(2,6)

(3,6)

(4,6)

(5,6)

(6,6)

(1,7)

(2,7)

(3,7)

(4,7)

(5,7)

(6,7)

(7,7)

Obviously (1

,

1) is a L for the player about to move, since there are no legal

moves remaining. Then, any position with a pile of two pebbles can reach (1

,

1)

(just throw away the OTHER pile and split the 2 into 1 and 1.) So, all positions

where one of the piles is 2 is a W

(1,1) L

(1,2) W

(2,2) W

(1,3)

(2,3) W

(3,3)

(1,4)

(2,4) W

(3,4)

(4,4)

(1,5)

(2,5) W

(3,5)

(4,5)

(5,5)

(1,6)

(2,6) W

(3,6)

(4,6)

(5,6)

(6,6)

(1,7)

(2,7) W

(3,7)

(4,7)

(5,7)

(6,7)

(7,7)

Now (1

,

3) can only move to (1

,

2), which is a W, so (1

,

3) is an L. Continuing

in this way, we can label all of the positions:

(1,1) L

(1,2) W

(2,2) W

(1,3) L

(2,3) W

(3,3) L

(1,4) W

(2,4) W

(3,4) W

(4,4) W

(1,5) L

(2,5) W

(3,5) L

(4,5) W

(5,5) L

(1,6) W

(2,6) W

(3,6) W

(4,6) W

(5,6) W

(6,6) W

(1,7) L

(2,7) W

(3,7) L

(4,7) W

(5,7) L

(6,7) W

(7,7) L

At this point, we see a pattern: it looks like a position is a L if BOTH piles are

odd, and a W if AT LEAST ONE pile is even. As we did in class, we check this

by verifying three properties.

(1) From any L, every move leads to a W.

If a position is an L, then both

piles are odd. This means that no matter which pile you throw away and which

pile you split, you will be splitting up an odd pile. Splitting an odd pile into

two pieces MUST result in an odd pile and an even pile. This means that every

move leads to a position with an odd pile and an even pile, which is a W.

(2) From any W, there is a move leading to an L.

If a position is a W,

then at least one pile is even. You can throw away the other pile and split the

even pile into two odd piles. (For instance, you can split into a pile of 1 and

a pile with the remaining portion.) This is a legal move leading to a position

with two odd piles, which is an L.

(3) For endings, your guesses agree with reality.

The game is over at

(1

,

1). Our rules say that this position is a L (both of the piles are odd), and

this agrees with reality: if confronted with (1

,

1), you just lost.

This verifies our guess, so we can say that no matter how big the piles are, a

position is an L if both piles are odd and a W if at least one pile is even

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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