Let be the function that satisfies the condition
in Definition 3.2 and let
be the Grundy number of
. The condition
in Definition 3.2 is a necessary and sufficient condition for
to have the Grundy number
, and we can use all the lemmas and theorems in previous sections for the function
and
.
Definition 4.1. We define the function as the followings.
Let be a natural number such that
![]() |
Let for any
.
We are going to show that the condition in Definition 4.1 is a necessary and sufficient condition for the chocolate bar to have the Grundy number
.
Lemma 4.1. Let and
be a natural number. Then
![]() |
(4.5) |
if and only if there exist a natural number and a non-negative integer
such that
![]() |
(4.6) |
Proof. We suppose Relation (4.5). When , let
with
and
. Let
with
and
. Since
and
,
. Since
,
. Therefore,
for
. Let
and
, then we have Relation (4.6). When
, we let
and
. Then we have Relation (4.6).
Next we suppose that there exist a natural number and a non-negative integer
that satisfy Relation (4.6). Then it is clear that we have Relation (4.5).
Lemma 4.2. Let and
be a natural number such that
for
. Let
such that
. Then
![]() |
(4.7) |
Proof. By Lemma 4.1, there exist a natural number and a non-negative integer
such that
and
.
Let such that
. Then we write
in base 2, and we have
. We prove that
for
. Let
such that
. Then there exist
such that
and
for
. Therefore,
![]() |
(4.8) |
Since for
such that
, the inequality in (4.8) implies Relation (4.7).
Lemma 4.3. Let be a natural number,
and
for
. Suppose that
for
. Then
if and only if
.
Proof. Suppose that . By Lemma 1.1,
, and hence
. Let
such that
. Then
, and Lemma 1.1 implies
. Clearly
for some natural number
, and hence
. By Lemma 1.1, we have
.
Conversely we suppose that . Then, Lemma 1.1 implies
for any
, and hence
for any
. For any
such that
, Lemma 1.1 implies that there exists
such that
and
. By Lemma 1.1, there exists
such that
, and hence we have
. Therefore Lemma 1.1 implies
.
Lemma 4.4. Let be a natural number such that
![]() |
(4.9) |
Then, for any such that
, we have
![]() |
|||
![]() |
(4.10) |
In particular .
Proof. By Theorem 3.2 and the definition of Grundy number,
![]() |
|||
![]() |
|||
![]() |
|||
![]() |
(4.11) |
When , we have
, and hence
. Since
and
, Lemma 3.10, Equation (4.9) and Lemma 4.2 imply
. Hence, by Theorem 3.2,
![]() |
(4.12) |
Equation (4.11) and Equation (4.12) imply Equation (4.10). Therefore, by Lemma 1, we have .
Lemma 4.5. Let be a natural number such that
![]() |
(4.13) |
For any such that
, we have
![]() |
(4.14) |
Proof. By Relation (4.13) and Lemma 4.4, we have
![]() |
![]() |
(4.15) |
for any such that
.
Since , Lemma 4.4 implies that for
![]() |
(4.16) |
Since , Lemma 4.4 implies that for
![]() |
(4.17) |
Lemma 4.3, the inequality in (4.16), the inequality in (4.17) and Equation (4.15) imply (4.14). We have completed the proof.
Theorem 4.1. Let be a natural number such that
![]() |
(4.18) |
and for any
. Let
be the Grundy number of
. Then
for any
such that
. Let
such that
. We prove by mathematical induction, and we assume that
for
such that
or
.
![]() |
|||
![]() |
|||
![]() |
|||
![]() |
(4.19) |
By Lemma 4.5, , and hence we finish this proof.