In this subsection, we study a necessary condition for a chocolate bar to have the Grundy number .
Definition 4.2. Let be a fixed natural number and be a function that satisfies the following three conditions:
for .
is monotonically increasing.
The Grundy number of is .
We are going to show that there exists a function such that for any ,
and the Grundy number of is .
Lemma 4.6. Let be a natural number and a function such that the conditions of Definition 4.2 are satisfied. Then we have for .
Proof. First, we prove that
(4.20) |
for by mathematical induction. By the definition of Grundy number, . We suppose that for and . By the definition of Grundy number, . By the conditions of Definition 4.2, we have , and hence Equation (4.20) implies . Therefore, we have completed the proof.
Theorem 4.2. Let be a natural number and a function such that the conditions of Definition 4.2 are satisfied. We define a function by for and for . Let be the Grundy number of . Then for any such that .
Proof. Case By the definition of , we have for , and hence the function satisfies the condition of Definition 3.2 for . Therefore for any such that and .
Case Next we prove that for . We prove by mathematical induction, and we assume that for such that or . By Lemma 4.2 and Lemma 4.6, we have Relation (4.21).
(4.21) |
By Definition 4.2,
(4.22) |
and hence we have
(4.23) | |||
(4.24) |
(4.25) |
Since for , Relation (4.21) implies .
Hence, Equation (4.22), the inequality in (4.23), the inequality in (4.24), Equation (4.25) and Lemma4.3 imply .
Theorem 4.1 and Theorem 4.2 prove the following proposition and respectively.
Let be a function such that the Grundy number of the chocolate bar is . Then the Grundy number of the chocolate bar is , where satisfies the condition (4.18) and .
Let be a function such that the Grundy number of the chocolate bar is . Then the Grundy number of the chocolate bar is , where . Note that .
Therefore we have a necessary and sufficient condition for the chocolate bar to have the Grundy number .
Next an example of this condition is presented for the function . As you see, this condition is quite simple for this function.
Corollary 4.1. Let for a fixed natural number . Then
(4.26) |
if and only if the Grundy number of is , where .
Proof. By Lemma 3.1, the function satisfies the conditions of Definition 3.2. By Lemma 4.1,
if and only if there exists such that
if and only if Condition (4.26) is valid. Therefore by Theorem 4.1 we finish the proof of this corollary.
S. Nakamura and R. Miyadera, Impartial Chocolate Bar Games, Integers Volume 15, 2015.
A.C.Robin, A poisoned chocolate problem, Problem corner, The Mathematical Gazette Vol. 73, No. 466 (Dec., 1989), pp. 341-343. An Answer for the above problem is in Vol. 74, No. 468, June 1990, pp. 171-173.
D.Zeilberger, Three-Rowed CHOMP, Adv. Applied Math Vol. 26 (2001), pp. 168-179.
M. H. Albert, R. J. Nowakowski and D. Wolfe, Lessons In Play, A K Peters, p-139.
A.N.Siegel, Combinatorial Game Theory (Graduate Studies in Mathematics), American Mathematical Society (2013).