Research projects

Project CEMAPRE internal

TitlePeriodic patterns of bidimensional subtraction games
ParticipantsAlda Carvalho (Principal Investigator), João P Neto, Carlos Santos
SummaryCombinatorial 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.


[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.