in Competitive programming

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
http://www.cs.cmu.edu/afs/cs/academic/class/15859-f01/www/notes/comb.pdf

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 🙂

Write a Comment

Comment