NBThis 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
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.
In chocolate games there are two kinds of states.
Definition 2
The mathematical structure of chocolate game 1 is well-known, and there is a formula to calculate losing states.
Proposition 1
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
is a losing state of chocolate game 2 if and only if 
.For a proof, see [2].
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, 
.
.Proposition 3
, 
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.
.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 
.Conjecture 1
, 
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 
.Proposition 4
, 
is a losing state if and only if 
.For a proof, see [10].
Chocolate Games That Satisfy the Inequalities 
and 
and 
.Conjecture 2
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
is the union of the four sets 
, 
, 
, and 
, where 
, 
, 
are non-negative integers.Definition 4
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
and 
.Proposition 5
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 
.
.Conjecture 3
, 
be natural numbers such that 
.
, for any natural number 
.- 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
, let 
, where 
is defined by the following rules.- If
, then let 
. If 
, then let 
. If 
, then let 
. - Suppose that
and 
. - Suppose that
and 
. - Suppose that
and 
.
, if 
.
, if 
.
, if 
.
, if 
.
, if 
.
, if 
.Proposition 6
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).
, 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.
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
| [1] | Wikipedia. “Chomp.” (Dec 4, 2013) en.wikipedia.org/wiki/Chomp. |
| [2] | A. C. Robin, “A Poisoned Chocolate Problem,” Problem Corner, The Mathematical Gazette, 73(466), 1989 pp. 341-343. (An answer for the above problem is in 74(468), 1990 pp. 171-173.) |
| [3] | R. Miyadera, S. Nakamura, and R. Hanafusa, “New Chocolate Games—Variants of the Game of Nim,” Proceedings of the Annual International Conference on Computational Mathematics, Computational Geometry & Statistics, Singapore, 2012 pp. 122-128. dl4.globalstf.org/?wpsc-product=new-chocolate-game-variants-of-the-game-of-nim. |
| [4] | R. Miyadera, S. Nakamura, and R. Hanafusa, “New Chocolate Games,” GSTF Journal of Mathematics, Statistics and Operations Research, 1(1), 2012 pp. 111-116. dl4.globalstf.org/?wpsc-product=new-chocolate-games. |
| [5] | S. Nakamura, Y. Naito, R. Miyadera et al., “Chocolate Games That Are Variants of Nim and Interesting Graphs Made by These Games,” Visual Mathematics, 14(2), 2012. www.mi.sanu.ac.rs/vismath/miyaderasept2012/index.html. |
| [6] | T. Yamauchi, T. Inoue, and Y. Tomari, “Variants of the Game of Nim That Have Inequalities as Conditions,” Rose-Hulman Institute of Technology, Undergraduate Math Journal, 10(2), 2009. www.rose-hulman.edu/mathjournal/archives/2009/vol10-n2/paper12/v10n2-12pd.pdf. |
| [7] | R. Miyadera and S. Nakamura, “A Chocolate Game,” Mathematics of Puzzles, Journal of Information Processing (special issue), 53(6), 2012 pp. 1582-1591 (in Japanese). |
| [8] | M. Naito, T. Yamauchi, T. Inoue et al., “Discrete Mathematics and Computer Algebra System,” Proceedings of the 9th Asian Symposium on Computer Mathematics-Mathematical Aspects of Computer and Information Sciences Joint Conference (ASCM-MACIS), Fukuoka, Japan: Kyushu University, 2009 pp. 127-136. gcoe-mi.jp/temp/publish/a2019bae287f4628e4bfc9d273150000.pdf. |
| [9] | MathPuzzle.com. “The Bitter Chocolate Problem.” Material added 8 Jan 06 (Happy New Year). www.mathpuzzle.com/26Feb2006.html. |
| [10] | T. Nakaoka, R. Miyadera et al., “Combinatorial Games and Beautiful Graphs Produced by Them,” Visual Mathematics, 11(3), 2009. www.mi.sanu.ac.rs/vismath/miyaderasept2009/index.html. |
| [11] | R. Cowen and J. Kennedy, Discovering Mathematics with Mathematica, Erudition Books, 2001. |
| [12] | M. Fukui, “Bitter Chocolate Games 1.” itunes.apple.com/jp/app/bitter-chocolate-games-1/id495880660?mt=8. |
| [13] | M. Fukui, “Bitter Chocolate Games 2.” itunes.apple.com/jp/app/bitter-chocolate-games-2/id502476677?mt=8. |
| [14] | S. Nakamura, “Poison Chocolate Game.” market.android.com/details?id=com.kgshmathclub.chocoapp. |
| [15] | R. Miyadera, T. Inoue, and S. Nakamura, “High School Mathematics Research Project Using Computer Algebra System,” Proceedings of the 16th International Seminar on Education of Gifted Students in Mathematics, The Korean Society of Mathematical Education, Chungnam National University, Daejeon, Korea, 2011 pp. 303-316. |
| [16] | S. Hashiba, D. Minematsu, H. Shimoda, and R. Miyadera, “How High School Students Can Discover Original Ideas of Mathematics Using Mathematica,” Mathematica in Education and Research 11(3), 2006. |
| [17] | H. Matsui, D. Minematsu, T. Yamauchi, and R. Miyadera, “Pascal-Like Triangles and Fibonacci-Like Sequences,” Mathematical Gazette, 94(529), 2010 pp. 27-41. |
| [18] | R. Miyadera, T. Hashiba, Y. Nakagawa, T. Yamauchi, H. Matsui, S. Hashiba, D. Minematsu, and M. Sakaguchi, “Pascal-Like Triangles and Sierpinski-Like Gaskets,” Visual Mathematics, 9(1), 2007. www.mi.sanu.ac.rs/vismath/miyad/pascalliketriangle.html. |
| [19] | H. Matsui and T. Yamauchi, “Formulas for Fibonacci-Like Sequences Produced by Pascal-Like Triangles,” Rose-Hulman Institute of Technology Undergraduate Math Journal, 9(2), 2008. www.rose-hulman.edu/mathjournal/archives/2008/vol9-n2/paper11/v9n2-11p.pdf. |
| [20] | H. Matsui, N. Saita, K. Kawata, Y. Sakurama, and R. Miyadera, “Elementary Problems, B-1019,” Fibonacci Quarterly, 44(3), 2006. www.fq.math.ca/Problems/August2006elementary.pdf. |
| [21] | R. Miyadera, “General Theory of Russian Roulette.” library.wolfram.com/infocenter/MathSource/5710. |
| [22] | R. Miyadera, K. Fujii et al., “How High School Students Could Present Original Math Research Using Mathematica,” The International Mathematica Symposium, 2003. library.wolfram.com/infocenter/Conferences/4983. |
| [23] | R. Miyadera and D. Minematsu, “Curious Properties of an Iterative Process: How Could High School Students Present Original Mathematics Research Using Mathematica?,” The International Mathematica Symposium, 2004. library.wolfram.com/infocenter/Conferences/6055. |
| [24] | R. Miyadera, “Using Mathematica in Doing the Research of Mathematics with High School Students,” Proceedings of the Fourth International Mathematica Symposium (IMS2001), Tokyo, 2001. |
| [25] | H. Matsui, T. Yamauchi, D. Minematsu, and R. Miyadera. “Pascal-Like Triangles Made from a Game” from the Wolfram Demonstrations Project—A Wolfram Web Resource. demonstrations.wolfram.com/PascalLikeTrianglesMadeFromAGame. |
| [26] | H. Matsui, T. Yamauchi, D. Minematsu, and R. Miyadera. “Pascal-Like Triangles Mod  ” from the Wolfram Demonstrations Project—A Wolfram Web Resource. demonstrations.wolfram.com/PascalLikeTrianglesModK. |
| [27] | T. Inoue, T. Nakaoka, and R. Miyadera. “A Bitter Chocolate Problem That Satisfies an Inequality” from the Wolfram Demonstrations Project—A Wolfram Web Resource. demonstrations.wolfram.com/ABitterChocolateProblemThatSatisfiesAnInequality. |
| R. Miyadera, S. Nakamura, Y. Okada, T. Ishikawa, and R. Hanafusa, “Chocolate Games,” The Mathematica Journal, 2013. dx.doi.org/doi:10.3888/tmj.15-12. | |
About the Authors
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.
Ryohei Miyadera
Mathematics Department
Kwansei Gakuin High School
runners@kwansei.ac.jp
miyadera1272000@yahoo.co.jp
Shunsuke Nakamura
Kwansei Gakuin High School
nakashun1994@gmail.com
Yu Okada
Kwansei Gakuin High School
alm1_a1m_aim@ezweb.ne.jp
Tomoki Ishikawa
Kwansei Gakuin High School
tom94826@gmail.com
Ryo Hanafusa
Kwansei Gakuin High School
ryo3waygate@yahoo.co.jp