Chocolate games that satisfy the inequality .

Brown blocks are sweet and the blue block is very bitter. This game is played by two players in turn. Each player breaks the chocolate (in a straight line along the blue line) into two area.

The player eats the area that does not contain blue block. The player who breaks the chocolate and eats to leave his opponent with the single bitter block (blue block) is the winner.

When we study the chocolate games, there are two important states of chocolates.

W-states, from which we can force a win, as long as we play correctly at every stage.

L-states, from which we will lose however well we play, but we may end up winning if our opponents make a mistake.

One of the most important topics of chocolate games is to find all the L-states and the W-states of games. We denote by the set of non-negative integers.

We define the nim-sum by

(2.1) |

we have .

We generalize the chocolate games in Fig. 2.2, and define the chocolate game that we study in this article.

The i-th column is block for and the i-th column is block for .

The generalization of the chocolate in Fig. 2.3 is the chocolate in Fig. 2.4. In this chocolate we have the first, the second, the fourth,...,n-th column,... on the right side of the blue block and th, th,..., -th column,... on the left side of the blue block.

The i-th column is block for and the i-th column is block for .

Brown blocks are sweet chocolate that can be eaten, and the blue block is the bitter chocolate that cannot be eaten.

You cut vertically on the left side of the blue (bitter) block.

You cut horizontally above the blue (bitter) block.

You cut vertically on the right side of the blue (bitter) block.

Therefore it is proper to represent this chocolate with , where stand for the maximum numbers of times that we can cut these chocolate in each direction. For example in Fig. 2.3 we can cut 6 times at most vertically on the left side of the blue block, we can cut 6 times at most horizontally above the blue (bitter) block and we can 12 times at most vertically on the right side of the blue block. Therefore , and . Therefore we represent the chocolate in Fig. 2.3 with the coordinates .

**Example 2.2**
*Here we have four examples of states of chocolates that appear when we play the chocolate game of Fig. 2.5*

where is the floor function. Note that is the largest integer not greater than for any real number .

Note that you can cut block horizontally times at most for any non-negative integer .

Inequality (2.2) is important to understand the structure of the chocolate. If you start with the chocolate in Fig. 2.5 and reduce the third coordinate to by cutting vertically on the right side of the bitter block, then by the structure of the chocolate the second coordinate is reduced to .

In this way we get the chocolate in Fig. 2.6.

If we are to explain the move from the chocolate in Fig. 2.5 to the chocolate in Fig. 2.6 using Inequality (2.2), we use the following explanation.

Let , then by Inequality (2.2) we get .

**Definition 2.5**
*Let
and
,
and
.
*

Next we prove that
is the set of L-states and
is the set of W-states of the game of Definition 2.4.
To do this we need some lemmas and theorems.
In this section we assume that
and we write them in base 2, so
,
and
with
, where
.

In this section we prove Theorem 2.6, and
we need several facts about the relations between 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
.
*

(2.7) |

Clearly if and only if , and if and only if and .

Therefore and are determined by when we have (2.3) and (2.4). In particular, for any there exist unique that satisfy (2.3) and (2.4).

By using Lemma 2.2 and Remark 2.3 for we have for each

for each and , and hence we have .

for any with .

for any with .

for any with .

for any with and .

and .

and .

. We assume that .

Suppose that the following (2.14) is valid for .

Suppose that there exists such that

Suppose that there exists such that for and .

We define for , , for , .

Next let and . In this way we let

(2.16) |

and | (2.17) |

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 by using the method in we let and for .

Let and . Then , and we have .

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 .

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 .

and , then by the fact that for we have for , and hence by the fact that we have . Therefore we have .

and . By the fact that for we have for , and hence by the fact that we have . Then we have .

is the set of all states that can be reached from the state in one step (directly).

**Example 2.3**
*We study the function
using examples of states in Example 2.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 .

(2.18) |

(2.19) |

Since , we have one of the following , , and .

with .

with .

with and .

with .

In each of these , , and we use Theorem 2.2 to get .

(2.20) |

(2.21) |

*
Since
, by
,
,
and
of Theorem 2.3 there exists
such that
. Therefore
*

If we start the game with a state , then by Theorem 2.5 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.

In this way you should leave the opponent with an L-state every time until you leave the opponent with the single block of bitter chocolate whose coordinates are . Then the game is finished, and you win the game.