IMPARTIAL AND PARTIZAN RESTRICTED CHOCOLATE BAR GAMES
Ryohei Miyadera
Keimei Gakuin Junior and High School, Kobe City, Japan
<EMAIL_ADDRESS>Shoei Takahashi
Keimei Gakuin Junior and High School, Kobe City, Japan
<EMAIL_ADDRESS>Aoi Murakami
Keimei Gakuin Junior and High School, Kobe City, Japan
<EMAIL_ADDRESS>Akito Tsujii
Keimei Gakuin Junior and High School, Kobe City, Japan
<EMAIL_ADDRESS>Hikaru Manabe
Keimei Gakuin Junior and High School, Kobe City, Japan
<EMAIL_ADDRESS>

Received: , Revised: , Accepted: , Published:

Abstract

In this paper, we consider impartial and partizan restricted chocolate bar
games. In impartial restricted chocolate bar games, players cut a chocolate
bar into two pieces along any horizontal or vertical line and eat whichever
piece is smaller. If the two pieces are the same size, a player can eat either
one.

In constrast, partizan restricted chocolate bar games include players
designated as Left and Right and chocolate bars with black and white stripes.
Left cuts the chocolate bar in two as above and eats the part with fewer black
blocks. Similarly, Right cuts the bar and eats the part with fewer white
blocks. A player loses when they cannot eat the remaining chocolate bar. We
provide formulas that describe the winning positions of the previous player,
Right, and Left players. We also present an interesting similarity in the
graphs of previous players’ winning positions for impartial and partizan
chocolate bar games.

##  1 Introduction

The classic game of Nim is played with stones arranged in discrete heaps or
piles. A player can remove any number of stones from any one pile during their
turn, and the player who takes the last stone is considered the winner.

Given its simplicity and importance in combinatorial game theory, many variant
forms of Nim have been devised.

In Section 2, we discuss a version of Maximum Nim with an upper bound $f(n)$
on the number of stones that can be removed in terms of the number of stones
$n$ in a given pile (see [3]). In this study, we consider the case in which
$f(n)=\left\lfloor\frac{n}{2}\right\rfloor$.

In Section 3, we explore variants of the game Chomp [2]. Robin presented the
first two-dimensional chocolate bar which used a rectangular array of squares
with a single black square representing a bitter piece [9]. The two players
take turns breaking the bar into two pieces along a straight line representing
the grooves in a chocolate bar and eat the piece without the bitter part. The
player that leaves their opponent with the single “bitter” or black block
wins. This is combinatorially equivalent to game of Nim with two heaps; for
example, the chocolate bar game shown in Figure 1 is eqivalent to the
classical Nim game with two piles shown in Figure 2. We have investigated many
variants of such chocolate bar games in prior works [6], [7], including some
with two-dimensional chocolate bars with irregular shapes (Figure 3). We have
also provided some for three-dimensional chocolate bars. See [4].

Figure 1: Original chocolate bar
with a bitter part Figure 2: Traditional
Nim with two piles Figure 3: Chocolate bar
with a bitter part,
where some squares
are removed

In the present work, we consider a rectangular chocolate bar game with
restrictions on the size of the piece to be eaten without a bitter part
(Figure 4).

Although we have described some characteristics of impartial restricted
chocolate bar games in a prior work, we present a simplified version of the
theory here [5].

These results on impartial restricted chocolate bar games are relevant to our
investigation of partizan restricted chocolate bar games owing to some
interesting similarities and differences of note.

Figure 4: Chocolate bar without any bitter part

Given this restriction, we consider a chocolate bar game equivalent to the sum
of two Maximum Nim. Hence, results that have been established for Maximum Nim
can be applied to this chocolate bar game.

In Section 4, we explore some characteristics of partizan restricted chocolate
bar games as a natural generalization of impartial restricted games.

These involve two players designated as Left and Right, with chocolate bars
with black and white stripes. Left cuts the bar into two pieces and eats that
with fewer black blocks. Similarly, Right cuts the bar and eats the piece with
fewer white blocks. A player loses when they cannot eat the remaining piece.
We provide formulas that describe the previous, Right, and Left players’
winning positions. In particular, we discuss an interesting similarity in the
graphs of previous players’ winning positions for impartial and partizan
chocolate bar games.

We briefly review some necessary concepts in combinatorial game theory (see
[1] for more details). We denote the sets of non-negative integers and natural
numbers as $\mathbb{Z}_{\geq 0}$ and $\mathbb{N}$, respectively. Here, we
consider impartial games with no draws, which admit of only two outcome
classes.

$(a)$ A position is called a $\mathcal{P}$-position if it is a winning
position for the previous player (the player who just moved), as long as
he/she plays correctly at every stage.
$(b)$ A position is called an $\mathcal{N}$-position if it is a winning
position for the next player, as long as he/she plays correctly at every
stage.

In combinatorial game theory, the Nim-sum indicates addition without
carryovers for numbers expressed in base $2$, which is identical to the
logical operation of exclusive or.

Let $x$, $y$ $\in Z_{\geq 0}$. We represent $x=\sum_{i=0}^{n}x_{i}2^{i}$ and
$y=\sum_{i=0}^{n}y_{i}2^{i}$ with $x_{i},y_{i}\in\\{0,1\\}$. We define the
Nim-sum $x\oplus y$ as $x\oplus y=\sum\limits_{i=0}^{n}{{w_{i}}}{2^{i}},\text{
where }w_{i}=x_{i}+y_{i}\ (\mathrm{mod}\ 2).$

The Grundy number is another important tool in combinatorial game theory. To
express this for the game considered here, we need to define the “move” that
the players make on successive turns.
$(i)$ For any position $\mathbf{p}$ of a game $\mathbf{G}$, there exists a set
of positions that can be reached by making precisely one move in $\mathbf{G}$,
which is denoted by move$(\mathbf{p})$.
$(ii)$ The minimum excluded value (mex) of a set $S$ of non-negative integers
is the least non-negative integer, not in S.
$(iii)$ Let $\mathbf{p}$ be the current position in an impartial game. The
associated Grundy number is denoted by $\mathcal{G}(\mathbf{p})$ and is
recursively defined by
$\mathcal{G}(\mathbf{p})=\textit{mex}\\{\mathcal{G}(\mathbf{h}):\mathbf{h}\in
move(\mathbf{p})\\}.$

The Grundy number of a position is important for two reasons. It is related to
the $\mathcal{P}$-position presented in Theorem 1, and can also applied to the
sum of multiple games.

######  Theorem 1.

Let $\mathcal{G}$ represent the Grundy number of the combinatorial game
$\mathbf{G}$. Then, for any position $\mathbf{p}$ of $\mathbf{G}$, we have
$\mathcal{G}(\mathbf{p})=0$ if and only if $\mathbf{p}$ represents a
$\mathcal{P}$-position.

For the proof, please see [1].

The sum of two games is an important concept in combinatorial game theory.

If $\mathbf{G_{1}}$ and $\mathbf{G_{2}}$ are combinatorial games, their sum,
denoted by $\mathbf{G_{1}}+\mathbf{G_{2}}$, represents a game in which each
player alternately chooses one among $\mathbf{G_{1}}$ and $\mathbf{G_{2}}$,
and plays a move in the selected game; the player who cannot play loses the
game. This scenario occurs only when $\mathbf{G_{1}}$ and $\mathbf{G_{2}}$
have reached a terminal position.

There is a simple relation for the Grundy number of the sum of two games.

Let $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ represent the Grundy numbers of
$\mathbf{G_{1}}$ and $\mathbf{G_{2}}$. Then, the Grundy number of a position
$\\{\mathbf{g},\mathbf{h}\\}$ in the game $\mathbf{G_{1}}+\mathbf{G_{2}}$ is
$\mathcal{G}_{1}(\mathbf{g})\oplus\mathcal{G}_{1}(\mathbf{h})$.

Given this background, the authors present new results from this point
forward.

##  2 Maximum Nim

We consider maximum Nim as follows.

Suppose there is a pile of $n$ stones, and two players take turns removing
stones from the pile. At each turn, the player is allowed to remove at least
one and at most $f(m)$ stones if the number of remaining stones is $m$. The
player who removes the last stone or stones is the winner. Here, $f(m)$
represents a function whose values are non-negative integers for $m\in Z_{\geq
0}$ such that $0\leq f(m)-f(m-1)\leq 1$ for any natural number $m$. We refer
to $f$ as the rule function.

######  Lemma 1.

Let $\mathcal{G}$ represent the Grundy number of the maximum Nim with the rule
function $f(x)$. Then, we have the following properties:
$(i)$ If $f(x)=f(x-1)$, $\mathcal{G}(x)=\mathcal{G}(x-f(x)-1)$.
$(ii)$ If $f(x)>f(x-1)$, $\mathcal{G}(x)=f(x)$.

This is Lemma 2.1 of [3].

In this paper, we assume that $f(m)=\left\lfloor\frac{m}{2}\right\rfloor$,
where $\left\lfloor x\right\rfloor$ represent the greatest integer less than
or equal to $x$ for $x\in\mathbb{Z}_{\geq 0}$.

For the maximum Nim of $x$ stones with rule function
$f(x)=\left\lfloor\frac{x}{2}\right\rfloor$,
$\textit{move}(x)$ $=\\{x-u:1\leq
u\leq\left\lfloor\frac{x}{2}\right\rfloor\text{ and }u\in\mathbb{N}\\}$.

######  Lemma 2.

Let $\mathcal{G}$ represent the Grundy number of the maximum Nim with the rule
function $f(m)=\left\lfloor\frac{m}{2}\right\rfloor$. Then, we have the
following properties:
$(i)$ For an even number $x$ such that $x=2m$ for $m\in\mathbb{Z}_{\geq 0}$,
we have

$\mathcal{G}(x)=m.$

$(ii)$ For an odd number $x$ such that $x=2^{k}(2m+1)-1$ for $k\in\mathbb{N}$
and $m\in\mathbb{Z}_{\geq 0}$, we have

$\mathcal{G}(x)=m.$

###### Proof.

$\mathrm{(i)}$ If $x=2m$ for $m\in\mathbb{Z}_{\geq 0}$, $f(x)>f(x-1)$.
Therefore, by $(ii)$ of Lemma 1,

$\mathcal{G}(2m)=f(2m)=\left\lfloor\frac{2m}{2}\right\rfloor=m.$ (1)

$\mathrm{(ii)}$ By $(\ref{evencase})$ and $(i)$ of Lemma 1, we have for
$k\in\mathbb{N}$ and $m\in\mathbb{Z}_{\geq 0}$

$\displaystyle\mathcal{G}(x)$ $\displaystyle=\mathcal{G}(2^{k}(2m+1)-1)$
$\displaystyle=\mathcal{G}(2^{k}(2m+1)-1-\left\lfloor\frac{2^{k}(2m+1)-1}{2}\right\rfloor-1)$
$\displaystyle=\mathcal{G}(2^{k}(2m+1)-1-(2^{k-1}(2m+1)-1))-1)$
$\displaystyle=\mathcal{G}(2^{k-1}(2m+1)-1)$ $\displaystyle\hskip
28.45274pt\vdots$ $\displaystyle=\mathcal{G}((2m+1)-1)=\mathcal{G}(2m)=m.$

∎

######  Lemma 3.

For any number $n\in\mathbb{Z}_{\geq 0}$

$\\{x:\mathcal{G}(x)=n\\}=\\{2^{k}(2n+1)-1:k\in\mathbb{Z}_{\geq 0}\\}.$ (2)

###### Proof.

Let $n\in\mathbb{Z}_{\geq 0}$. If $k=0$, $2^{k}(2n+1)-1=2n$. Then, by $(i)$ of
Lemma 2 we have $\mathcal{G}(2n)=n$. If $k\geq 1$, by $(ii)$ of Lemma 2,
$\mathcal{G}(2^{k}(2n+1)-1)=n$. Therefore,

$\\{x:\mathcal{G}(x)=n\\}\supset\\{2^{k}(2n+1)-1:k\in\mathbb{Z}_{\geq 0}\\}.$
(3)

Suppose that $\mathcal{G}(x)=n$ for $n\in\mathbb{N}$. By Lemma 2, we have
$x=2n$ or $x=2^{k}(2n+1)-1$ for some $k\in\mathbb{N}$. Therefore we have

$\\{x:\mathcal{G}(x)=n\\}\subset\\{2^{k}(2n+1)-1:k\in\mathbb{Z}_{\geq 0}\\}.$
(4)

By (3) and (4) we have (2). ∎

##  3 Chocolate bar games with restrictions on the size of chocolate bar to be
eaten

We define chocolate bar games with restrictions.

######  Definition 3.1.

$(i)$ A chocolate bar is a rectangular array of squares.
$(ii)$ We describe the position of this chocolate bar as $(x,y)$ when $x$ and
$y$ represent the height and the width of the chocolate. Then, the size of the
chocolate bar is calculated by $xy$.
$(iii)$ Two players take turns and break the chocolate bar along any one of
the horizontal or vertical lines into two pieces and eat the smaller one of
the pieces, where players can eat either piece if the pieces are of equal
size.
$(iv)$ The player who is left with a $1\times 1$ piece of chocolate and hence
cannot make another move loses the game. Therefore the $1\times 1$ piece of
chocolate with the coordinates $(1,1)$ is the terminal position of the game.

For an example of the position of a chocolate bar, see Figure 6.

######  Remark 2.

Note that cutting chocolate bar horizontally is the same as reducing the first
coordinate, and cutting chocolate bar vertically is the same as reducing the
second coordinate.

######  Theorem 3.

Let $\mathcal{G}(x,y)$ be the Grundy number of the chocolate bar game $(x,y)$,
$\mathcal{G}(x)$ and $\mathcal{G}(y)$ be the Grundy number of the Max Nim of
$x$-stones and $y$-stones with the rule sequence
$f(n)=\left\lfloor\frac{n}{2}\right\rfloor$. If we define
$G_{n}=\\{2^{k}(2n+1)-1:k\in\mathbb{Z}_{\geq 0}\\}$ for $n\in\mathbb{Z}_{\geq
0}$, then we have for $n\in\mathbb{Z}_{\geq 0}$,

$\\{(x,y):\mathcal{G}(x,y)=n\\}=\cup\\{G_{s}\cap G_{t}:s,t\in\mathbb{Z}_{\geq
0}\text{ such that }s\oplus t=n\\}.$ (5)

###### Proof.

Since the chocolate bar game is the sum of two Max Nim with a rule sequence
$f(n)=\left\lfloor\frac{n}{2}\right\rfloor$, we have
$\mathcal{G}(x,y)=\mathcal{G}(x)\oplus\mathcal{G}(y)$. Therefore, by Lemma 3,
we have $(\ref{g1g2sum})$. ∎

######  Definition 3.2.

Let

$\displaystyle\mathcal{P}=$
$\displaystyle\\{(x,y):y=2^{k}x+2^{k}-1,x\in\mathbb{N}\text{ and
}k\in\mathbb{Z}_{\geq 0}\\}$
$\displaystyle\cup\\{(x,y):x=2^{k}y+2^{k}-1,y\in\mathbb{N}\text{ and
}k\in\mathbb{Z}_{\geq 0}\\}.$

######  Theorem 4.

The set $\mathcal{P}$ in Definition 3.2 is the set of $\mathcal{P}$-positions
of the chocolate bar game of Definition 3.1.

###### Proof.

Since the chocolate bar game is the sum of two Max Nim, $(x,y)\in\mathcal{P}$
if and only if

$\mathcal{G}(x)=\mathcal{G}(y)=n$ (6)

for some $n\in\mathbb{Z}_{\geq 0}$. By Lemma 2, we have (6) if and only if

$(x+1,y+1)=(2^{s}(2n+1),2^{t}(2n+1))$ (7)

for $s,t,n\in\mathbb{Z}_{\geq 0}$. Equation (7) is equivalent to

$y+1=2^{s-t}(x+1)$

for $s,t\in\mathbb{Z}_{\geq 0}$ such that $s\geq t$ or

$x+1=2^{t-s}(y+1)$

for $s,t\in\mathbb{Z}_{\geq 0}$ such that $t\geq s$. Since we need to consider
only the chocolate bar whose height and width are natural numbers, and we
assume that $x,y\in\mathbb{N}$. Therefore, the set $\mathcal{P}$ in Definition
3.2 is the set of $\mathcal{P}$-positions of the chocolate bar game of
Definition 3.1. ∎

The chocolate bar game in this section was presented at the 17th International
Olympiad in Informatics [8], where the set of $\mathcal{P}$-positions was
presented with proof. Still, Grundy numbers of the chocolate bar games were
not mentioned. In [10], the set of $\mathcal{P}$-positions was presented with
a proof that is different from the one used in [8].

Each point in the graph in Figure 6 with position $(x,y)$ (the bottom left is
$(1,1)$) represents a $x\times y$ rectangular chocolate that is a
$\mathcal{P}$-position. The $\mathcal{P}$-positions in this graph of the
chocolate bar game appear to be arranged in lines. For example, the central
diagonal has a slope of 1; the following line down has a slope of
$\frac{1}{2}$; the next, $\frac{1}{4}$; and so on.

Figure 5: (5,4)

Figure 6: P-positions

##  4 Partizan chocolate bar game with a restriction on the size of chocolate
bar to be eaten

There are two different classifications of a game in combinatorial games:
impartial and partizan. An impartial game is one where the same moves exist
for both players and games in sections 2 and 3 are impartial.

In this section, we study partizan chocolate games, where players control
their own moves.

Let the name of two players be Left (using she as a pronoun) and Right (using
he as a pronoun). Here we use chocolate bars with black and white stripes. See
Figures 7, 8, 9, and 10 for examples. The use of this black and white
chocolate bar was suggested by Prof. R. J. Nowakowski when one of the authors
discussed a partizan version of chocolate bar games at Combinatorial Game
Theory Colloquium IV.

Left cuts the chocolate bar into two parts, and she eats the part with fewer
black blocks. When the number of black blocks is the same for both parts, she
can eat either. When there is only a one-by-one white chocolate bar that is
$(1,1,0)$ in figures 11 and 16, she can eat it.

Similarly, Right cuts the chocolate bar into two and eats the part with fewer
white blocks. If the number of white blocks is the same, he can eat either.
When there is only a one-by-one black chocolate bar that is $(1,1,1)$ in
figures 11 and 16, he can eat it.

A player loses in the game when she or he cannot eat the remaining chocolate
bar.

Figure 7:
(5,4,1) Figure 8:
(5,4,0) Figure 9:
(1,5,1)
and(2,5,1) Figure 10:
(5,2,0)
and(5,1,0) Figure 11: (1,1,1)
and(1,1,0)

In the following, we describe a bar of black and white chocolate bar with a
matrix of numbers, where $1$ is for a black block and $0$ is for a white
block.

Black and white chocolate bars in figures 7, 8, 9, and 10 are represented by
matrices in figures 12, 13, 14, and 15.

Figure 12:
(5,4,1) Figure 13:
(5,4,0) Figure 14:
(1,5,1)
and (2,5,1) Figure 15:
(5,2,0)
and (5,1,0) Figure 16: (1,1,1)
and(1,1,0)

We denote a chocolate bar by $(x,y,s)$, where $x$ and $y$ are the height and
the width of the chocolate bar, respectively, and $s$ is the first number of
the first row.

Please compare the chocolate bar in Figure 7 and the chocolate bar in Figure
8. These are represented as matrices in 12 and 13. Note that the difference
between $(5,4,1)$ and $(5,4,0)$ is the value of the third coordinate, the
first number of the first row of each matrix.

According to the rule of the game, there are three ways that the game ends. A
player loses the game when there is no chocolate bar left. Player L loses when
there is only $(1,1,1)$, and Player R loses when there is only $(1,1,0).$

Beside $\mathcal{P}$-position and $\mathcal{N}$-position in Section 2, we need
the following two outcome classes in Section 4.

######  Definition 4.1.

$(a)$ A position is referred to as a $\mathcal{L}$-position if it is a winning
position for L.
$(b)$ A position is referred to as an $\mathcal{R}$-position if it is a
winning position for R.

######  Theorem 5.

Every position of a game belongs to exactly one of four outcome classes
$\mathcal{P}$-position, $\mathcal{N}$-position, $\mathcal{L}$-position, and
$\mathcal{R}$-position.

###### Proof.

This fact is presented on page 36 of [1]. ∎

######  Lemma 4.

$(i)$ A position is a $\mathcal{P}$-position if and only if $R$ always move to
a $\mathcal{L}$ or $\mathcal{N}$-position and $L$ always moves to a
$\mathcal{R}$ or $\mathcal{N}$-position.
$(ii)$ A position is a $\mathcal{N}$-position if and only if $R$ can move to a
$R$ or $\mathcal{P}$-position and $L$ can move to a $\mathcal{L}$ or
$\mathcal{P}$-position.
$(iii)$ A position is a $\mathcal{L}$-position if and only if $R$ always move
to a $\mathcal{L}$ or $\mathcal{N}$-position and $L$ can move to a
$\mathcal{L}$ or $\mathcal{P}$-position.
$(iv)$ A position is a $\mathcal{R}$-position if and only if $R$ can move to a
$R$ or $\mathcal{P}$-position and $L$ always moves to a $\mathcal{R}$ or
$\mathcal{N}$-position.

###### Proof.

This fact is presented as Observation 2.4 on page 37 of [1].

∎

The result of Lemma 4 is presented as Table 1. By this, we can decide the
outcome class of each position.

Table 1: How to decide the outcome class of a game |  $R$ can move to a |  $R$ always moves to
---|---|---
|  $\mathcal{R}$ or $\mathcal{P}$-position | a $\mathcal{L}$ or $\mathcal{N}$-position
$L$ can move to a |  |
$\mathcal{L}$ or $\mathcal{P}$-position |  $\mathcal{N}$-position |  $\mathcal{L}$-position
$L$ always moves to |  |
a $\mathcal{R}$ or $\mathcal{N}$-position |  $\mathcal{R}$-position |  $\mathcal{P}$-position

######  Lemma 5.

Let

$\mathbb{N}_{1}=\\{2^{s}(2p+5)-1:s,p\in\mathbb{Z}_{\geq 0}\\},$
$\mathbb{N}_{2}=\\{2^{s}4-1:s\in\mathbb{Z}_{\geq 0}\\},$

and

$\mathbb{N}_{3}=\\{2^{s}3-1:s\in\mathbb{Z}_{\geq 0}\\}.$

Then the set of natural numbers

$\mathbb{N}=\\{1\\}\cup\mathbb{N}_{1}\cup\mathbb{N}_{2}\cup\mathbb{N}_{3}.$

###### Proof.

Let $n$ be a natural number such that

$n\geq 2.$ (8)

For $n$, there exist $m\in\mathbb{Z}_{\geq 0}$ and $k\in\mathbb{N}$ such that
$n+1=2^{m}k$ and $k$ is odd. If $k=1$, then by (8), we have $2^{m}=n+1\geq 3$.
Therefore, we have $m\geq 2$, and $n=2^{m-2}4-1\in\mathbb{N}_{2}$. If $k=3$,
$n=2^{m}3-1\in\mathbb{N}_{3}$. If $k$ is an odd number such that $k\geq 5$,
then $n=2^{m}(2p+5)-1\in\mathbb{N}_{1}$ for some $p\in\mathbb{Z}_{\geq 0}$. ∎

Figure 17: To divide chocolate bars

######  Lemma 6.

Suppose that we cut a chocolate bar $(a+b,m,p)$ into two pieces $A=(a,m,s)$
and $B=(b,m,t)$, where $a,b,m\in\mathbb{N},$ $m\geq 2$, $a>b\geq 1$ and
$s,t=0$ or $1$. Then, the number of $0$ and the number of $1$ in $A$ are
larger than those of $B$, respectively.

###### Proof.

We divide $A$ into $A_{1}=(a-b-1,m,p)$, $A_{2}=(b,m,r)$ and $A_{3}=(1,m,s)$,
where $r,s=0,1$. See Figure 17. If $a=b+1$, then
$A_{1}=(a-b-1,m,p)=(0,m,p)=\emptyset$. Since $B$ and $A_{2}$ are horizontally
symmetrical as matrices of $0$ and $1$, the numbers of $0$ and $1$ are the
same for both. Since $m\geq 2,$ $A_{3}$ contains some $0$ and $1$, the number
of $0$ and the number of $1$ in $A=A_{1}\cup A_{2}\cup A_{3}$ are larger than
those of $A_{2}$. ∎

######  Remark 6.

Suppose you have a chocolate bar $(x,y,s)$ with $x,y\geq 2$ and $s=0,1$. When
you cut this chocolate bar into two pieces, then by Lemma 6, you can eat the
smaller one and cannot eat the bigger one. If two pieces are the same size,
you have to count the $0$ and $1$ in these pieces to decide which to eat. As
for the chocolate bars $(n,1,s)$ or $(1,n,s)$ with

######  Lemma 7.

Let $n\in\mathbb{Z}_{\geq 0}$. Then, we have the following:
$(i)$ If $L$ cuts $(4n+1,1,0)$ chocolate bar , she gets chocolate bars
$(2n,1,0),\cdots,(4n,1,0)$.
$(ii)$ If $R$ cuts $(4n+1,1,0)$ chocolate bar , he gets chocolate bars
$(2n+1,1,0),\cdots,(4n,1,0)$.
$(iii)$ If $R$ cuts $(4n+3,1,0)$ chocolate bar , he gets chocolate bars
$(2n+1,1,0),\cdots,(4n+2,1,0)$.

###### Proof.

$\mathrm{(i)}$ Let $A=(4n+1,1,0)$, $A_{1}=(2n,1,0)$, and $A_{2}=(2n+1,1,0)$.
Then $A=A_{1}\cup A_{2}$ and the number of $1$ in $A_{1}$ is the same as the
number of $1$ in $A_{2}$, and hence you can eat $A_{2}$ to get $A_{1}$. It is
clear that $A_{1}$ is the smallest chocolate bar you can get from $A$.
$\mathrm{(ii)}$ Let $A=(4n+1,1,0)$, $A_{1}=(2n+1,1,0)$, $A_{2}=(2n,1,0)$ ,
$A^{\prime}_{1}=(2n,1,0)$, $A^{\prime}_{2}=(2n+1,1,0)$. Then we have
$A=A_{1}\cup A_{2}$ and $A=A^{\prime}_{1}\cup A^{\prime}_{2}$. The number of
$0$ in $A_{1}$ is $n+1$, the number of $0$ in $A_{2}$ is $n$, the number of
$0$ in $A^{\prime}_{1}$ is $n$, the number of $0$ in $A^{\prime}_{2}$ is
$n+1$, and hence $R$ can eat $A_{2}$ to get $A_{1}$, but $R$ cannot eat
$A^{\prime}_{2}$ to get $A^{\prime}_{1}$. It is clear that $A_{1}$ is the
smallest chocolate bar $R$ can get from $A$.
$\mathrm{(iii)}$ Let $A=(4n+3,1,0)$, $A_{1}=(2n+1,1,0)$, and
$A_{2}=(2n+2,1,0)$. Then $A=A_{1}\cup A_{2}$, and the number of $0$ in $A_{1}$
is $n+1$, and the number of $0$ in $A_{2}$ is $n+1$. Therefore, $R$ can eat
$A_{2}$ to get $A_{1}$. Clearly, $A_{1}$ is the smallest chocolate bar $R$ can
get from $A$. ∎

######  Definition 4.2.

Let $\mathcal{P}_{a}=\\{(2^{n}(2p+5)-1,2^{m}(2p+5)-1,s):n,m\in\mathbb{Z}_{\geq
0},p\in\mathbb{Z}_{\geq 0}\text{ and }s=0,1\\}$,
$\mathcal{P}_{b}=\\{(2^{n}3-1,2^{m}4-1,s):n,m\in\mathbb{Z}_{\geq 0}\text{ and
}s=0,1\\}$ and
$\mathcal{P}_{c}=\\{(2^{n}4-1,2^{m}3-1,s):n,m\in\mathbb{Z}_{\geq 0}\text{ and
}s=0,1\\}$. Let
$\mathcal{P}=\mathcal{P}_{a}\cup\mathcal{P}_{b}\cup\mathcal{P}_{c}\cup\\{(1,2,s),(2,1,s):s=0,1\\}\cup\\{(0,0)\\}$.

######  Definition 4.3.

Let $\mathcal{L}_{1}=\\{(2n+5,1,0):n\in\mathbb{Z}_{\geq 0}\\}$,
$\mathcal{L}_{2}=\\{(1,2n+5,0):n\in\mathbb{Z}_{\geq 0}\\}$ and
$\mathcal{L}=\mathcal{L}_{1}\cup\mathcal{L}_{2}\cup\\{(1,1,0)\\}$.

######  Definition 4.4.

Let $\mathcal{R}_{1}=\\{(2n+5,1,1):n\in\mathbb{Z}_{\geq 0}\\}$,
$\mathcal{R}_{2}=\\{(1,2n+5,1):n\in\mathbb{Z}_{\geq 0}\\}$ and
$\mathcal{R}=\mathcal{R}_{1}\cup\mathcal{R}_{2}\cup\\{(1,1,1)\\}$.

######  Definition 4.5.

Let $\mathcal{N}=\\{(x,y,s):x,y\in\mathbb{N},s=0,1\text{ and
}(x,y,s)\notin\mathcal{P}\cup\mathcal{L}\cup\mathcal{R}\\}.$

######  Lemma 8.

We have the following $(i)$, $(ii)$, $(iii)$, and $(iv)$ for the set
$\mathcal{N}$:
$(i)$ We have $(3,1,p),(1,3,p)\in\mathcal{N}$ for $p=0,1$.
$(ii)$ We have $(2n,1,p),(1,2n,p)\in\mathcal{N}$ for $n\in\mathcal{N}$ such
that $n\geq 2$ and $p=0,1$.

###### Proof.

By Definitions 4.2, 4.3, 4.4, and 4.5 if $(n,1,s)\in\mathcal{L}$ or
$\mathcal{R}$, $n=1$ or $n\geq 5$ and $n$ is odd. If $(n,1,s)\in\mathcal{P}$,
$n=2$. Therefore, we have $(i)$ and $(ii)$. ∎

######  Lemma 9.

We have the following $(i)$, $(ii)$, $(iii)$, and $(iv)$:
$(i)$ If $L$ starts with a position in $\mathcal{L}$, then she wins or can
move to a position in $\mathcal{L}\cup\mathcal{P}$.
$(ii)$ If $R$ starts with a position in $\mathcal{R}$, then he wins or can
move to a position in $\mathcal{R}\cup\mathcal{P}$.
$(iii)$ If $R$ starts with a position in $\mathcal{L}$, then he loses or
always move to a position in $\mathcal{L}\cup\mathcal{N}$.
$(iv)$ If $L$ starts with a position in $\mathcal{R}$, then he loses or always
move to a position in $\mathcal{R}\cup\mathcal{N}$.

###### Proof.

$\mathrm{(i)}$ If $L$ starts with a position $(2n+5,1,0)$ with
$n\in\mathbb{N}$, then she can move to the position
$(2(n-1)+5,1,0)\in\mathcal{L}$. If she starts with $(5,1,0)$, then by $(i)$ of
Lemma 7 she can move to the position $(2,1,0)\in\mathcal{P}$. If she starts
with $(1,1,0)$, then she wins by eating this last piece.
$\mathrm{(ii)}$ By the method that is similar to the one used in
$\mathrm{(i)}$, we prove $(ii)$.
$\mathrm{(iii)}$ Suppose that $R$ starts with a position in $\mathcal{L}$.
$\mathrm{(iii.1)}$ If he starts with a position $(2n+5,1,0)\in\mathcal{L}_{1}$
with $n\in\mathbb{Z}_{\geq 0}$, there are two cases.
$\mathrm{(iii.1.1)}$ If $n=2m$ for $m\in\mathbb{Z}_{\geq 0}$, then
$2n+5=4(m+1)+1$. By $(ii)$ of Lemma 7, he moves to one of

$(2m+3,1,0),\cdots,(4m+4,1,0).$ (9)

$\mathrm{(iii.1.2)}$ If $n=2m+1$ for $m\in\mathbb{Z}_{\geq 0}$, then
$2n+5=2(2m+1)+5=4(m+1)+3$. By $(iii)$ of Lemma 7, he moves to one of

$(2m+3,1,0),\cdots,(4m+6,1,0).$ (10)

For any position in (9) and (10), the 1st coordinate is larger than or equal
to $3$. Therefore, by Definition 4.3 and Lemma 8, any chocolate bar in (9) and
(10) belongs to $\mathcal{L}$ when the 1st coordinate is odd and bigger than
5, and it belongs to $\mathcal{N}$ when the 1st coordinate is three or an even
number bigger than 4.
$\mathrm{(iii.2)}$ If he starts with a position in $\mathcal{L}_{2}$, we can
prove by a method that is similar to the one used in $\mathrm{(iii.1)}$.
$\mathrm{(iii.3)}$ If he starts with a position $(1,1,0)$, he loses in the
game.
$\mathrm{(iv)}$ By the method that is similar to the one used in
$\mathrm{(iii)}$, we prove $(iv)$. ∎

######  Lemma 10.

If we start the game with a chocolate bar $(x,y,s)\in\mathcal{P}$ with
$x,y\in\mathbb{N}$ and $s=0,1$, then any move leads to a chocolate bar
$(v,w,t)\notin\mathcal{P}$, where $v,w\in\mathbb{N}$ and $t=0,1$.

###### Proof.

$\mathrm{(i)}$ Suppose that we start with the position

$A=(2^{n}(2p+5)-1,2^{m}(2p+5)-1,s)\in\mathcal{P}_{a}$ (11)

for some $n,m,p\in\mathbb{Z}_{\geq 0}$ and $s=0,1$. It is sufficient to
consider the case when we reduce the first coordinate. We prove this by
contradiction. We assume that we cut $A$ into $A_{1}$ and $A_{2}$, and eat
$A_{2}$ to get $A_{1}$.
$\mathrm{(i.1)}$ Suppose that
$A_{1}=(2^{k}(2p+5)-1,2^{m}(2p+5)-1,s)\in\mathcal{P}_{a}$ for
$k\in\mathbb{Z}_{\geq 0}$ such that $k<n$. Then the first coordinate of
$A_{2}$ is

$\displaystyle 2^{n}(2p$ $\displaystyle+5)-1-(2^{k}(2p+5)-1)$
$\displaystyle=(2^{n}-2^{k})(2p+5)$ $\displaystyle\geq 2^{n-1}(2p+5)$
$\displaystyle>2^{k}(2p+5)-1.$ (12)

By (12) and Lemma 6, the number of $0$ and $1$ in $A_{2}$ are larger than
those in $A_{1}$. This contradicts the definition of the game. Therefore,
$A_{1}\notin\mathcal{P}_{a}$.
$\mathrm{(i.2)}$ Suppose that $A_{1}\in\mathcal{P}_{b}\cup\mathcal{P}_{c}$.
Then, the second coordinate of $A_{1}$ is

$2^{m}(2p+5)-1=2^{k}4-1$ (13)

or

$2^{m}(2p+5)-1=2^{k}3-1$ (14)

for some $k\in\mathbb{N}$, but (14) and (13) are impossible, since $2p+5$ is
an odd number larger than or equal to 5. Therefore, any move does not lead to
a position in $\mathcal{P}_{b}\cup\mathcal{P}_{c}$.

By (11), the height and the width of $A$ is larger than or equal to $4$, any
move does not lead to $(1,2,s)$ or $(2,1,s)$ for $s=0,1$.
$\mathrm{(ii)}$. Next, we start with the position

$A=(x,y)=(2^{n}3-1,2^{m}4-1,s)\in\mathcal{P}_{b}$ (15)

for $n,m\in\mathbb{Z}_{\geq 0}\text{ and }s=0,1$. We cut $A$ into $A_{1}$ and
$A_{2}$, and eat $A_{2}$ to get $A_{1}$.

By (15), we have $x\geq 2$ and $y\geq 3$, and hence $A_{1}\neq(1,2,s)$ nor
$(2,1,s)$ for $s=0,1$. Therefore, we only have to prove that
$A_{1}\notin\in\mathcal{P}_{a}\cup\mathcal{P}_{b}\cup\mathcal{P}_{c}$.
$\mathrm{(ii,1)}$. First, we reduce the first coordinate.
$\mathrm{(ii,1.1)}$.Suppose that
$A_{1}=(2^{k}3-1,2^{m}4-1,s)\in\mathcal{P}_{b}$ for $k\in\mathbb{Z}_{\geq 0}$
such that $k<n$. Then the first coordinate of $A_{2}$ is

$\displaystyle 2^{n}3-$ $\displaystyle 1-(2^{k}3-1)$ $\displaystyle\geq
2^{n-1}3$ $\displaystyle>2^{k}3-1.$ (16)

By (16) and Lemma 6, the number of $0$ and $1$ in $A_{2}$ are larger than
those in $A_{1}$. This contradicts the definition of the game, and hence
$A_{1}\notin\mathcal{P}_{b}$.
$\mathrm{(ii,1.2)}$. If $A_{1}\in\mathcal{P}_{a}$, the second coordinate of
$A_{1}$ is

$2^{m}4-1=2^{k}(2p+5)-1$

for $k,p\in\mathbb{Z}_{\geq 0}$. This is impossible, and we have
$A_{1}\notin\mathcal{P}_{a}$.
$\mathrm{(ii,1.3)}$. If $A_{1}\in\mathcal{P}_{c}$, the second coordinate of
$A_{1}$ is

$2^{m}4-1=2^{k}3-1$ (17)

for some $k\in\mathbb{Z}_{\geq 0}$, and this is impossible, and
$A_{1}\notin\mathcal{P}_{c}$

Next, we reduce the second coordinate.
$\mathrm{(ii,2.1)}$ Suppose that
$A_{1}=(2^{m}3-1,2^{k}4-1,s)\in\mathcal{P}_{b}$ for $k<n$ such that
$k\in\mathbb{Z}_{\geq 0}$, then the first coordinate of $A_{2}$ is

$\displaystyle 2^{m}4-$ $\displaystyle 1-(2^{k}4-1)$ $\displaystyle\geq
2^{m-1}4$ $\displaystyle>2^{k}4-1.$

By (16) and Lemma 6, the number of $0$ and $1$ in $A_{2}$ are larger than
those in $A_{1}$. This contradicts the definition of the game. Therefore,
$A_{1}=(2^{m}3-1,2^{k}4-1,s)\notin\mathcal{P}_{b}$.
$\mathrm{(ii,2.2)}$ If $A_{1}\in\mathcal{P}_{a}$, we have

$2^{m}3-1=2^{k}(2p+5)$

for $k,p\in\mathbb{Z}_{\geq 0}$. This is impossible, and we have
$A_{1}\notin\mathcal{P}_{a}$.
$\mathrm{(ii,2.3)}$ If $A_{1}\in\mathcal{P}_{c}$, we have

$2^{m}3-1=2^{k}4-1$

for some $k\in\mathbb{Z}_{\geq 0}$, and this is impossible. Therefore, we have
$A_{1}\notin\mathcal{P}_{c}$.
$\mathrm{(iii)}$ If we start with the position
$(2^{n}4-1,2^{m}3-1,s)\in\mathcal{P}_{c}$ for $n,m\in\mathbb{Z}_{\geq 0}\text{
and }s=0,1$. Then, we can use a method very similar to the one used in
$\mathrm{(ii)}$.
$\mathrm{(iv)}$ If we start with the position $(2,1,s)$ or
$(1,2,s)\in\mathcal{P}_{c}$ for $s=0,1$, then $L$ moves to
$(1,1,1)\in\mathcal{R}$ and $R$ moves to $(1,1,0)\in\mathcal{L}$. ∎

######  Lemma 11.

We have the following $(i)$ and $(ii)$:
$(i)$ If $L$ starts with a position in $\mathcal{P}$, then she always moves to
a position in $\mathcal{R}\cup\mathcal{N}$.
$(ii)$ If $R$ starts with a position in $\mathcal{P}$, then he always moves to
a position in $\mathcal{L}\cup\mathcal{N}$.

###### Proof.

$\mathrm{(i)}$ If $L$ starts with a position in $\mathcal{P}$, by Lemma 10 she
cannot move to a position in $\mathcal{P}$. Therefore, she always move to a
position in $\mathcal{L}\cup\mathcal{R}\cup\mathcal{N}$.

It is sufficient to show that she cannot move to a position in $\mathcal{L}$.
$\mathrm{(i.1)}$ If $L$ starts with $(1,2,s)$ or $(2,1,s)$ with $s=1,2$, then
she always move to $(1,1,1)\in\mathcal{R}$.
$\mathrm{(i.2)}$ Suppose that $L$ starts with
$A\in\mathcal{P}_{a}\cup\mathcal{P}_{b}\cup\mathcal{P}_{c}$, and moves to the
position $B\in\mathcal{L}$.
$\mathrm{(i.2.1)}$ For $B=(2n+5,1,0)$ or $B=(1,2n+5,0)\in\mathcal{L}$, we
prove only the case that $B=(2n+5,1,0)\in\mathcal{L}$. By Lemma 6 we have

$A=(2n+5,2,s)$ (18)

for $s=1,2$ or

$A=(m,1,s)$ (19)

for $m\in\mathbb{N}$ such that $m>2n+5$ and $p=0,1$.

When we have (18), there is $B^{\prime}=(2n+5,1,1)$ such that $A=B\cup
B^{\prime}$. Since the number of $1$ in $B^{\prime}$ is larger than that of
$B$, by the rule of the game, $L$ cannot eat $B^{\prime}$ to get $B$. this
contradicts the rule of the game.

When we have (19), by Definition 4.2 we have $A\notin\mathcal{P}$. This leads
to a contraction.
$\mathrm{(i.2.2)}$ If $B=(1,1,0)$, then $A=(2,1,1)=B\cup(1,1,1)$ or
$A=(1,2,1)=B\cup(1,1,1)$. Here, we have a contradiction since $L$ cannot eat
$(1,1,1)$.
$\mathrm{(ii)}$ We prove $(ii)$ by a method that is similar to the one used in
$\mathrm{(i)}$. ∎

######  Lemma 12.

We have the following $(i)$ and $(ii)$:
$(i)$ If $L$ starts the game with a position $(x,y,s)\in\mathcal{N}$, then she
can move to a position $(v,w,t)\in\mathcal{P}\cup\mathcal{L}$.
$(ii)$ If $R$ starts the game with a position $(x,y,s)\in\mathcal{N}$, then he
can move to a position $(v,w,t)\in\mathcal{P}\cup\mathcal{R}$.

###### Proof.

$\mathrm{(i)}$ Suppose that $L$ start with the position
$A=(x,y,s)\in\mathcal{N}$. Since $x\in\mathbb{N}$, by Lemma 5, we have the
following cases $\mathrm{(i.1)}$, $\mathrm{(i.2)}$, $\mathrm{(i.3)}$ and
$\mathrm{(i.4)}$.
$\mathrm{(i.1)}$ Suppose that $x=1$. Then, we start with the position
$A=(1,y,s)\in\mathcal{N}$.

By Definition 4.2, Definition 4.3 and Definition 4.4, we have $A\neq(1,2,s)$,
$A\neq(1,1,s)$ and $A\neq(1,2n+5,s)$ for any $n\in\mathbb{Z}_{\geq 0}$ and
$s=0,1$. Therefore, we have $A=(1,3,s)$, $(1,4,s)$ or $(1,2n+6,s)$ for
$n\in\mathbb{Z}_{\geq 0}$ and $s=0,1$.

If $(1,y,s)=(1,3,s)$ or $(1,4,s)$, then $L$ can move to $(1,2,s)$.

If $(1,y,s)=(1,2n+6,s)$, $L$ can move to $(1,2n+5,0)\in\mathcal{L}$.
$\mathrm{(i.2)}$ Suppose that $x=2^{n}4-1$ for some $n\in\mathbb{Z}_{\geq 0}$.
Then, we have the following two cases $\mathrm{(i.2.1)}$ and
$\mathrm{(i.2.2)}$.
$\mathrm{(i.2.1)}$ Suppose that there exists $k\in\mathbb{Z}_{\geq 0}$ such
that

$2^{k}3-1<y<2^{k+1}3-1.$

Since

$y\leq 2^{k+1}3-2,$

we have

$0<y-(2^{k}3-1)\leq 2^{k}3-1.$

Let $A_{1}=(x,2^{k}3-1,s)$ and $A_{2}=(x,y-(2^{k}3-1),s)$. If $A_{1}$ and
$A_{2}$ are the same size, $A_{1},A_{2}\in\mathcal{P}$. Then, $L$ can eat the
chocolate bar that contains less or equal number of $1$ than or to the other,
and get a chocolate bar in $\mathcal{P}$. If $A_{1}$ is bigger than $A_{2}$,
$L$ eats $A_{2}$ to get $A_{1}\in\mathcal{P}$.
$\mathrm{(i.2.2)}$ Suppose that

$y<2^{0}3-1=2.$

Then, we have $y=1$, and we prove by a method that is similar to the one used
in $\mathrm{(i.1)}$.
$\mathrm{(i.3)}$ Suppose that $x=2^{n}3-1$ for some $n\in\mathbb{Z}_{\geq 0}$.
$\mathrm{(i.3.1)}$ Suppose that there exists $k\in\mathbb{Z}_{\geq 0}$ such
that

$2^{k}4-1<y<2^{k+1}4-1.$

Then we have

$0<y-(2^{k}4-1)\leq 2^{k}4-1,$

and the rest of the proof of this case is similar to the one in
$\mathrm{(i.2.1)}$.
$\mathrm{(i.3.2)}$ Suppose that

$y<2^{0}4-1=3.$

If $y=1$, we use a method that is similar to the one used in $\mathrm{(i.1)}$.
Suppose that $y=2=2^{0}3-1$.
$\mathrm{(i.3.2.1)}$ Suppose that $n\geq 1.$ Since

$2^{n}3-1<2^{n}4-2,$

we have

$0<2^{n}3-1-(2^{n-1}4-1)<2^{n-1}4-1.$

Let $A_{1}=(2^{n-1}4-1,2,s)$ and $A_{2}=(2^{n}3-1-(2^{n-1}4-1),2,t)$ with
$t=0,1.$ $L$ can eat $A_{2}$ to get $A_{1}\in\mathcal{P}_{c}$.
$\mathrm{(i.3.2.2)}$ Suppose that $n=0.$ Then, $A=(2,2,s)$, and we let
$A_{1}=(2,1,0)$ and $A_{2}=(2,1,1)$. Then, we have $A=A_{1}\cup A_{2}$, and
$L$ can eat $A_{1}$ to get $A_{2}$.
$\mathrm{(i.4)}$. Suppose that $x=2^{n}(2p+5)-1$ for some
$n,p\in\mathbb{Z}_{\geq 0}$. Since $(x,y,s)\in\mathcal{N}$, by Definition 4.2,
we have the following two cases $\mathrm{(i.4.1)}$ and $\mathrm{(i.4.2)}$.
$\mathrm{(i.4.1)}$ Suppose that there exists $k\in\mathbb{Z}_{\geq 0}$ such
that

$2^{k}(2p+5)-1<y<2^{k+1}(2p+5)-1.$

Since $y\leq 2^{k+1}(2p+5)-2$, we have

$0<y-(2^{k}(2p+5)-1)\leq 2^{k}(2p+5)-1.$

Let $A_{1}=(x,2^{k}(2p+5)-1,s)$ and $A_{2}=(x,y-(2^{k}(2p+5)-1),t)$ with $t=0$
or $1$. If we have

$0<y-(2^{k}(2p+5)-1)<2^{k}(2p+5)-1,$

then by Lemma 6 and Remark 6, the number of 1 in $A_{2}$ is smaller than that
of 1 in $A_{1}$. Therefore, $L$ can eat $A_{2}$ to get $A_{1}\in\mathcal{P}$.

If we have

$y-(2^{k}(2p+5)-1)=2^{k}(2p+5)-1,$

then $A_{1}$ and $A_{2}$ are of the same size, and
$A_{1},A_{2}\in\mathcal{P}$. Player $L$ can eat $A_{1}$ or $A_{2}$ that
contains less or equal $1$ than or to the other to get a chocolate bar in
$\mathcal{P}$.
$\mathrm{(i.4.2)}$ Suppose that

$y<(2p+5)-1=2p+4.$ (20)

Since $y\in\mathbb{N}$, by Lemma 5, we have the following cases
$\mathrm{(i.4.2.1)}$, $\mathrm{(i.4.2.2)}$, $\mathrm{(i.4.2.3)}$ and
$\mathrm{(i.4.2.4)}$.
$\mathrm{(i.4.2.1)}$ Suppose that there exist $k,q\in\mathbb{Z}_{\geq 0}$ such
that

$y=2^{k}(2q+5)-1.$ (21)

By (20), there exists $u\in\mathbb{Z}_{\geq 0}$ such that

$\frac{2p+5}{2^{u+1}}\leq 2^{k}(2q+5)<\frac{2p+5}{2^{u}}.$

Then, we have

$\frac{2p+5}{2}\leq 2^{k+u}(2q+5)<2p+5,$

and hence we have

$p+3\leq 2^{k+u}(2q+5)<2p+5.$ (22)

By (22) we have

$\displaystyle 2^{k+u}(2q+5)$ $\displaystyle>p+2$ $\displaystyle=2p+5-(p+3)$
$\displaystyle\geq 2p+5-2^{k+u}(2q+5).$ (23)

We fix $y$, and reduce the first coordinate $x=2^{n}(2p+5)-1.$ Let
$A_{1}=(2^{n}(2^{k+u}(2q+5))-1,y,s)$ and
$A_{2}=(2^{n}(2p+5-2^{k+u}(2q+5)),y,t)$ with $t=0,1$. By
(21),$A_{1}\in\mathcal{P}$. By (23) we have

$2^{n}(2^{k+u}(2q+5))-1\geq 2^{n}(2p+5-2^{k+u}(2q+5)).$

If

$2^{n}(2^{k+u}(2q+5))-1>2^{n}(2p+5-2^{k+u}(2q+5)),$

by Lemma 6 and Remark 6, the number of 1 in $A_{2}$ is smaller than that of 1
in $A_{1}$. Since $A=A_{1}\cup A_{2}$, $L$ can get $A_{1}\in\mathcal{P}$ by
eating $A_{2}$. If

$2^{n}(2^{k+u}(2q+5))-1=2^{n}(2p+5-2^{k+u}(2q+5)),$

then we also have $A_{2}\in\mathcal{P}$, and $L$ can choose $A_{1}$ or $A_{2}$
according to the number of $1$, and eat the one with a smaller number of $1$.
If the number of $1$ is the same for both, $L$ can eat either of them. In this
way, she can get a chocolate bar in $\mathcal{P}$.
$\mathrm{(i.4.2.2)}$ Suppose that there exist $k\in\mathbb{Z}_{\geq 0}$ such
that $y=2^{k}4-1$. Then, we prove by a method that is similar to the one used
for $x=2^{n}4-1$ in $\mathrm{(i.2)}$.
$\mathrm{(i.4.2.3)}$ Suppose that there exist $k\in\mathbb{Z}_{\geq 0}$ such
that $y=2^{k}3-1$. Then, we prove by a method that is similar to the one used
for $x=2^{n}3-1$ in $\mathrm{(i.3)}$.
$\mathrm{(i.4.2.4)}$ Suppose that $y=1$. Then, we prove by a method that is
similar to the one used for $x=1$ in $\mathrm{(i.1)}$.
$\mathrm{(ii)}$ We can prove the case for the case of Player $R$ by a method
that is very similar to the one used for Player $L$ in $\mathrm{(i)}$. ∎

######  Theorem 7.

We have the following $(i)$, $(ii)$, $(iii)$, and $(iv)$:
$(i)$ The set $\mathcal{P}$ is the set of $\mathcal{P}$-positions.
$(ii)$ The set $\mathcal{N}$ is the set of $\mathcal{N}$-positions.
$(iii)$ The set $\mathcal{L}$ is the set of $\mathcal{L}$-positions.
$(iv)$ The set $\mathcal{R}$ is the set of $\mathcal{R}$-positions.

###### Proof.

By Lemma 4 and Lemma 11, we have $(i)$, and by Lemma 4 and Lemma 12, we have
$(ii)$.

By Lemma 4 and Lemma 9, we have $(iii)$ and $(iv)$. ∎

Figure 18: P-positions of
a partizan chocolate bar game.

Figure 19: P-positions of
an impartial chocolate bar game

The set of $\mathcal{P}$-positions of a partizan chocolate bar game is
different from, but is very similar to the set of $\mathcal{P}$-positions of
an impartial chocolate bar game. See Figure 19 and Figure 19.

##  5 The Prospect of Further Research

The authors are studying three-dimensional chocolate games, and the impartial
version is an easy generalization, but the partizan version is a challenging
problem. The authors have not managed to find formulas for the set of previous
players’ positions.

## Acknowledgements

This work was supported by JSPS KAKENHI Grant Number 23H05173.

We would like to thank Prof. R. J. Nowakowski for his useful advice, and we we
would like to thank Editage (www.editage.com) for English language editing.

## References

  * [1] M. H. Albert, R. J. Nowakowski and D. Wolfe, Lessons In Play: An Introduction to Combinatorial Game Theory, Second Edition, A K Peters/CRC Press, Natick, MA., United States, 2019.
  * [2] D. Gale, A Curious Nim-type Game, The American Mathematical Monthly Vol. 81, No. 8  (1974), 876-879.
  * [3] L. Levine, Fractal sequences and restricted Nim, Ars Combinatoria 80 (2006), 113-127.
  * [4] R.Miyadera and Y.Nakaya, Grundy Numbers of Impartial Three-Dimensional Chocolate-Bar Games, Integers 21B (2021), #A19.
  * [5] R. Miyadera, S. Nakamura and H. Manabe, Maximum Nim and Chocolate Bar Games, To appear in Thai Journal of Mathematics.
  * [6] S.Nakamura, R.Miyadera and Y.Nakaya, Impartial chocolate bar games, Integers 15 (2015), #G4.
  * [7] S. Nakamura, R. Miyadera and Y. Nakaya, Impartial Chocolate Bar Games, Grundy Numbers of Impartial Chocolate Bar Games, Integers 20 (2020), #G1.
  * [8] J.Radoszewski, M.Kubica and S.Wasik, Rectangle Game, the 17th International Olympiad in Informatics Solutions and booklet, https://ioinformatics.org/files/ioi2005solutions.pdf
  * [9] A. C.Robin, A poisoned chocolate problem,
Math. Gaz. No. 466 (1989), 341-343.

  * [10] The chocolate bar game, The Math Less Traveled https://mathlesstraveled.com/2016/01/14
/the-chocolate-bar-game/