In this subsection we study a sufficient condition for a chocolate bar to have a Grundy number
.
In our proofs, it will be useful to have the disjunctive sum of a chocolate bar to the right of the bitter square and a single strip of chocolate bar to the left, as in Figures 3.1, 3.2, 3.3, 3.4, 3.5 and 3.6. We will denote such a position by
, where
is the length of the single strip of chocolate bar and
are coordinates of
. Figures 3.4, 3.5 and 3.6 give some examples of the coordinate system. For the disjunctive sum of the chocolate bar game with
to the right of the bitter square and a single strip of chocolate bar to the left, we will show that the
-positions are when
, so that the Grundy number of the chocolate bar
is
.
Example 3.1. Examples of coordinates of chocolate bar games.
Figure 3.1.
{4,7,12}
Figure 3.2.
{3,5,10}
Figure 3.3.
{0,4,6}
Figure 3.4.
Figure 3.5.
Figure 3.6.
is the set that contains all the positions that can be reached from the position
in one step (directly).
Definition 3.1. For , we define
, where
.
The following condition in Definition 3.2 is a sufficient condition for a chocolate bar
to have a Grundy number
.
Definition 3.2. Let be a function of
into
that satisfies the conditions of Definition 2.1. and the following condition
.
Suppose that
![]() |
(3.1) |
for some and some natural number
. Then we have
![]() |
(3.2) |
Remark 3.1. The condition of Definition 3.2 is equivalent to the following condition
.
Suppose that
for
and
![]() |
Let be a natural number. Then for any
for
there exist
for
such that
![]() |
The condition of Definition 3.2 is very abstract, so we present some examples of functions that satisfy condition
of Definition 3.2 in Lemma 3.1 and Lemma3.2.
Lemma 3.1. Let for some natural number
. Then
satisfies the condition of Definition 3.2. We prove the contraposition of the condition of Definition 3.2. We suppose that Equation (3.2) is false. Then there exist
and a natural number
such that
![]() |
(3.3) |
We prove that Equation (3.1) is false. From the inequality in (3.3), we have
![]() |
and hence
![]() |
(3.4) |
From the inequality in (3.4), we have
![]() |
Therefore we have
![]() |
This shows that Equation (3.1) is false. Therefore, we have completed the proof of this lemma.
Lemma 3.2. Let and
for
such that
. Then
satisfies the condition of Definition 3.2. We prove the contraposition of the condition of Definition 3.2. Suppose that Equation (3.2) is false. Then for a natural number
![]() |
(3.5) |
We prove that Equation (3.1) is false. Let and
such that
and
. Then by the inequality in (3.5), we have
![]() |
(3.6) |
By the inequality in (3.6), we have
![]() |
(3.7) | ||
![]() |
|||
![]() |
(3.8) |
By the inequalities in (3,7) and (3.8), we have
![]() |
This shows that Equation (3.1) is false. Therefore we have completed the proof.
In the remainder of this subsection we assume that is the function that satisfies the condition
in Definition 3.2. Our aim is to show that the disjunctive sum of the chocolate bar game with
to the right of the bitter square and a single strip of chocolate bar to the left have
-positions when
, so that the Grundy number of the chocolate bar
is
.
We need Lemma3.6and Lemma3.7 for this aim. Lemma 3.6 implies that from a position of the disjunctive sum such that
you always have a option that leads to a position for which the nim-sum of the coordinates is
. Lemma 3.7 implies that from a position
of the disjunctive sum such that
any option leads to a position for which the nim-sum of the coordinates is not
.
To prove Lemma 3.6 and Lemma 3.7 we need some properties of the function that satisfies the condition
in Definition 3.2. These properties are proved in Lemma 3.3, Lemma 3.4 and Lemma 3.5.
Lemma 3.3. Suppose that
![]() |
(3.9) |
Then, for any natural number ,
![]() |
Proof. Let for
. Then, by the inequality in (3.9),
![]() |
and hence
![]() |
(3.10) |
Let for
. By the inequality in (3.10), Definition 3.2 and Remark 3.1, there exist
for
such that
![]() |
Lemma 3.4.
Suppose that for some natural number
![]() |
(3.11) |
Then
![]() |
Suppose that
![]() |
Then
![]() |
We prove . Let
for
. Then, by Remark 3.1, there exist
for
such that
. Then, by the inequality in (3.11), we have
![]() |
and hence we have the inequality in (3.12) or Relation (3.13).
![]() |
(3.12) |
There exists such that
![]() |
(3.13) |
Then, by the inequality in (3.12) or Relation (3.13),
![]() |
We prove . This is the contraposition of the proposition in
of this lemma.
Lemma 3.5. Suppose that
![]() |
(3.14) |
Then
![]() |
Proof. Let and
. Then, by the inequality in (3.14), we have
, and statement
of Lemma 3,4 implies
. Therefore we have completed the proof of this lemma.
If the nim-sum of the cooridinates of a position is not 0, then by Definition 3.1and the following Lemma 3.6, there is always an option that leads to a position whose nim-sum is 0.
Lemma 3.6. Suppose that and
![]() |
(3.15) |
Then at least one of the following statements is true.
for some
such that
.
for some
such that
.
for some
such that
and
.
for some
such that
and
.
Proof. Let ,
and
. If
, then this lemma is obvious. We assume that
. Suppose that there exists a non-negative integer
such that
for
and
![]() |
(3.16) |
Case Suppose that
. Then, we define
by
for
,
and
for
. Then we have
and
. Therefore, we have statement
of this lemma.
Case Suppose that
. Then, by the method that is similar to the one used in
, we prove that
for some
such that
. Therefore we have statement
of this lemma.
Case We suppose that
![]() |
(3.17) |
For , let
![]() |
(3.18) |
Let for
. By the inequality in (3.16) and Equation (3.17), we have
, and hence
![]() |
(3.19) |
Subcase If
, then we have statement
of this lemma.
Subcase Next we suppose that
![]() |
(3.20) |
By the inequality in (3.15), we have , and hence by Lemma 3.3 and (3.18)
![]() |
(3.21) |
By the inequalities in (3.21) and (3.20), there exists a natural number such that
![]() |
(3.22) | ||
![]() |
(3.23) |
By the inequalities in (3.21) and (3.23),
![]() |
(3.24) |
By the inequality in (3.22) and of Lemma 3.4,
![]() |
(3.25) |
By the inequality in (3.23),
![]() |
(3.26) |
By the inequalities in (3.25) and (3.26), we have
![]() |
(3.27) |
We construct and
by assigning values to
and
for
. First, for
, let
![]() |
(3.28) |
and let
![]() |
(3.29) |
and
![]() |
Since and
, by the inequality in (3.27)
![]() |
(3.30) |
By the inequality in (3.30) and Lemma 3.5, we have
![]() |
(3.31) |
Next we prove the inequality in (3.32) for any recursively.
![]() |
(3.32) |
By the inequality in (3.31), we have the inequality in (3.32) for . We suppose the inequality in (3.32) for some natural number
such that
. Then we have the inequality in (3.33) or the inequality in (3.36). Our aim is to prove (3.35) and (3.38) by using these inequalities.
If
![]() |
(3.33) |
then let and
. Since
, by the inequality in (3.33) we have
![]() |
(3.34) |
Note that . By Lemma 3.5 and the inequality in (3.34),
![]() |
(3.35) |
If
![]() |
(3.36) |
then let and
.
Since , the inequalities in (3.36) and (3.32) give
![]() |
(3.37) |
Then, by the inequality in (3.37) and Lemma 3.5, we have
![]() |
(3.38) |
In this way we get the inequality in (3.35) or the inequality in (3.38) by the inequality in (3.32). Note that the inequality in (3.35) and the inequality in (3.38) are the same inequality. By continuing this process we have
![]() |
Therefore, we have By iequalities (3.19), (3.24), (3.29) and Equation (3.28), we have
and
. Therefore, we have statement
of this lemma. If the nim-sum of the cooridinates of a position is 0, then by Definition 3.1 and the following Lemma 3.7, any option from this position leads to a position whose nim-sum is not 0.
Lemma 3.7. If and
, then the following hold:
for any
such that
.
for any
such that
.
for any
such that
.
for any
such that
and
. Statements
,
and
of this lemma follow directly from Definition 1 (the definition of nim-sum).
We now prove statement . We suppose that
for some
such that
. We also suppose that
![]() |
(3.39) |
By , we have
. Hence, by Lemma 3.3, we have
![]() |
(3.40) |
Since and
, Relation (3.39) gives
![]() |
(3.41) |
By the inequalities in (3.40) and (3.41), we have
![]() |
Hence, for ,
![]() |
(3.42) |
Since , we have
![]() |
(3.43) |
By Relation (3.39), Equation (3.42) and Equation (3.43), we have , and hence
.
Let and
and
and
.
Let and
be the sets defined in Definition 3.3. Then the following hold:
If we start with a position in
, then any option (move) leads to a position in
.
If we start with a position in
, then there is at least one option (move) that leads to a position in
.
Since that is defined in Definition 3.1 contains all the positions that can be reached from the position
in one step, we have statements
and
by Lemma 3.7 and Lemma 3.6 respectively.
Theorem 3.1. Let and
be the sets defined in Definition 3.3.
is the set of
-positions and
is the set of
-positions of the disjunctive sum of the chocolate bar game with
to the right of the bitter square and a single strip of chocolate bar to the left. If we start the game from a position
, then Lemma 3.8 indicates that any option we take leads to a position
in
. From this position
, Lemma 3.8 implies that our opponent can choose a proper option that leads to a position in
. Note that any option reduces some of the numbers in the coordinates. In this way, our opponent can always reach a position in
, and will finally win by reaching
. Note that position
represent the bitter square itself, and we cannot eat this part. Therefore
is the set of
-positions.
If we start the game from a position , then Lemma 3.8 means that we can choose a proper option that leads to a position
in
. From
, Lemma 3.8 implies that any option taken by our opponent leads to a position in
. In this way we win the game by reaching
. Note that our opponent cannot eat the bitter part. Therefore
is the set of
-position
Theorem 3.2 Let be the function that satisfies the condition
in Definition 3.2. Then the Grundy number of
is
.
Proof. By Theorem 3.1, a position of the sum of the chocolate bars is a
-position when
. Therefore, Theorem 1.1 implies that the Grundy number of the chocolate bar to the right is
.
By Theorem 3,2, the condition of Definition 3.2 is a sufficient condition for the chocolate bar to have the Grundy number
. Lemma 3.1, Lemma 3.2 and Theorem 3.2 imply that chocolate bar games in Figure 2.1, Figure 2.2, Figure 2.3 and Figure 2.4 have the Grundy number
.
In the next subsection we prove that the condition of Definition 3.2 is a necessary condition for the chocolate bar to have the Grundy number
.