In Subsection 3.1, we proved that the Grundy number for
when the function
satisfies the condition
in Definition 3.2.
In this subsection, we prove that the condition in Definition 3.2 is a necessary condition for
to have the Grundy number
for the chocolate bar
. Let
be a monotonically increasing function of
into
that satisfies the following condition
.
Suppose that
is the Grundy number of the chocolate bar
. Then,
![]() |
Throughout this subsection we assume that the function satisfies the condition
of Definition 3.4, and we prove that this function
satisfies the condition
of Definition 3.2 using the following Lemma 3.9, Lemma 3.10 and Lemma 3.11.
Lemma 3.9. Let such that
,
and
. Then,
.
Proof. Since , we have
for
. Therefore,
, where
.
![]() |
|||
![]() |
(3.44) |
Since ,
. Therefore, (3.44) implies
.
Lemma 3.10. For any such that
, we have
. Let
such that
, and let
![]() |
(3.45) |
Then, Equation (3.45) implies that . By the definition of Grundy number, there exist
such that
and
.
By the definition of , we have the following Equation (3.46) or Equation (3.47).
![]() |
(3.46) |
for with
.
![]() |
(3.47) |
for with
. Equation (3.47) contradicts Equation (3.45), and hence we have Equation (3.46).
If
![]() |
(3.48) |
then . Hence,
![]() |
(3.49) |
By Equations (3.46) and (3.49), we have
![]() |
(3.50) |
Since , Equation (3.50) leads to a contradiction. Therefore, the inequality in (3.48) is false, and we have
. Hence, Equation (3.46) implies that
. The number of elements in
is the same as the number of elements in
, and hence we have
.
Lemma 3.11 Let
![]() |
for ,
,
and
.
If for
, then
. Let
![]() |
(3.51) |
for . We suppose that
![]() |
(3.52) |
and we show that this leads to a contradiction.
Case If
, then
![]() |
(3.53) |
By Equation (3.51), the inequality in (3.52) and Lemma 3.9, we have , which contradicts Equation (3.53).
Case If
, then
. Note that
, since
and
.
Therefore, by the definition of Grundy number we have
![]() |
(3.54) |
![]() |
|||
![]() |
(3.55) |
Note that .
For , we have
. Hence
(3.55) ![]() |
|||
![]() |
(3.56) |
Since
, Lemma 3.10 implies that
. Therefore, by Definition 3.4
(3.56) | ![]() |
||
![]() |
![]() |
(3.57) | ||
![]() |
(3.58) | ||
![]() |
(3.59) | ||
![]() |
(3.60) |
Then we have the following statements ,
,
and
.
All the numbers in Set (3.57) are of the type
, and hence this set does not contains
. Note that
.
The coefficients of
of the numbers in Set (3.58) are not
, and hence this set does not contains
.
All the numbers in Set (3.59) are of the type
, and hence this set does not contains
.
Note that and
.
The coefficients of
of the numbers in Set (3.60) are not
, and hence this set does not contains
.
Statements ,
,
and
contradict Relation (3.54). Therefore we conclude that the inequality in (3.52) is false.
Theorem 3.3. Suppose that the function satisfies the condition
in Definition 3.4.
Then function satisfies the condition
in Definition 3.2.
Proof. If does not satisfy the condition in Definition 3.2, then there exist
and a natural number
such that
,
![]() |
(3.61) |
and
![]() |
(3.62) |
By Equation (3.61), there exist for
such that
and
. By the inequality in (3.62), there exist
for
and a natural number
such that
,
![]() |
(3.63) |
and
![]() |
(3.64) |
Let . Then
. Hence Equations (3.63) and (3.64) imply that
![]() |
(3.65) |
and
![]() |
(3.66) |
Let
![]() |
(3.67) |
and
![]() |
(3.68) |
Then, follows directly from (3.67) and (3.68). Let
. Then,
. By (3.65),
, and hence Equation (3.67) implies
![]() |
(3.69) |
By , we have
.
Hence Equations (3.68), (3.66) and the inequality in (3.69) implies that . Therefore, there exist
and
such that
,
and
.
By Equation (3.65) and the inequality in (3.69), we have
![]() |
(3.70) |
Equation (3,67) implies
![]() |
(3.71) |
and
![]() |
(3.72) |
Inequalities (3.70), (3.71) and (3.72) contradict the result of Lemma 3.11, and hence that satisfies the condition in Definition 3.1. By Theorem 3.3, the condition
in Definition 3.1 is a necessary condition for
to have the Grundy number
.