## Chocolate Games NB   CDF   PDF

### How High School Students Discovered New Formulas Using Mathematica

This article presents the results of high school mathematics research projects. The authors are Dr. Miyadera and four high school students. Under the leadership of Dr. Miyadera, students have been doing mathematical research using Mathematica for more than 15 years, and they have discovered many formulas and theorems. They have given talks at conferences and published their results in mathematics magazines. In this article the authors present the results of the research on chocolate games, which are variants of the game of Nim. That high school students can discover new theorems and formulas with Mathematica is very important for mathematics education. The authors think that the best way to learn how to be creative is to make something new. The combination of Mathematica and the fresh minds of high school students can produce remarkable results.

### Introduction

We study well-known chocolate games and new ones that we have invented. Most of the games presented here have simple formulas for the set of losing states, but many do not, and it is interesting that those have very beautiful graphs for the set of losing states.

### Bitter Chocolate Games That Are Variants of Nim

The setup for Nim is a set of heaps that contain objects. For example, three heaps might contain three, four, and five objects. Two players alternate in taking any positive number of objects away from a single heap. The player who takes the last object loses.

Chocolate games generalize Nim to two dimensions. In this section we study well-known chocolate games and variations created by the authors. The chocolate games are simple to play, but they are interesting mathematically.

Definition 1

In a rectangular piece of chocolate made of squares, the brown parts are sweet and a single blue square is very bitter. Two players play alternately. To move, a player breaks the chocolate in a straight line along one of the grooves and eats the rectangular piece broken off. The player who takes the bitter square loses. The same game can be played with a rectangular box made of cubes.

There are other types of chocolate games; one of the most well-known is Chomp [1]. Again the chocolate is a rectangle made of squares, with the top-left square being very bitter. To move, a player removes a square and all the squares below it and to its right. Many people have studied this game and many interesting theories about it have been developed.

Each chocolate game treated in this article satisfies an inequality, so they are very different from Chomp, and for certain types of inequalities the mathematical structure of the winning strategy is very simple.

#### The Rectangular Chocolate Games

##### Can You Win This 2D Game?

Play the chocolate game in Figure 1 with “nim-sum” unchecked. Choose the values of , , and then click “new game.” Each time you click a line (not a square), you break the chocolate into two pieces along that line and eat the piece without the bitter square [2]. The game coordinates , , are the number of squares to the left, above, and to the right of the blue square, respectively.

Figure 1. Chocolate game 1: a rectangular chocolate game.

In chocolate games there are two kinds of states.

Definition 2

A winning state is a state from which we can force a win as long as we play correctly at every stage. A losing state is a state from which we lose no matter how well we play, if our opponent plays correctly.

The mathematical structure of chocolate game 1 is well-known, and there is a formula to calculate losing states.

Proposition 1

The state is a losing state of chocolate game 1 if and only if , where is the bitwise exclusive-or operation (the same as BitXor in Mathematica).

For a proof, see [2].

Once we know the formula for losing states, the strategy to win is clear. Suppose that you have a winning state. Then you can choose a move that gives your opponent a losing state. Any move by your opponent is a winning state for you, and you can always move to a losing state again. Finally, you reach and win the game.

You can use this strategy in chocolate game 1 by selecting “nim-sum.” For each state you see , and you know if the state is a losing state or a winning state.

##### Can You Win This 3D Game?

In the box chocolate game, the bitter (blue) cube is at the bottom of the 3D chocolate; to see it, drag to rotate.

Chocolate game 2 is a little more complicated than chocolate game 1, but the mathematical structure is almost the same.

In chocolate game 2, there are five controls. (You cannot cut the chocolate by clicking a face.)

Proposition 2

The state is a losing state of chocolate game 2 if and only if .

For a proof, see [2].

Figure 2. Chocolate game 2: a chocolate game in a box. The blue cube is underneath; to see it, drag to rotate.

#### Can You Win These New Chocolate Games?

Here are some new chocolate games.

##### Chocolate Games That Satisfy the Inequality

In chocolate game 3, you can cut the chocolate in three ways: to the left or right of the blue piece, or above it. The coordinates , , and are the maximum number of times you can cut the chocolate in those directions.

The geometry is such that clicking lines with low values of also deletes lines, so that the coordinates always satisfy ; that is, .

Figure 3. Chocolate game 3: a triangular chocolate game that satisfies the inequality .

Proposition 3

For , is a losing state of chocolate game 3 if and only if .

In fact this proposition is valid for chocolate games with the inequality for even . Although Proposition 3 is very similar to Proposition 1, their proofs are very different. For proofs, see [3] and [4].

##### Chocolate Games That Satisfy the Inequality

Chocolate game 4 is the same as chocolate game 3, but you can vary . In this game ; that is, for any state.

Figure 4. Chocolate game 4: triangular chocolate games that satisfy the inequality .

The authors are the first researchers who studied chocolate games whose coordinates satisfy inequalities.

For certain types of inequalities, the mathematical structure of the set of losing states is very similar to that of the well-known games of Nim and rectangular chocolate, but for most inequalities the mathematical structure of the set of losing states is very different.

##### Chocolate Games That Satisfy the Inequality

The authors could not find any simple formula for the losing states of triangular chocolate games whose coordinates satisfy the inequality . They present a conjecture for the formulas of losing states in Section 3 of [5]. It seems that chocolate games whose coordinates satisfy for odd do not have simple formulas for the set of losing states, because the set of losing states has very complicated graphs. In Figure 9 you can see graphs made by the set of losing states; for even the graph is a Sierpinski gasket and for odd the graph is complicated. As for the graphs made by losing states, see Figure 6.

##### Chocolate Games That Satisfy the Inequality

Figure 5. Triangular chocolate games that satisfy the inequality .

Conjecture 1

For a triangular chocolate game satisfying , is a losing state if and only if when (mod 4), and is a losing state if and only if when (mod 4).

This conjecture is Proposition 4 when and is proved for in [6].

For other types of chocolate games that the authors studied, see [7], [6], [8], and [9].

##### Chocolate Games That Satisfy the Inequality

Figure 6. The triangular chocolate game that satisfies the inequality .

Proposition 4

For the triangular chocolate game that satisfies the inequality , is a losing state if and only if .

For a proof, see [10].

##### Chocolate Games That Satisfy the Inequalities and

Figure 7. The chocolate game that satisfies the inequalities and .

Conjecture 2

For the chocolate game that satisfies the inequalities and , the state is a losing state of this chocolate game if and only if .

The authors have proved but not published this proposition.

##### Grundy Numbers and Chocolate Games

Here the authors present a Mathematica program to calculate losing states of the chocolate game whose coordinates satisfy the inequality . First define the function for each state of the chocolate and the function , where is a set of positive integers.

Definition 3

The function is the union of the four sets , , , and , where , , are non-negative integers.

Definition 4

The function is the smallest non-negative integer that is not an element of the set (the “minimum excluded ordinal”).

Example 1

and .

This defines the Grundy number recursively.

Definition 5

Let and .

Proposition 5

The state is a losing state of the chocolate game if and only if .

This is a well-known fact in the field of combinatorial games.

##### Restricting the Number of Rows and Columns You Can Remove

This game has two coordinates with the inequality ; and are the height and width of the chocolate when we ignore the blue part.

See Figure 8; here is the upper bound of the number of the rows and columns you can remove. Below the game is the table of Grundy numbers .

Figure 8. Chocolate games that satisfy the inequality .

Conjecture 3

Let , be natural numbers such that .
1. , for any natural number .
2. If , then .

### Mathematica Programs for Chocolate Games

#### Mathematica Programs to Calculate Losing States

By Proposition 5, is a losing state if and only if the Grundy number .

##### Calculating Losing States with Grundy Numbers

Here is a Mathematica program to calculate losing states using Grundy numbers. Here . This Mathematica program comes from [11]. The definition for mex is as in the code for Figure 8. The definitions for move3 and Gr3 are modifications of move and Gr from that code, so we change their names slightly.

These are the candidate states for a particular case.

This calculates the losing states using Grundy numbers.

Indeed these are losing states.

There are no other losing states.

##### Calculating Losing States Using Grundy-Like Numbers

Here the authors define the Grundy-like numbers , which are efficient to calculate.

Definition 6

For any state , let , where is defined by the following rules.
1. If , then let . If , then let . If , then let .
2. Suppose that and .
3. Let , if .
Let , if .
4. Suppose that and .
5. Let , if .
Let , if .
6. Suppose that and .
7. Let , if .
Let , if .

Proposition 6

The state is a losing state of the chocolate game if and only if .

For a proof of this proposition see Theorem 4.2 of [4].

This defines the corresponding Mathematica function G2.

This calculates the losing states using Grundy-like numbers.

They are exactly all the losing states.

### Graphs of the Set of Losing States

Here are some graphs of the set of losing states of chocolate games. (For more, see [10].)

##### 2D and 3D Graphs of the Set of Losing States of the Triangular Chocolate Game with

By Proposition 2 there is a simple formula for the set of losing states of the chocolate games satisfying , where is even. In Figure 9 the graph is a Sierpinski gasket for even .

When is odd, the graph is very different from a Sierpinski gasket. Since the graph is quite complicated, it seems likely that there is no simple formula for the set of losing states. As for the relation between the graphs of losing states and the Sierpinski gasket, see [7] (in Japanese).

Figure 9. Graphs of the set of losing states of the game whose coordinates satisfy inequalities , for .
##### 2D and 3D Graphs of the Set of Losing States of the Triangular Chocolate Game with

Figure 10 shows that the graph is the Sierpinski gasket for odd , so it seems that there may be a simple formula for the set of losing states in that case.

When , by Proposition 3 there is a simple formula for the set of losing states. When , the state is a losing state of this chocolate game if and only if [6]. The authors are now trying to find a simple formula for the set of losing states for an arbitrary odd number .

When is even, the graph is very different from the Sierpinski gasket. Since the graph is quite complicated, it seems that there is no simple formula for the set of losing states.

Figure 10. Graphs of the set of losing states of the games whose coordinates satisfy for .

### Other Chocolate Games

We can study many kinds of inequalities. For example, the chocolate games that satisfy the inequalities or are interesting, when is even and is a non-negative integer. The authors are studying these games.

### High School Mathematical Research Project

#### How High School Students Discovered New Chocolate Games

Dr. Miyadera taught the rectangular chocolate games presented in [2] to his students and encouraged them to make new chocolate games. Students were very good at proposing new types of chocolate games, including the ones in Figures 3-8. These students were the first people who studied chocolate games that satisfy inequalities.

As for the triangular chocolate game applications on smart phones, see [12], [13], and [14].

The fact that high school students could discover new theorems using computer algebra systems is very important for mathematics education. There are many teachers around the world who make students rediscover formulas in the classroom. In so-called “learning by doing,” students are supposed to rediscover formulas and theorems, while teachers know these formulas and theorems. In the authors’ high school research projects, students discover new things! The difference between discovery and rediscovery is very big, and the method the authors introduced can change mathematics education greatly.

The method used in the group is as follows.

First Dr. Ryohei Miyadera introduces some problems to the high school students, and after that students are required to create new problems by changing the conditions of the original problems. Sometimes they make a problem that is a little bit different from the original problem. At other times they propose a completely new problem. When the proposed problem seems to be very promising to Dr. Miyadera, he and his students begin to research it. They make computer programs using Mathematica and try to find interesting facts by calculation. Once they discover a new fact, they begin to prove it. Even if the proposed problem does not seem to be interesting enough, Dr. Miyadera encourages students to study it. It is often the case that a problem that seems to be trivial to him turns out to be a good problem. Some students have a kind of intuition that is beyond the imagination of Dr. Miyadera, who is an active mathematician himself. This method of research looks simple, but it is very effective.

In the history of this research group, more than 60 students have participated. Dr. Miyadera discovered that some students are very good at proposing new ideas while others are good at proving formulas and theorems. According to some researchers of mathematics education, there has never been a group of high school students that have been constantly discovering new formulas and theorems.

This group of students won the first prize in the Canada Wide Virtual Science Fair 2007, 2008, 2009, 2010, 2011, 2012, and 2013. They won the Imai Isao Award in 2007, which is the first prize in the Japan Wide High School Research Contest supported by Kogakuin University in Japan. They won the first prize in the Japan Science & Engineering Challenge 2008, and represented Japan in the International Science and Engineering Fair. (Japan declined to send them to the fair because of the epidemic of swine influenza.) They became finalists in the Japan Science & Engineering Challenge in 2011, 2012, and 2013. They became Google Science Fair Regional Finalists in 2012 and became semifinalists in the Yau High School Mathematics Awards in 2012 and 2013.

For a detailed explanation about the authors’ high school mathematics research project, see [15], [16], [17], [18], [19], [20], and [21]. The authors have presented their research at the International Mathematica Symposium in [22], [23], and [24].

They have also presented their research in the Mathematica Demonstrations Project, and Ryohei Miyadera was selected as a featured contributor. See [25], [26], and [27].

Dr. Miyadera received the Excellent Teacher Award from the Ministry of Education of Japan in 2012, and he received the Wolfram Innovator Award in 2012 for his research with high school students.

If you are interested in doing a high school or undergraduate mathematics research project, one of the best books to use is by Cowen and Kennedy [11].

### Conclusion

If students use Mathematica freely with an experienced mathematician, they can discover a lot of new and interesting facts of mathematics. The difference between a true discovery and rediscovery is great. We think that the best way to learn how to be creative is to create new and interesting things.

### Acknowledgments

We would like to thank Professor Robert Cowen of the City University of New York for his encouragement when we met [22]; he gave his book [11] to us. We learned how to use Mathematica in our research by using his book. We also would like to thank Ed Pegg Jr of Wolfram Research and Professor Tadashi Takahashi for giving us valuable advice.

### References

Ryohei Miyadera received a Ph.D. (mathematics) at Osaka City University and received a second Ph.D. (mathematics education) at Kobe University. He has two fields of research: probability theory of functions with values in an abstract space and applications of Mathematica to discrete mathematics. He and his high school students have been doing research in discrete mathematics for more than 15 years. They have talked at IMS 2001 [24], IMS 2003 [22], and IMS 2004 [23]. They have also published more than 22 refereed articles. Ryohei Miyadera received the Excellent Teacher Award from the Ministry of Education of Japan in 2012, and he received the Wolfram Innovator Award in 2012. His hobby is long-distance running, and he is one of the best runners in the over-55-years-old group of his prefecture.

Shunsuke Nakamura has graduated from Kwansei Gakuin High School and is preparing for the entrance examination to university. He did mathematical research with Dr. Miyadera when he was a high school student at Kwansei Gakuin. He has published papers in [3], [4], [5], and [7]. He is a member of the Information Processing Society of Japan. Nakamura’s hobbies are playing the piano and playing video games.

Yu Okada is a high school student. He is a very serious player of Massively Multiplayer Online RPGs.

Tomoki Ishikawa is a university student at Kwansei Gakuin. He did mathematical research with Dr. Miyadera when he was a high school student at Kwansei Gakuin. He has published papers on origami mathematics. He is a photographer who received an excellent photography award in the Japan Wide Cultural Festival.

Ryo Hanafusa is a university student at Kwansei Gakuin. He did mathematical research with Dr. Miyadera when he was a high school student at Kwansei Gakuin. He has published papers in [3] and [4]. He is a photographer who received an excellent photography award in the Japan Wide Cultural Festival.

Mathematics Department
Kwansei Gakuin High School

runners@kwansei.ac.jp

Shunsuke Nakamura
Kwansei Gakuin High School
nakashun1994@gmail.com