Title: Twenty years of my research on combinatorial game theory with high school students -Chocolate Games, Games with a Pass, Maximum Nim-
Speaker: Ryohei Miyadera
Abstract
I will talk about three topics: chocolate games, games with a pass, and Maximum Nim. I have been researching these topics with my high school students for more than 20 years. These three topics are related to each other. Arguably, I was the first in the world to take up combinatorial games as a topic for a high school math research group and publish papers with students. My high school students and I read about rectangular chocolate games twenty years ago, and rectangular chocolate games are disguised Nim. These games are mathematically the same as three-pile Nim but have representations that differ from classical Nim. It is often the case that a different representation offers a different path for research, and this rectangular chocolate gave my students and me a perfect opportunity to conduct research. By changing the shape of chocolates, we developed a variety of Nim variants and published nine articles on chocolate games. We discovered the necessary and sufficient conditions for chocolate games to have the Grundy-number formula described by the nim-sum, and some sufficient conditions for chocolate games to have a formula for P-positions described by the nim-sum. About 10 years ago, we began studying games with a pass. This pass move may be used at most once in the game and not from the terminal position. In the case of classical Nim, the introduction of the pass alters the game’s mathematical structure, considerably increasing its complexity, and finding the formula that describes the set of previous players’ winning positions remains an important open question. We wondered why a pass move makes traditional Nim too complicated and began studying many games with a pass, and found that Chocolate Game, Maximum Nim, Wythoff’s Game, and Silver Dollar Game have formulas for P-positions when a pass is permitted. We discovered a sufficient condition for chocolate games with a pass to have Grundy-number formulas. We also found a sufficient condition for games in general to have formulas for P-positions, and well-known games such as Wythoff’s Game, Silver Dollar Game, Maximum Nim, and Greedy Nim satisfy this condition. We also studied Maximum Nim without a pass and discovered a fascinating relation between Maximum Nim and the Josephus problem. We found a formula to calculate the P-positions of Maximum Nim without using recursion, which enables us to efficiently determine the last remaining number in the Josephus problem. In Chess, Go, and Shogi (Japanese Chess), there are many very young professional players, indicating the significant potential of young talent in the study of games. I hope that many young people will discover many new things in combinatorial games in the coming decades.