Next: Chocolates without simple formulas Up: Chocolate games that are Previous: Introduction


2. A proof of Theorem 1.2

In this section we assume that $ x,y,z\in Z_{\geqq0}$ and we write them in base 2, so $ x=\displaystyle\sum_{i=0}^{n} x_i2^i$ , $ y=\displaystyle\sum_{i=0}^{n} y_i2^i$ and $ z=\displaystyle\sum_{i=0}^{n} z_i2^i$ with $ x_{i},y_{i},z_{i}\in \{0,1\}$ , where $ n = log_2 max(x,y,z)$ .

In this section we prove Theorem 1.2, and we need several facts about the relations between numbers in base $ 2$ , the nim-sum of numbers and the floor function.

Lemma 2.1   $ (1)$ $ y=\left\lfloor \frac{z}{2} \right\rfloor$ if and only if $ y_{n} = 0$ and $ y_{i} = z_{i+1}$ for $ i = 0,1,2,...,n-1$ .
$ (2)$ $ y < \left\lfloor \frac{z}{2} \right\rfloor$ if and only if $ y_{n} = 0$ , $ y_{i} = z_{i+1}$ for $ i = m+1,m+2,...,n-1$ and $ y_{m} = 0 < z_{m+1} = 1$ for some $ m\in Z_{\geq 0}$ .

Proof    When we write $ y,z$ in base 2, $ (1)$ and $ (2)$ of this lemma is clear from the definition of floor function $ \left\lfloor \ \right\rfloor$ .

Lemma 2.2   We suppose that

$\displaystyle x\oplus y\oplus z=0.$ (2.1)

$ (1)$ Then

$\displaystyle y= \left\lfloor \frac{z}{2} \right\rfloor$ (2.2)

if and only if $ x_{n} = z_{n} = 1, y_{n} = 0$ and for each $ i = 0,1,2,...,n-1$

$\displaystyle y_{i}=z_{i+1}$ (2.3)

and

$\displaystyle z_{i}=x_{i}+y_{i} \ (mod \ 2).$ (2.4)

$ (2)$

$\displaystyle y< \left\lfloor \frac{z}{2} \right\rfloor$ (2.5)

if and only if there exists $ m\in Z_{\geqq0}$ such that $ x_{n} = z_{n} = 1, y_{n} = 0$ ,(2.4) is valid for each $ i = 0,1,2,...,n-1$ , (2.3) is valid for each $ i = m+1,m+2,...,n-1$ and $ y_{m} = 0 < z_{m+1} = 1$ .

Proof    $ (1)$ and $ (2)$ are direct from Lemma 2.1 and the Definition 1.3 of nim-sum.

Remark 2.1   Suppose that $ x\oplus y\oplus z= 0$ and $ y \leq \left\lfloor \frac{z}{2} \right\rfloor$ , then by using (2.3) and (2.4) repeatedly we get $ z_{i}=\displaystyle\sum_{j=i}^{n} x_j \ (mod\ 2)$ and $ y_{i}=\displaystyle\sum_{j=i+1}^{n} x_j \ (mod\ 2)$ for $ i = k,k+1,k+2,...n-1$ with some $ k \in Z_{\geqq0}$ .
Clearly $ y=\left\lfloor \frac{z}{2} \right\rfloor$ if and only if $ k = 0$ , and $ y < \left\lfloor \frac{z}{2} \right\rfloor$ if and only if $ k > 0$ and $ y_{k-1} < z_k$ . In particular, for any $ x$ there exist unique $ y,z$ that satisfy (2.1) and (2.2).

Lemma 2.3   We suppose that

$\displaystyle x\oplus y\oplus z=0$    and $\displaystyle y = \left\lfloor \frac{z}{2} \right\rfloor.$ (2.6)

If there exist $ v,w\in Z_{\geq 0}$ such that $ x\oplus v\oplus w=0$ and $ v<\left\lfloor \frac{w}{2} \right\rfloor$ ,then $ v<y$ .

Proof    By Lemma 2.2 we have $ {x_n} = {z_{_n}} = 1,{y_n} = 0$ and for each $ i = 0,1,2,...,n-1$

$\displaystyle {y_i} = {z_{i + 1}},{z_i} = {x_i} + {y_i}\ (mod\ 2).$ (2.7)

Suppose that there exist $ v,w\in Z_{\geq 0}$ such that

$\displaystyle x\oplus v\oplus w=0\ and\ v < \left\lfloor {w/2} \right\rfloor.$ (2.8)

Clearly $ v_{n}=0$ and $ w_n=1$ . By Lemma 2.2 and Remark 2.1 there exists $ m \in {Z_{ \ge 0}}$ such that
for each $ i=m+1,m+2,...n-1$

$\displaystyle {w_i} = \sum\limits_{j = i}^n {{x_i}}\ (mod\ 2),{v_i} = \sum\limits_{j = i + 1}^n {{x_i}}\ (mod\ 2)$ (2.9)

and $ v_m<w_{m+1}$ .
By using Lemma 2.2 and Remark 2.1 for $ x,y,z$ we have for each $ i = 0,1,2,...,n-1$

$\displaystyle {z_i} = \sum\limits_{j = i}^n {{x_i}}\ (mod\ 2),{y_i} = \sum\limits_{j = i + 1}^n {{x_i}}\ (mod\ 2).$ (2.10)

Then by (2.9) and (2.10) we have
$ v_i=y_i$ for each $ i=m+1,m+2,...n-3,n-2,n-1$ and $ v_m<y_m$ , and hence we have $ v<y$ .

Theorem 2.1   If $ x\oplus y\oplus z= 0$ and $ y \le \left\lfloor {z/2} \right\rfloor$ ,then
$ (1)$ $ u \oplus y \oplus z \ne 0$ for any $ u\in Z_{\geq 0}$ with $ u<x$ .
$ (2)$ $ x \oplus v \oplus z \ne 0$ for any $ v\in Z_{\geq 0}$ with $ v<y$ .
$ (3)$ $ x \oplus y \oplus w \ne 0$ for any $ w\in Z_{\geq 0}$ with $ w<z$ .
$ (4)$ $ x \oplus v \oplus w \ne 0$ for any $ v,w\in Z_{\geq 0}$ with $ v<y,w<z$ and $ v = \left\lfloor {w/2} \right\rfloor$ .

Proof (1)   , (2) and (3) are direct from Theorem 1.1. We suppose that $ x\oplus v\oplus w=0$ and $ v = \left\lfloor {w/2} \right\rfloor$ for some $ v,w \in {Z_{ \ge 0}}$ with $ v<y,w<z$ . If $ y < \left\lfloor {z/2} \right\rfloor $ , then by Lemma 2.3 we have $ y<v$ , and this contradicts the fact $ v<y$ . If $ y = \left\lfloor {z/2} \right\rfloor $ , then by Remark 2.1 we have $ y=v$ , and this contradicts the fact $ v<y$ . Therefore $ x \oplus v \oplus w \ne 0$ .

Lemma 2.4   For any $ x,y \in {Z_{ \ge 0}}$ there exists $ z$ that satisfies one of the following two conditions.
$ [i]$ $ x\oplus y\oplus z= 0$ and $ y \le \lfloor {z/2} \rfloor$ .
$ [ii]$ Let $ y^\prime = \lfloor z/2 \rfloor$ , then $ y^\prime < y$ and $ x\oplus y^\prime \oplus z=0$ .

Proof   Let

$\displaystyle u_i = x_i+y_i \ (mod \ 2)$ (2.11)

for $ i = 0,1,2,...,n$ .
$ [a]$   We assume that $ y_n = 0$ .
$ [a-1]$ Suppose that the following % latex2html id marker 3175 $ (\ref{condition1})$ is valid for $ i = 0,1,...,n-1$ .

$\displaystyle y_i = u_{i+1}.$ (2.12)

Then let $ z =u = \sum\limits_{i = 0}^n {{u_i}} {2^i}$ . By $ (1)$ of Lemma 2.1 we have $ y = \lfloor {z/2} \rfloor$ , and hence by % latex2html id marker 3188 $ (\ref{condition12a})$ we have $ [i]$ of this lemma.
$ [a-2]$ Suppose that there exists $ m$ such that

$\displaystyle y_m=0 < 1 = u_{m+1},$ (2.13)

and % latex2html id marker 3199 $ (\ref{condition1})$ is valid for $ i = m+1,m+2,...,n-1$ . Then let $ z =u = \sum\limits_{i = 0}^n {{u_i}} {2^i}$ . By $ (2)$ of Lemma 2.1 we have $ y < \lfloor {z/2} \rfloor$ , and hence we have $ [i]$ of this lemma.
$ [a-3]$ Suppose that there exists $ m$ such that $ y_i$ $ =u_{i+1}$ for $ i = m+1,m+2,...,n-1$ and $ y_m=1>$ $ 0 = u_{m+1}$ .
We define $ y^\prime _i = y_i$ for $ i = m+1,m+2,...,n$ , $ y^\prime _m = 0$ , $ z_i = u_i$ for $ i = m+1,m+2,...,n$ , $ z_m = y^\prime _m + x_m$ $ (mod 2)$ and

$\displaystyle y^\prime _i = z_{i+1}$ (2.14)

and $\displaystyle z_i = x_i + y^\prime _i \ (mod \ 2)$ (2.15)

for $ i = 0,1,2,...,m-1$ .
Let $ z = \sum\limits_{i = 0}^n {{z_i}} {2^i}$ and $ y^\prime = \sum\limits_{i = 0}^n {{y^\prime _i}} {2^i}$ . Clearly $ y^\prime < y$ . By Lemma 2.1 we have $ y^\prime = \lfloor z/2 \rfloor$ , and hence we have $ [ii]$ of this lemma.
$ [a-4]$ Suppose that $ y_{n-1} = 1 > 0 = u_n$ . Then by the same method used in $ [a-3]$ we get $ [ii]$ of this lemma.
$ [b]$ Suppose that $ y_n=1$ . Then let $ y^\prime _n = 0$ , $ z_n = x_n + y^\prime _n \ (mod \ 2 )$ , and for $ i = 0,1,2,...,n-1$ $ y^\prime _i =z_{i+1}$ and $ z_i = y^\prime _i + x_i$ $ (mod 2)$ .
Let $ z = \sum\limits_{i = 0}^n {{z_i}} {2^i}$ and $ y^\prime = \sum\limits_{i = 0}^n {{z^\prime _i}} {2^i}$ . Then we have $ [ii]$ .

Theorem 2.2   Suppose that $ x \oplus y \oplus z \ne 0$ and $ y \le \left\lfloor {z/2} \right\rfloor$ .
Then at least one of the following (1), (2), (3) and (4) is true.
$ (1)$ $ u \oplus y \oplus z = 0$ for some $ u \in {Z_{ \ge 0}}$ with $ u<x$ .
$ (2)$ $ x \oplus v \oplus z = 0$ for some $ v \in {Z_{ \ge 0}}$ with $ v<y$ .
$ (3)$ $ x \oplus y \oplus w = 0$ for some $ w \in {Z_{ \ge 0}}$ with $ w<z$ .
$ (4)$ $ x\oplus v\oplus w=0$ for some $ v,w \in {Z_{ \ge 0}}$ with $ v<y,w<z$ and $ v = \left\lfloor {w/2} \right\rfloor$ .

Proof   Suppose that $ x_i +y_i +z_i =0\ (mod\ 2)$ for $ i = m+1,m+2,...,n$ and $ x_m +y_m +z_m \neq 0\ (mod\ 2)$ .
$ (a)$ If $ x_m=1$ , we define $ u= \sum_{i=0}^{n} u_i 2^i$ by $ u_i=x_i$ for $ i=m+1,m+2,...n,u_m=0<x_m$ and $ u_i=y_i+z_i$ for $ i=0,1,...,m-1$ . Then we have $ u \oplus y \oplus z \oplus =0$ and $ u<x$ . Therefore we have (1).
$ (b) $ If $ y_m=1$ , we define $ v= \sum_{i=0}^{n} v_i 2^i$ by $ v_i=y_i$ for $ i=m+1,m+2,...n,v_m=0<y_m$ and $ v_i=x_i+z_i$ for $ i=0,1,...,m-1$ . Then we have $ x \oplus v \oplus z \oplus =0$ and $ v<y$ . Therefore we have (2).
$ (c)$ Next we suppose that $ x_m=y_m=0$ and $ z_m=1$ .

By Lemma 2.4 For $ x,y$ there exists $ w= \sum_{i=0}^{n} w_i 2^i$ that satisfies one of the following two conditions $ [i]$ and $ [ii]$ .
$ [i]$ $ \{x,y,w\}$ satisfies $ x \oplus y \oplus w = 0$ and $ y \le \lfloor {w/2} \rfloor$ , then by the fact that $ x_i +y_i +z_i =0\ (mod\ 2)$ for $ i = m+1,m+2,...,n$ we have $ w_i = z_i$ for $ i = m+1,m+2,...,n$ , and hence by the fact that $ w_m = x_m + y_m = 0 < 1 = z_m$ we have $ w<z$ . Therefore we have $ (3)$
$ [ii]$ Let $ y^\prime = \lfloor w/2 \rfloor$ , then $ y^\prime < y$ and $ x\oplus y^\prime \oplus w=0$ . By the fact that $ x_i +y_i +z_i =0\ (mod\ 2)$ for $ i = m+1,m+2,...,n$ we have $ w_i = z_i$ for $ i = m+1,m+2,...,n$ , and hence by the fact that $ w_m = x_m + y_m = 0 < 1 = z_m$ we have $ w<z$ . Let $ v = y^\prime$ , then we have $ (4)$ .

Next we are going to define the function $ move (\{x, y, z\})$ for a state $ \{x, y, z\}$ of chocolates.
$ move (\{x, y, z\})$ is the set of all states that can be reached from the state $ \{x, y, z\}$ in one step (directly).

Definition 2.1   For $ x,y,z \in Z_{\ge 0}$ we define $ move(\{x,y,z\})=\{\{u,y,z \};u<x \} \cup \{\{x,v,z \};v<y \} \cup \{ \{x,y,w \};w<z \} \cup \{ \{x,min(y, \lfloor w/2 \rfloor ),w \};w<z \}$ , where $ u,v,w \in Z_{\ge 0}$ .

Example 2.1   We study the function $ move (\{x, y, z\})$ using examples of states in Example 1.2 . If we start with the state $ \{x,y,z\}=\{2,2,5\}$ and reduce $ z=5$ to $ w=3$ , then the second coordinate will be $ min(2, \lfloor 3/2 \rfloor )=min(2,1)=1$ .
Therefore we have $ \{2,1,3\} \in move(\{ 2,2,5 \})$ . It is easy to see that
$ \{0,2,5\},\{2,0,5\} \in move(\{2,2,5\})$ . It is clear that $ \{0,2,5\} \notin move(\{2,1,3\})$ , since we cannot move to $ \{0, 2, 5\}$ from $ \{2, 1, 3\}$ . Note that $ \{0,1,5\} \notin move(\{2,2,5\})$ , since it will take 2 steps to reach $ \{0, 1, 5\}$ from $ \{2,2,5\}$ .

Next we prove that if you start with an element of $ A_2$ , then any move leads to an element of $ B_2$ .

Theorem 2.3   For any $ \{x,y,z\} \in A_2$ we have $ move(\{x,y,z\}) \subset B_2$ .

Proof   Let $ \{x,y,z\} \in A_2$ , then we have

$\displaystyle x \oplus y \oplus z \oplus =0$ (2.16)

and

$\displaystyle y \leq \left\lfloor z/2 \right\rfloor.$ (2.17)

Suppose that we move from $ \{x, y, z\}$ to $ \{p,q,r\}$ ,i.e., $ \{p,q,r\} \in move(\{x,y,z \})$ . Next we prove that $ \{p,q,r\} \in B_2$ .
Since $ move(\{x,y,z\})=\{\{u,y,z\};u<x\} \cup \{\{x,y,z\};v<y\} \cup \{ \{x,y,w \};w<z \} \cup \{\{x,min(y,\lfloor w/2 \rfloor ),w\};w<z\}$ ,by Theorem 2.1 $ p \oplus q \oplus r \oplus \ne 0$ .

Next we prove that if you start with an element of $ B_2$ , then there is a proper move that leads to an element of $ A_2$ .

Theorem 2.4   Let $ \{x,y,z\} \in B_2$ , then $ move(\{x,y,z\})\cap A_2 \ne \phi$ .

Proof   Let $ \{x,y,z\} \in B_2$ . Then have

$\displaystyle x \oplus y \oplus z \oplus \ne 0$ (2.18)

and

$\displaystyle y \leq \left\lfloor z/2 \right\rfloor.$ (2.19)

Since $ move(\{x,y,z\})= \{\{u,y,z\};u < x\} \cup \{\{x,v,z\};v<y\}$ $ \cup \{ \{x,y,w \};w<z \} \cup \{\{x,min\left( y,\lfloor \frac{w}{2} \rfloor\right),w\};w<z\}$ , by Theorem 2.2 there exists $ \{p,q,r\} \in move\left(\{x,y,z\}\right)$ such that
$ p\oplus q\oplus r= 0$ . Therefore $ \{p,q,r\} \in move(\{x,y,z\})\cap A_2 $.

By Theorem 2.3 and 2.4 we finish the proof of Theorem 1.2. If we start the game with a state $ \{x,y,z\}\in A_{2}$ , then by Theorem 2.3 any option by us leads to a state $ \{p,q,r\}$ in $ B_2$ . From this state $ \{p,q,r\}$ by Theorem 2.4 our opponent can choose a proper option that leads to a state in $ A_2$ . Note that any option reduces some of the numbers in the coordinates. In this way our opponent can always reach a state in $ A_2$ , and finally he wins by reaching $ \{0,0,0\}\in A_{2}$ . Therefore $ A_2$ is the set of L states.
If we start the game with a state $ \{x,y,z\}\in B_{2}$ , then by Theorem 2.4 we can choose a proper option leads to a state $ \{p,q,r\}$ in $ A_2$ . From $ \{p,q,r\}$ any option by our opponent leads to a state in $ B_2$ . In this way we win the game by reaching $ \{0,0,0\}$ . Therefore $ B_2$ is the set of W states.



Next: Chocolates without simple formulas Up: Chocolate games that are Previous: Introduction