A chocolate problem that has a simple formula for P-positions

The chocolate problem of Example 2.1 is very difficult to study mathematically, and hence the authors have made a easier version the chocolate problem. This chocolate has a very simple formula to calculate P-positions.

Example 3.1.   Suppose that you have the chocolate in Graph 3.1. In Graph 3.1 you can cut the chocolate in 3 ways, so it is appropriate to represent it with 3 non-negative integers $\{x, y, z\}$. We represent the position in Graph 3.1 with $\{4, 6, 2\}$. It is clear that we have an inequality between these 3 coordinates. $y \leq x + z$.
Note that a list of non-negative numbers $\{x, y, z\}$ is a position of this chocolate problem when $y \leq x + z$.

Graph 3.1.  

Theorem 3.1.   The chocolate problem of Example 3.1 has the following simple formula to calculate P-positions.
$(1)$ The position {x, 0, z} is a P-position if and only if $x = z$.
$(2)$ The position {x+1, y, z+1} is a P-position if and only if $x \oplus y \oplus z = 0$.

We are going to prove Theorem 3.1, and we need some corollaries and lemmas.

Example 3.2.   We are going to use the chocolate problem of Graph 3.2. This chocolate problem is a special case of the problem of  Example 1.1, but this is useful when we study the chocolate problem of Example 3.1
.

Graph 3.2.  

In Graph 3.2 you can cut the chocolate in 3 ways, so it is appropriate to represent it with 3 non-negative integers $\{x, y, z\}$. You can make any size of this kind of chocolate problem if you use arbitrary non-negative integers $x, y, z$.

Remark 3.1.   For convenience's sake we are going to call the chocolate problem of Example 3.2 and the chocolate problem of Example 3.1 the Game 1 and the Game 2 respectively.

Let $A_+$ = { $\{x, y, z\}$, $x \oplus y \oplus z$=0 and $y > 0$} and $B_ 0$= { $\{x, y, z\}$, $x \oplus y \oplus z$=0 and $y = 0$} = { $\{x, y, z\}$, $y = 0$ and $x = z$}. Let $B_{+}$ = { $\{ x+1, y, z+1\}$, $x \oplus y \oplus z$ =0 and $y > 0$}.

Corollary 3.1.   The list {{x, y, z}, $x \oplus y \oplus z$=0} is the set of P-positions of Game 1 and the list {{x, y, z}, $x \oplus y \oplus z \neq 0$} is the set of N-positions of Game 1.

Proof.   This is direct from Theorem 1.1.
By Remark 3.1 Game 1 is a special case of the game of Example 1.1, and hence we can use Theorem 1.1 to Game 1 by making the fourth coordinate 0.

Corollary 3.2.   $[1]$ If x $\oplus y \oplus z$=0, u $<$ x, v $<$ y and w $<$ z, then we have u $\oplus y \oplus z \neq 0$, $x \oplus v \oplus z \neq 0$ and $x \oplus y \oplus w \neq 0$.
$[2]$ If $x \oplus y \oplus z \neq 0$, then at least one of the following three conditions is satisfied.
$[2.1]$ There exists u such that u $<$ x and $u \oplus y \oplus z = 0$.
$[2.2]$ There exists v such that v $<$ y and $x \oplus v \oplus z = 0$.
$[2.3]$ There exists w such that w $<$ z and $x \oplus y \oplus w = 0$.

Proof. [1].  This is direct from Corollary 3.1 and the definition of P-positions and N-Positions. For example if $x \oplus y \oplus z = 0$, then by Corollary 3.1 {x, y, z} is a P-position of Game 1. From this position you can move to {u, y, z} with u $<$ x or {x, v, z} with v $<$ y or {x, y, w} with w $<$ z. Therefore {u, y, z}, {x, v, z} and {x, y, w} are N-positions of Game 2. Therefore we have $u \oplus y \oplus z \neq 0$, $x \oplus v \oplus z \neq 0$ and $x \oplus y \oplus w \neq 0$.
[2] If $x \oplus y \oplus z \neq 0$, then by Corollary 3.1 {x, y, z} is an N-position, and hence there should be a option that leads to a N-position.
Therefore at least one of the conditions $[2.1], [2.2]$ and $[2.3]$ are satisfied.

Lemma 3.1.   If $x \oplus y \oplus z = 0$, then $x + z \geq y$.

This is clear from Definition 1.2 and Example 1.2.

Remark 3.2.   By Lemma 3.1 $A_+, B_ 0, B_+$ $\subset$ {{x, y, z}, $x + z \geq y$}, and hence if $\{x, y, z\} \in A_+, B_ 0, B_+$, then $\{x, y, z\}$ is a position of the chocolate problem of Example 3.1.

Lemma 3.2.   For any non-negative integer x {x, 0, x} is an N-position of Game 2, i.e., any element in $B_ 0$ is a P-position of Game 2.

Proof.   For the list {{x, y, z}, with y = 0} , Game 1 and Game 2 have the same mathematical structure. Therefore by the fact that $x \oplus 0 \oplus x = 0$ and by Corollary 3.1 we know that {x, 0, x} is an P-position of Game 1, and hence it is an P-position of Game 2.

Lemma 3.3.   For non-negative integers $x, z$ with $x \neq z$ {x,0,z} is an N-position of Game 2.

Proof.   By reducing x or z we can make the first and the third coordinate the same. Therefore we can move from {x,0,z} to a P-position of Game 2. Therefore {x, 0, z} is an N-position.

Lemma 3.4.   $(1)$. {0, 0, 0}, {1, 0, 1}, {1, 1, 2}, {2, 0, 2} and {2, 1, 1} are P-positions.
$(2)$. {0, 0, 1}, {0, 0, 2}, {0, 0, 3}, {0, 0, 4}, {0, 1, 1}, {0, 1, 2}, {0, 1, 3}, {0, 2, 2}, {1, 0, 0}, {1, 0, 2}, {1, 0, 3}, {1, 1, 0}, {1, 1, 1}, {1, 2, 1}, {2, 0, 0}, {2, 0, 1}, {2, 1, 0}, {2, 2, 0}, {3, 0, 0}, {3, 0, 1}, {3, 1, 0} and {4, 0, 0} are N-positions.

Proof.  By Definition of P-position {0, 0, 0} is a P-position. By Lemma 3.2 {1, 0, 1}, and {2, 0, 2} are P-positions.

It is easy to see that {0, 0, 1}, {0, 0, 2}, {0, 0, 3}, {0, 0, 4}, {0, 1, 1}, {0, 1, 2}, {0, 1, 3}, {0, 2, 2}, {1, 0, 0}, {1, 1, 0}, {2, 0, 0}, {2, 1, 0}, {2, 2, 0}, {3, 0, 0},{3, 1, 0} and {4, 0, 0} are N-positions, since you can move from each of them to {0, 0, 0}. For example, if you have {2, 1, 0}, then by subtracting 2 from the first coordinate you get {0, 0, 0}, since the position should satisfy the inequality $y \leq x + z$.
{1, 0, 2}, {1, 0, 3}, {1, 1, 1}, {1, 2, 1}, {2, 0, 1} and {3, 0, 1} are N-positions, since you can move from each of them to {1, 0, 1} that is a P-position.

From {1, 1, 2} we can move to {0,1,2}, {1,0,2}, {1,1,1} and {1,1,0}, and we have proved that these 4 positions are N-positions. Therefore {1, 1, 2} is a P-position. Similarly {2, 1, 1} is a P-position.

Lemma 3.5.   $(1)$ For any non-negative integers $x, y$ with $x\geq y$ {x, y, 0} is an N-position of Game 2.
$(2)$ For any non-negative integers $y, z$ with $z\geq y$ {0, y, z} is an N-position of Game 2.

Proof.   From {x, y, 0} we can move to {0, 0, 0}, and hence {x, y, 0} is an N-position of Game 2.
Note that you get {0,0,0} by subtracting x and the condition of the inequality. Similarly {0, y, z} is an N-position of Game 2.

We are going to prove the following Theorem 3.2 that is essentially the same as Theorem 3.1.

Theorem 3.2.   $(1)$ Any element in $(B_0\cup B_+)$ is a P-position of Game 2.
$(2)$ Any element in {{x,y,z} , x + z $\geq$ y} - $(B_0\cup B_+)$ is an N-position of Game 2.

Proof.   We have already proved that any element in $B_ 0$ is a P-position of Game 2. We are going to use Mathematical induction on the size of sum of 3 coordinates.

$[1]$ { {x, y, z}, {x, y, z} $\in$ $(B_0\cup B_+)$and }$x + y + z \leq 4$ = {{0, 0, 0}, {1, 0, 1}, {1, 1, 2}, {2, 0, 2}, {2, 1, 1}}.

By Lemma 3.4 any position in {{x, y, z}, {x, y, z} $\in$ $(B_0\cup B_+)$ and $x + y + z \leq 4$} is a P-position of Game 2.

{{x,y,z}, $x + z \geq y$ and $x + y + z \leq 4$}- {{x, y, z}, {x, y, z} $\in$ $(B_0\cup B_+)$ and $x + y + z \leq 4$} = {{0, 0, 1}, {0, 0, 2}, {0, 0, 3}, {0, 0, 4}, {0, 1, 1}, {0, 1, 2}, {0, 1, 3}, {0, 2, 2}, {1, 0, 0}, {1, 0, 2}, {1, 0, 3}, {1, 1, 0}, {1, 1, 1}, {1, 2, 1}, {2, 0, 0}, {2, 0, 1}, {2, 1, 0}, {2, 2, 0}, {3, 0, 0}, {3, 0, 1}, {3, 1, 0}, {4, 0, 0}}, and hence by Lemma 3.4 any position in {{x,y,z}, $x + z \geq y$ and }$x + y + z \leq 4$ }- {{x, y, z}, {x, y, z} $\in$ $(B_0\cup B_+)$ and $x + y + z \leq 4$} is an N-position of Game 2. Therefore Theorem 2 is valid for any {x, y, z} such that $x + y + z \leq 4$.
$[2]$ We suppose that the conclusion of this theorem is valid for {x, y, z} with $x + y + z \leq k$.

$[2.1]$ We are going to prove $(1)$ of this theorem for {x, y, z} with $x + y + z = k + 1$. By Lemma 3.2 we have only to show that {x+1,y,z+1} is a P-position of Game 2 when (x+1) + y +(z+1) = k + 1, $x \oplus y \oplus z = 0$ and $y > 0$. It is sufficient to prove that any position that can be reached from {x+1,y,z+1} is an N-position of Game 2. Note that we have

$$x\neq z$$ (3.1)

,since $x \oplus y \oplus z = 0$ and $y > 0$.

$[2.1.1]$ Suppose that we move from {x+1,y,z+1} to {x+1,0,z+1}. By $(\ref{conditionxz})$ and Lemma 3.3 {x+1,0,z+1} is an N-position of Game 2.

$[2.1.2]$ Suppose that we move from {x+1,y,z+1} to {x+1,v,z+1} with v $<$ y. Since $x \oplus y \oplus z$ =0, by $(1)$ of Corollary 3.2 we have $x \oplus v \oplus z \neq 0$, and hence {x+1,v,z+1} $\in$ {{x,y,z}, $x + z \geq y$} - $(B_0\cup B_+)$ and $x+1+v+z+1\leq k$. Therefore by the hypothesis of Mathematical induction {x+1,v,z+1} is an N-position of Game 2.

$[2.1.3.1]$ Suppose that we move from {x+1,y,z+1} to {x+1,y ,w+1} with w $<$ z. Since $x \oplus y \oplus z = 0$, by $(1)$ of Corollary 3.2 we have $x \oplus y \oplus w \neq 0$. By the same argument that we used in $[2.1.2]$ we know that {x+1,y ,w+1} is an N-position of Game 2.

$[2.1.3.2]$ Suppose that we move from {x+1,y,z+1} to {x+1,y ,0}, then we have $y \leq x+1$. Therefore by Lemma 3.5 {x+1,y ,0} is an N-position of Game 2.

$[2.1.4.1]$ Suppose that we move from {x+1,y,z+1} to {x+1,v ,w+1} with v $<$ y and w $<$ z. This is a case that two coordinates decreased at the same time by the inequality between 3 coordinates, and hence we have (x+1)+(w+1) = v. Since x + w $<$ v, by Lemma 3.1 $x \oplus v \oplus w \neq 0$. By the hypothesis of mathematical induction {x+1,v ,w+1} is an N-position of Game 2.

$[2.1.4.2]$ Suppose that we move from {x+1,y,z+1} to {x+1,v ,0} with v $<$ y. Then by Lemma 3.5 {x+1,v ,0} is an N-position of Game 2.

When we subtract a natural number from the first coordinate, we can use the method that we used in $[2.1.3.1], [2.1.3.2], [2.1.4.1], [2.1.4.2]$.

$[2.2]$ We are going to prove $(2)$ of this theorem for {x, y, z} with $x + y + z = k + 1$. Let {p, q, r}$\in$ $\{\{x,y,z\}, x + z \geq y\}$ - $(B_0\cup B_+)$ such that p + q + r = k + 1. If $p = 0$ or $r = 0$, then by Lemma 3.5 {p, q, r} is an N-position of Game 2.
Now we can suppose that $p > 0$ and $r > 0$, and there exist non-negative numbers $x, y, z$ such that $p = x + 1$, $q = y$ and $r = z + 1$. Therefore we have only to show that {x+1,y,z+1} is an N-position of Game 2 when $(x+1) + y +(z+1) = k + 1$ and $x \oplus y \oplus z \neq 0$ and $y > 0$. It is sufficient to prove that there exists a P-position of Game 2 that can be reached from {x+1,y,z+1}. If $x \oplus y \oplus z \neq 0$, then by Corollary 3.2 at least one of the following three conditions are satisfied.

$[2.2.1]$ There exists u such that $u < x$ and $u \oplus y \oplus z = 0$. By Lemma 3.1 $u + z \geq y$, and hence $(u + 1) + (z + 1) \geq y$. Therefore by the hypothesis of mathematical induction we have that {u+1, y, z+1} is a P-position of Game 2.

$[2.2.2]$ There exists v such that $v < y$ and $x \oplus v \oplus z = 0$.
Similarly {x+1, v, z+1} is a P-position of Game 2.

$[2.2.3]$ There exists w such that $w < z$ and $x \oplus y \oplus w = 0$. Similarly {x+1, y, w+1} is a P-position of Game 2.