数理解析研究所講究録
第 1815 巻 2012 年 106-111

106

The Relation between Normal Play Chocolate Gamesand Misere Play Chocolate Games that SatisfyInequality$y \leq\lfloor\frac{x+z}{k}\rfloor$

宮寺良平

関西学院高等部*RYOHEI MIYADERAKWANSEI GAKUIN

1Introduction

In this article the author presents the result of a high school mathematics research project. Theauthor and his students studied chocolate games that are variants of the game of Nim.
The game of Nim is well known combinatorial game, and it is a very good topic for the research bycomputer algebra systems such as Mathematica.
By using Mathematica program and graphics ability of Mathematica the author and his students discovered interesting facts.
They studied the relation between normal play chocolate games and misere play chocolate games. In [1],, and[2}, [3] and [4] the authors studied normal play chocolate games that satisfy inequality$k\neq
1,3.$
they discovered formulae for states when $k=1,3$ , but they did not find any formula when
for arbitrary
It seems that the research on the chocolate problem that satisfies the inequality
positive number is quite difficult, but the authors discovered that the states of normal play chocolate$y \leq L\frac{x+z}{k}\rfloor$$L$$y \leq L\frac{x+z}{k}\rfloor$

$L$

$k$

games and misere play chocolate games are almost the same when $k>2.$
The authors used the computer algebra system Mathematica a lot in their research on chocolate games,
because it is easy to make a Mathematica program to calculate states of the games.
$L$

2

The chocolate problems that satisfy inequality$y \leq L\frac{x+z}{k}\rfloor$

In this article we study two types of games. Normal play chocolate games are defined by Definition
1 and misere type of chocolate games are defined by Definition 2.

Definition 1
Pieces of chocolate are of two types, sweet and very bitter. Two players in urn break the chocolate in astraight line along the grooves and $eat$ the piece broken off.
$t$imiyadera1272000@yahoo.co.jp

107
The winner is the player who leaves their opponent with the single bit $ter$ part.
In this article the graphs of the chocolate problems use the convention that light gray parts are sweet,
dark gray par are bitter.
This is a normal play chocolate game, and the player who makes the last move wins.
$ts$Definition 2
Pieces of chocolate are of two types, sweet and very bitter. The players cannot eat the very bitter part.
Two players in turn break the chocolate in a straight line along the grooves and $eat$ the piece broken off.
The player whothe last move loses, and hence this is a misere chocolate gameIn this article the graphs of the chocolate problems use the convention that light gray parts are sweet,dark gray parts are bitter.
$m\partial kes$

Definition 3
Here we define two important states of chocolates.
$(a)W$ States, from which we can force a win, as long as we play correctly at every stage.
$(b)LSta$ tes, from which we will lose however well we play, but we may end up winning if $our$ opponents
make a mistake.
In this section we deal with only the normal play games of Definition 1.
Example 1

We can study many kinds of chocolate problems.

Graph 2.1

Graph 2.2

{4,6,2}{12,6,6}

Definition 4
Suppose that a chocolate can be cut end-toend from the pper right to the lower left at most times,
horizontally at most times, and from the upper left to the lower right at most times for some non$x$

$u$

$y$

$z$

negative numbers $x,$
Then we represent this chocolate with three numbers $\{x, y, z\}$ , and we call these numbers the coordinatesof the chocolate.
$y,$ $z.$

Remark 1
In Example 1 we attached coordinates to each chocolate.
$In$ a normal play
chocolate game the player who makes the last move $(i.e., who$ moves $to \{0,0,0\})$ wins,and in misere play game the player who makes the last move $(i.e., who$ moves $to \{0,0,0\})$ loses.
The chocolate problems in Graph 2.1 and Graph 2.2 satisfy the inequalities $y\leq x+z$ andrespectively, and in this article we only study the chocolate games that satisfy inequality
forsome positive number$y \leq L\frac{x+z}{3}\rfloor$$y \leq L\frac{x+z}{k}\rfloor$

$k.$

108
Here we define the function movelk $(\{x, y, z\})$ . movelk $(\{x, y, z\})$ is the list of all the states that can bereached from the state $\{x, y, z\}$ in one step (directly).
Definition 5
We define movelk $( \{x, y, z\})=\{\{x’, {\rm Min}(y, \lfloor\frac{x’+z}{k}\rfloor), z\};x’<x\}\cup\{\{x, {\rm Min}(y, \lfloor\frac{x+z’}{k}\rfloor), z’\};z’<z\}$$\cup\{\{x, y’, z\};y’<y\}.$Example 2This is a Mathematica program to calculate states of the chocolate game for $k=3.$
The program for chocolate game is easy to $make$ once we define the function movek $()$ properly.
$L$

ss $=20$ ; al$k=3$ ;$=$

{ $a,$

Flatten[Table[ $\{a, b, c\},$$0$, Floor[1.5 ss]}, $\{b, 0,2 ss\},${c, ,Floor[1.5 ss]} , 2];
Select $[al, (1/k) (\#[[1]]+\#[[3]])>=\#[[2]] \ ]$ ;allcases
$]$

$O$

$=$

move

Block $[\{p\},$ $p=z$ ;Union Table [ $\{tl$ , Min[Floor[(l/k) (tl $+p[[3]])],$ $p[[2]]$ ],$[z_{-}]$$:=$$[$$p[[3]]\},$ $\{tl, 0, p[[1]]-1\}],$

Table $[\{p[[1]],$ $t2,$ $p[[3]]\},$ $\{t2,0,$ $p[[2]]-1\}],$
Table $[\{p[[1]]$ , Min[Floor[(l/k) (t3 $+p[[1]])],$ $p[[2]]],$$t3\},$$\{t3,0, p[[3]]-1\}]]]$ ;Mex$[L_{-}]$$:=$

Gr[pos-]$:=$ppositionxy

Min[Complement[Range[O, Length[L]], $L]$ ];Gr $[pos]=$ Mex $[Map[Gr$ , move $[pos]]]$ ;$=$Select[allcases, Gr $[\#]==$

To more easily describe the set ofintegers$L$0&];

states we utilize the nim-sum notation$x\oplus y$for any non-negative$x,$ $y.$Definition 6
Let $x,$ be non-negative integers, and write them in base 2, so$y_{i}\in\{0,1\}$ . We define the $nim$ -sumby$y$$x= \sum_{i=0}^{n}x_{i}2^{i}$and$y= \sum_{i=0}^{n}y_{i}2^{i}$with$x\oplus y$$x_{i},$$x \oplus y=\sum_{i=0}^{n}w_{i}2^{i},$$wherew_{i}=x_{i}+y_{i}$(mod 2).

(1)

Theorem 7
In the game of Graph 2.1 we have(1) The state $\{x, 0, z\}$ is a state if and only if $x=z.$(2) The state $\{x+1, y, z+1\}$ is a state if and only if $x\oplus y\oplus z=0.$
$L$

$L$

Proof For a proof see [1].

$I$

Theorem 8
In the game of Graph 2.2$\{\{x, y, z\};x, y, z\in Z_{\geq 0}, x\oplus y\oplus z=0\}$

Proof For a proof see [4].

is the set of$L$

states.
$I$

109
Conjecture 2.1
In th game that satisfies inequality

for an odd number $k\geq 3$$\{\{x, y, z\};x, y, z\in Z_{\geq 0}, x\oplus y\oplus z=0\}$ is the set ofstates.
$e$$y \leq L\frac{x+z}{k}\rfloor$$L$

By the calculation of Mathematica Conjecture 2.1 seems true, but we have only proved the case of$k=3.$The relation between the normal games and misere play games
that satisfy inequality

3$y \leq L\frac{x+z}{k}\rfloor$

Example 3Graph 3.3 and Graph 3.4 are the $3D$ graph of the set of states of the normal play game and the misereplay game with $k=2$ respectively. Although there is a difference between them, the difference is not$L$clear.

Graph 3.1

Graph 3.2

We define two transformations that are useful in studying the difference between Graph 3.3 and Graph

3.4.
Definition 9.
Under the following transformations (1) and (2) we can map the point $(a, b, c)$ to(1) The rotation of the point by { radians around the second coordinate $(or the$ vector $(0,1,0)$ ).
(2) The projection of the point to the plane made by the second and the third coordinates.
$(b, \frac{c-a}{\sqrt{2}})$

Remark 2
We discovered transformations in Definition 9 by rotating the Graph 3.3 and Graph 3.4 using Mathematica.
Example 4by
We project the sets of states of the normal play game and the misere play game with $k=2$ onto
using transformations (1) and (2), then the projected images are Graph 3.3 and Graph 3.4 respectively.
There is a clear difference between them.
$L$$R^{2}$

110

Graph 3.4

Graph 3.3

In the remainder of this section we assume that $k>2$ . Note that can be arbitrary positive number.
, and when we treat
In this section we study chocolate problems that satisfy inequality
that, then we aesume$\{x, y, z\}$ for any non-negative numbers $x,$$k$$y \leq L\frac{x+z}{k}\rfloor$$y \leq L\frac{x+z}{k}\rfloor.$$y,$ $z$

Definition 10
Let $C$ and $D$ be the sets of states and $W$ states of the game respectively. aearly $\{0,0,0\},$ $\{1,0,1\}\in C$
and $\{1, 0,0\},$ $\{0,0,1\}\in D$ . Let $C_{0}=C-\{\{0,0,0\}, \{1,0,1\}\}$ and $D_{0}=D-\{\{1,0,0\}, \{0,0,1\}\}.$$L$

Theorem 11$\{x, y, z\}\in C$ if and only if$\{x, y, z\}\in D$

movelk $(\{x, y, z\})\subset D$ .

(2)

movelk $(\{x, y, z\})\cap C\neq\emptyset$ .

(3)

if and only if

Proofthat leads to a$Fh^{r}om$$L$state any move leads to a $W$ state, and from a $W$ state there always exists a movestate. Therefore this is direct from the definition of $C$ and $D.$a$L$$I$

Lemma 12
Let $k>2$ . If $x,$ $z\geq 1$ , then $\{0, y, z\},$ $\{x, y, 0\}\in D$ . If $x,$ $z\geq 2$ , then $\{x, y, 1\},$ $\{1,y, z\}\in D.$

Proof By Definition 5 it is clear that $\{0,0,0\}\in move1k(\{0, y, z\})$ . Since $\{0,0,0\}\in C$ , by Theorem
11 $\{0, y, z\}\in D$ . Similarly $\{x, y, O\}\in D.$
Since $k>2$ , by Definition 5 it is clear that $\{1, 0,1\}\in move1k(\{1, y, z\})$ . Since $\{1, 0,1\}\in C$ , by Theorem
1
11 $\{1, y, z\}\in D$ . Similarly $\{x, y, 1\}\in D$ .
Lemma 13
If $\{u, v, w\}\in C_{0}$ , then $u,$ $w\geq 2.$
Proof If $u\leq 1$ or $w\leq 1$ , then $\{u, v, w\}\in\{\{0, y, z\};z\geq 1\}\cup\{\{x, y, 0\};x\geq 1\}\cup\{\{x, y, 1\};x\geq 2\}$$\cup\{\{1, y, z\};z\geq 2\}U\{\{O, O, O\}, \{1,0,1\}\}.$

Therefore by the fact that$D\cap C_{0}=\emptyset,$$\{0,0,0\},$ $\{1,0,1\}\not\in C_{0}$, and Lemma 12 we get this lemma.

1Lemma 14
Let $\{x, y, z\}\in D_{0}$ . If $\{0,0,0\}$ or $\{1, 0,1\}\in$ movelk $(\{x, y, z\})$ , then we have $\{1, 0,0\}$ or $\{0,0,1\}\in$movelk $(\{x, y, z\})$ .

111
Proof If $\{0,0,0\}\in mme1k(\{x, y, z\})$ , then we have $\{x, y, z\}=\{0, y, z\}$ or $\{x, y, 0\}.$Since $\{1, 0,0\},$ $\{0,0,1\}\not\in D_{0},$ $\{x, y, z\}=\{0, y, z\}$ with $z\geq 2$ or $\{x, y, 0\}$ with $x\geq 2$ . Then $\{0,0,1\}$ or$\{1, 0,0\}\in move1k(\{x, y, z\})$ .
If $\{1, 0,1\}\in move1k(\{x, y, z\})$ , then $\{x, y, z\}=\{1, y, z\}$ with $z\geq 2$ or $\{x, y, 1\}$ with $x\geq 2$ . Clearly wehave $\{1, 0,0\}$ or $\{0,0,1\}\in move1k(\{x, y, z\})$ .
Let $CM=C_{0}\cup\{\{1,0,0\}, \{0,0,1\}\}$ and $DM=D_{0}\cup\{\{0,0,0\}, \{1,0,1\}\}.$$I$

Theorem 15$CM$ and $DM$ are the sets of$L$states and $W$ states of misere play chocolate game of Definition 2.

Proof [1] Let $\{x, y, z\}\in CM$ and $\{p, q, r\}\in move1k(\{x, y, z\})$ .
[1.1] If $\{x, y, z\}\in C_{0}$ , by Definition 10 and Theorem 11 we have $\{p, q, r\}\in D$ . Since $\{x, y, z\}\in C_{0}$ , byLemma 13 $z\geq 2$ . Therefore $\{p, q, r\}\neq\{1,0,0\},$ $\{0,0,1\}$ and $\{p, q, r\}\in D_{0}\subset DM.$
[1.2] If $\{x, y, z\}=\{1,0,0\}$ or $\{0,0,1\}$ , then $\{p, q, r\}=\{0,0,0\}\in DM$ . We proved that$x,$

movelk $(\{x, y, z\})\subset DM$.

(4)[2] Let $\{x, y, z\}\in DM.$
[2.1] If $\{x, y, z\}\in D_{0}$ , by Definition 10 and Theorem 11 there exists $\{p, q, r\}\in move1k(\{x, y, z\})\cap C.$[2.1.1] If $\{p, q, r\}=\{0,0,0\}$ or $\{1, 0,1\}$ . Then by Lemma 14 $\{1, 0,0\}$ or $\{0,0,1\}\in move1k(\{x, y, z\})\cap CM.$[2.1.2] If $\{p, q, r\}\neq\{0,0,0\}$ or $\{1, 0,1\}$ , then $\{p, q, r\}\in move1k(\{x, y, z\})\cap C_{0}\subset move1k(\{x, y, z\})\cap CM.$[2.2] If $\{x, y, z\}=\{0,0,0\}$ , then the player does not have to move. This state $\{x, y, z\}$ is $W$-state.
[2.3] If $\{x, y, z\}=\{1,0,1\}$ , then $\{1, 0,0\}$ and $\{0,0,1\}\in move1k(\{x, y, z\})\cap CM.$
We proved thatmovelk $(\{x, y, z\})\cap CM\neq\emptyset$.
(5)

By (4) and (5) we finish the proof of this theorem.

$I$

Remark 3
I would like to thank Taishi Inoue, Wataru Ogasa, Koichiro Nishimura, Yuki Tomari, Takuma Nakaoka,Takuya Kakuda Akihiro Kanno, $Ren$ Kimura and $Ryo$ Hanahusa for their contribution to the researchpresented in this article.

References[1] Yamauchi, T., Inoue T., Tomari, Y.: Variants of the Game of Nim that have Inequalities as Conditions, Rose-Hulman Institute of Technology, Undergraduate Math Journal, Vol.10. Issue 2, (2009).

[2] Miyadera, R., Naito, M.: Combinatorial Games and Beautiful Graph produced by them, Visual
Mathematics Art and Science Electric Journal of ISIS-Symmetry, Volume 11, No. 3, (2009).
[3] Naito, M., Inoue, T., Miyadera, R., etc., Discrete Mathematics and Computer Algebra System, The
Joint Conference of ASCM 2009 and MACIS 2009, COE Lecture Note Vol.22:Kyushu University.

[4] Inoue T. and Miyadera, R, Variants of Nim and the Sierpinski Sieves Produced by them, to appear.