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 and we write them in base 2, so , and with , where .

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

Lemma 2.1   if and only if and for .
if and only if , for and for some .

Proof    When we write in base 2, and of this lemma is clear from the definition of floor function .

Lemma 2.2   We suppose that

 (2.1)

Then

 (2.2)

if and only if and for each

 (2.3)

and

 (2.4)

 (2.5)

if and only if there exists such that ,(2.4) is valid for each , (2.3) is valid for each and .

Proof    and are direct from Lemma 2.1 and the Definition 1.3 of nim-sum.

Remark 2.1   Suppose that and , then by using (2.3) and (2.4) repeatedly we get and for with some .
Clearly if and only if , and if and only if and . In particular, for any there exist unique that satisfy (2.1) and (2.2).

Lemma 2.3   We suppose that

 and (2.6)

If there exist such that and ,then .

Proof    By Lemma 2.2 we have and for each

 (2.7)

Suppose that there exist such that

 (2.8)

Clearly and . By Lemma 2.2 and Remark 2.1 there exists such that
for each

 (2.9)

and .
By using Lemma 2.2 and Remark 2.1 for we have for each

 (2.10)

Then by (2.9) and (2.10) we have
for each and , and hence we have .

Theorem 2.1   If and ,then
for any with .
for any with .
for any with .
for any with and .

Proof (1)   , (2) and (3) are direct from Theorem 1.1. We suppose that and for some with . If , then by Lemma 2.3 we have , and this contradicts the fact . If , then by Remark 2.1 we have , and this contradicts the fact . Therefore .

Lemma 2.4   For any there exists that satisfies one of the following two conditions.
and .
Let , then and .

Proof   Let

 (2.11)

for .
We assume that .
Suppose that the following is valid for .

 (2.12)

Then let . By of Lemma 2.1 we have , and hence by we have of this lemma.
Suppose that there exists such that

 (2.13)

and is valid for . Then let . By of Lemma 2.1 we have , and hence we have of this lemma.
Suppose that there exists such that for and .
We define for , , for , and

 (2.14)

 and (2.15)

for .
Let and . Clearly . By Lemma 2.1 we have , and hence we have of this lemma.
Suppose that . Then by the same method used in we get of this lemma.
Suppose that . Then let , , and for and .
Let and . Then we have .

Theorem 2.2   Suppose that and .
Then at least one of the following (1), (2), (3) and (4) is true.
for some with .
for some with .
for some with .
for some with and .

Proof   Suppose that for and .
If , we define by for and for . Then we have and . Therefore we have (1).
If , we define by for and for . Then we have and . Therefore we have (2).
Next we suppose that and .

By Lemma 2.4 For there exists that satisfies one of the following two conditions and .
satisfies and , then by the fact that for we have for , and hence by the fact that we have . Therefore we have
Let , then and . By the fact that for we have for , and hence by the fact that we have . Let , then we have .

Next we are going to define the function for a state of chocolates.
is the set of all states that can be reached from the state in one step (directly).

Definition 2.1   For we define , where .

Example 2.1   We study the function using examples of states in Example 1.2 . If we start with the state and reduce to , then the second coordinate will be .
Therefore we have . It is easy to see that
. It is clear that , since we cannot move to from . Note that , since it will take 2 steps to reach from .

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

Theorem 2.3   For any we have .

Proof   Let , then we have

 (2.16)

and

 (2.17)

Suppose that we move from to ,i.e., . Next we prove that .
Since ,by Theorem 2.1 .

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

Theorem 2.4   Let , then .

Proof   Let . Then have

 (2.18)

and

 (2.19)

Since , by Theorem 2.2 there exists such that
. Therefore .

By Theorem 2.3 and 2.4 we finish the proof of Theorem 1.2. If we start the game with a state , then by Theorem 2.3 any option by us leads to a state in . From this state by Theorem 2.4 our opponent can choose a proper option that leads to a state in . Note that any option reduces some of the numbers in the coordinates. In this way our opponent can always reach a state in , and finally he wins by reaching . Therefore is the set of L states.
If we start the game with a state , then by Theorem 2.4 we can choose a proper option leads to a state in . From any option by our opponent leads to a state in . In this way we win the game by reaching . Therefore is the set of W states.

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