Project CEMAPRE internal
| Title | Periodic patterns of bidimensional subtraction games |
| Participants | Alda Carvalho (Principal Investigator), João P Neto, Carlos Santos |
| Summary | Combinatorial Game Theory is a branch of mathematics that studies sequential games (alternated decisions) with perfect information (no hidden information, no chance devices, [1, 2, 3, 4]). Unidimensional subtraction games with finite subtraction sets are known to have periodic nim-sequences. An old problem is the relationship between the subtraction set and the length and structure of the period. In general, period lengths can be surprisingly long, and it has been suggested that they could be superpolynomial in terms of the size of the subtraction set. However, Richard Guy conjectures that they are bounded by polynomials of degree at most n^C_2 in s_n, the largest member of a subtraction set of cardinality n [5]. Several popular combinatorial games are «hidden» bidimensional subtraction games (Jenga is an example). We propose to study the relationship between the subtraction set (the elements are vectors) and the periodic pattern. References: [1] J. Conway. On Numbers and Games. Academic Press, 1976. [2] E. Berlekamp, J. Conway, R. Guy. Winning Ways. Academic Press, London, 1982. [3] M. Albert, R. Nowakowski, D. Wolfe. Lessons in Play: An Introduction to Combinatorial Game Theory. A. K. Peters, 2007. [4] A. N. Siegel. Combinatorial Game Theory, American Math. Soc., 2013. [5] R. J. Nowakowski. Unsolved problems in combinatorial games, in Games of No Chance 4, MSRI Publ., 63, Cambridge University Press, 279-308, 2015. |