# Solution for “Empty and Divide” problem

Problem statement:

There are two boxes. Initially, one box contains $m$ 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, 1). Last player to move wins. Find all P-positions.

Original task source: Game Theory, Class notes for Math 167, Fall 2000, Thomas S. Ferguson

From problem statement we can find that (1, 1) is P position (because last player to move wins, we consider that normal play rule takes place). Lets find N-positions that lead to terminal position.

The only way to obtain (1, 1) position is to divide value 2 into two boxes, therefore positions (2, n) and (m, 2), $\forall n > 0, \forall m > 0$ are N-positions that lead to terminal P-position.

Taking step further, let’s find some P-positions that lead to (2, 1) and (1, 2). Positions (3, 1), (1, 3) are P-positions from definition of P-position (they lead only to N-positions, in this case (2, 1) and (1, 2)). Taking several steps forward by keeping one of values as 1 and increasing another by one, we will find that

(1, 1) -> P
(2, n), (m, 2) -> N, for any m > 0, n > 0
(3, 1), (1, 3) -> P
(4, 1), (1, 4) -> N
(5, 1), (1, 5) -> P
(6, 1), (1, 6) -> N


However, then we have (1, 7) and (7, 1). Are they really P-positions? Using value 7, we can find next pairs: (1, 6) – N, (2, 5) – N, (3, 4) – ?, (4, 3) – ?, (5, 2) – N, (6, 1) – N.

Is (3, 4) P-position? No, because we can obtain position (1, 3) by dividing value 4 into two boxes, which denies definition of P-position.
Is (3, 4) N-position? Yes, we can reach some P-position from it.

Applying same logic to (4, 3), we can assume that positions (1, 7) and (7, 1) are truly P-positions.

Trying other positions like (3, 5), (5, 7), (9, 3) and so on, we can start observing some pattern by how P-positions and N-positions are distributed.

Now we assume that we have next sets (set P is for P-positions and N for N-positions):

$P = \{ (x,y) | (x+y) \mod 2 = 0 \quad \textrm{and} \quad x \mod 2 = 1 \quad \textrm{and} \quad y \mod 2 = 1 \}, \forall x > 0, y > 0$
$N = \{ (x,y) | (x+y) \mod 2 = 1 \quad \textrm{or} \quad x \mod 2 = 0 \quad \textrm{or} \quad y \mod 2 = 0 \}, \forall x > 0, y > 0$

First of all, let’s prove that $N \cup P = U$ holds. Let’s define some subsets to simplify proof:

$M_1$ = $\{ (x,y) | x \mod 2 = 1 \quad \textrm{and} \quad y \mod 2 = 1 \}, \forall x > 0, \forall y > 0$
$M_0$ = $\{ (x,y) | x \mod 2 = 0 \quad \textrm{or} \quad y \mod 2 = 0 \}, \forall x > 0, \forall y > 0$
$P_M$ = $\{ (x,y) | (x+y) \mod 2 = 0 \}, \forall x > 0, \forall y > 0$
$N_M$ = $\{ (x,y) | (x+y) \mod 2 = 1 \}, \forall x > 0, \forall y > 0$

It is clear from definition that $M_1 \cup M_0 = U, M_1 \cap M_0 = \emptyset, U \setminus M_1 = M_0$ ($M_1$ takes $1 / 4$ and $M_0$ takes another $3 / 4$ of possible combinations of pairs in space { (x, y) | x > 0, y > 0 }, and they don’t intersect), $P_M \cup N_M = U, P_M \cap N_M = \emptyset, U \setminus P_M = N_M$. Then we can present P and N sets as:

$P = P_M \cap M_1$
$N = N_M \cup M_0$

Substituting, we have:

$N = N_M \cup M_0 = (U \setminus P_M) \cup M_0 = (U \setminus P_M) \cup (U \setminus M_1) = (U \cup (U \setminus M_1) ) \setminus ( P_M \setminus (U \setminus M_1) ) = U \setminus (P_M \setminus (U \setminus M_1) ) = U \setminus ((P_M \cap M_1) \cup ( P_M \setminus U )) = U \setminus P$

$N \cup P = (U \setminus P) \cup P = (U \cup P) \setminus ( P \setminus P ) = U$

Let’s prove that all positions from set P are really P-positions:

Pick some position $(x_p, y_p)$ from set P where $x_p > 1, y_p > 0$. Let’s use value $x_p > 1$ to construct new position $(x_n, y_n)$. By definition of our division operation, we have $y_n = x_p - x_n, 0 < x_n < x_p$, so we have some pair $(x_n, x_p - x_n)$. Calculating modulo of sum of coordinates, we have $(x_n + (x_p - x_n)) \mod 2 = x_p \mod 2 = 1$ (we have $x_p \mod 2 = 1$ from definition of point in set P), so $(x_n, x_p - x_n)$ belong to set N. So, we can conclude that performing division operation on any point in set P gives us new point from set N.

By analogy, same logic chain can be applied for any position with value $x_p > 0, y_p > 1$, but then we construct new position by using coordinate $y_p$.

There is a corner case (1, 1), but it is trivial P-position that can’t be used to construct anything.

Let’s prove that all positions from set N are really N-positions:

Pick some position $(x_k, y_k)$ from set N where $x_k > 1, y_k > 1$. Let’s construct new position $(x_n, y_n)$. By definition of our division operation, we have that $y_n = x_k - x_n, 0 < x_n < x_k$, so we have some pair $(x_n, x_k - x_n)$.

If $x_k \mod 2 = 0$, then pick $x_n = 1$. Then $(y_n) mod 2 = (x_k - x_n) mod 2 = 1$ and therefore we constructed some point $(x_n, y_n)$ that belongs to set P.

If $x_k \mod 2 = 1$, then use $y_k$ for construction of new point instead of $x_k$ (construction method is same as above). We can prove that $y_k \mod 2 = 0$ when $x_k \mod 2 = 1$:
1. If $(x_k + y_k) \mod 2 = 1$ applies (definition of set S), then $(x_k + y_k) \mod 2 = (x_k \mod 2 + y_k \mod 2 ) \mod 2 = (1 + y_k \mod 2) \mod 2 = 1$, which possible only when $y_k \mod 2 = 0$.
2. If $(x_k + y_k) \mod 2 \ne 1$ and $x_k \mod 2 = 1$, then $y_k \mod 2 = 0$ by definition of set N.

So, we can conclude that by performing division operation on any point in set N it is possible to construct some point from set P, which satisfies definition of N-positions.

Proof took some time, but hopefully will help to solve not only this problem 🙂

This site uses Akismet to reduce spam. Learn how your comment data is processed.