Réunion d'été SMC 2013

Université Dalhousie, 4 - 7 juin 2013


Théorie combinatoire des jeux
Org: Richard Nowakowski et Paul Ottaway (Dalhousie)

ALEX FINK, North Carolina State University
Lim: an impartial game elucidated by a coordinate change  [PDF]

We present an analysis of the impartial game Lim, including a computation of its G-values, and its relation to the Ulam-Warburton cellular automaton.

URBAN LARSSON, Mathematical Sciences, Chalmers and University of Gothenburg
A Doubling game avoiding three term arithmetic progressions  [PDF]

We consider the following Doubling game on a heap of tokens: the next player removes any positive number of tokens, \emph{or} first doubles the previous player's removal and then removes any number of tokens from the remaining heap. A player who is unable to double the previous player's removal wins. Hence, you never want to remove more than half of the remaining heap. The starting position is special, because the previous removal is empty. We prove that the starting position is in P if and only if the heap size does not contain any $2$s in its ternary expansion. This sequence was first studied by Szekeres, Erd\H{o}s and Tur\'{a}n, obtained by greedily avoiding non-trivial arithmetic progressions of the form $2y=x+z$, on the nonnegative integers. It cannot be simulated by standard (invariant) subtraction games on one heap of tokens. Thus we resolve a new class of sequences as winning positions of impartial games. Our Doubling game has equivalent formulations on hyper graphs, as board games and as comply games with vast generalizations on finite numbers of heaps. It can also be played as a Multiplication game, with potential in educational games/recreational mathematics.

RICHARD J. NOWAKOWSKI, Dalhousie University
Game Profiles  [PDF]

The profile of a partizan placement game on a board is the bi-variate polynomial that enumerates all the positions. We look at the profile of several games. We also show that the show why the bivariate and not the uni-variate polynomial is required by showing that on a bipartite board, the number of positions with k pieces in COL is the same as in SNORT.

Dicots, and a taxonomic ranking for misère games  [PDF]

We study combinatorial games in misère version. In a general context, little can be said about misère games. For this reason, several universes were earlier considered for their study, which can be ranked according to their inclusion ordering. We study in particular a special universe of games called dicots, which turns out to be the known universe of lowest rank modulo which equivalence in misère version implies equivalence in normal version. We also prove that modulo the dicot universe, we can define a canonical form as the reduced form of a game that can be obtained by getting rid of dominated options and most reversible options. We finally count the number of dicot equivalence classes of dicot games born by day $3$.

FRASER STEWART, Xi'An Jiaotong University
Scoring Play Combinatorial Games  [PDF]

Games where the winner is determined by the score, rather than who moves last, are not very well understood. In this talk I will introduce the most general theory for this class of games, that has so far been developed. I will then demonstrate that there is a proper subset of scoring games that is exactly equivalent to the set of normal play games, and a proper subset that is exactly equivalent to the set of mis\`ere play games. This will show that all combinatorial games can be analysed using scoring play combinatorial game theory.

Surreal Analysis: An Analogue of Real Analysis for Surreal Numbers  [PDF]

Surreal numbers, which were discovered as part of analyzing combinatorial games, possess a rich numerical structure of their own and share many arithmetic and algebraic properties with real numbers. In order to develop the theory of surreal numbers beyond simple arithmetic and algebra, mathematicians have initiated the formulation of surreal analysis, the study of surreal functions and calculus operations. In this paper, we extend their work with a rigorous treatment of transcendental functions, limits, derivatives, power series, and integrals. In particular, we propose surreal definitions of three new analytic functions using truncations of Maclaurin series. Using a new representation of surreals, we present formulae for limits of sequences and functions (hence derivatives). Although the class of surreals is not Cauchy complete, we can still characterize the kinds of surreal sequences that do converge, prove the Intermediate Value Theorem, and establish the validity of limit laws for surreals. Finally, we show that some elementary power series and infinite Riemann sums can be evaluated using extrapolation, and we prove the Fundamental Theorem of Calculus for surreals so that surreal functions can be integrated using antidifferentiation. Extending our study to defining other analytic functions, evaluating power series in generality, finding a consistent method of Riemann integration, proving Stokes' Theorem to further generalize surreal integration, and solving differential equations remains open.

This research was conducted under the supervision of Dr. Simon Rubinstein-Salzedo, a professor of mathematics at Dartmouth College while the author was a high school student at the Harker School, San Jose, CA 95129.

MIKE WEIMERSKIRCH, University of Minnesota
Why David Gale’s ‘Nim with Pass’ is difficult to solve  [PDF]

In 2009, David Gale asked for an analysis of Nim played with the option of a single pass by either of the players. Here we find a solution if the heap size is restricted to be no more than four. The associated quotient monoid is infinite, which makes further computation more challenging.


Centre de recherches mathématiques AARMS: Atlantic Association for Research in the Mathematical Sciences Fields Institute Institut des sciences mathématiques Pacific Institute for the Mathematical Sciences

© Société mathématique du Canada : http://www.smc.math.ca/