**Problem statement:**

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, 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), 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):

*First of all, let’s prove that holds. Let’s define some subsets to simplify proof:*

=

=

=

=

It is clear from definition that ( takes and takes another of possible combinations of pairs in space { (x, y) | x > 0, y > 0 }, and they don’t intersect), . Then we can present P and N sets as:

Substituting, we have:

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

Pick some position from set P where . Let’s use value to construct new position . By definition of our division operation, we have , so we have some pair . Calculating modulo of sum of coordinates, we have (we have from definition of point in set P), so 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 , but then we construct new position by using coordinate .

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 from set N where . Let’s construct new position . By definition of our division operation, we have that , so we have some pair .

If , then pick . Then and therefore we constructed some point that belongs to set P.

If , then use for construction of new point instead of (construction method is same as above). We can prove that when :

1. If applies (definition of set S), then , which possible only when .

2. If and , then 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 ðŸ™‚