Partition games

We introduce cut, the class of 2-player partition games. These are nim type games, played on a finite number of heaps of beans. The rules are given by a set of positive integers, which specifies the number of allowed splits a player can perform on a single heap. In normal play, the player with the l...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2020-10, Vol.285, p.509-525
Main Authors: Dailly, Antoine, Duchêne, Éric, Larsson, Urban, Paris, Gabrielle
Format: Article
Language:English
Subjects:
Arithmetic
Beans
Combinatorial games
Combinatorics
Computer Science
Discrete Mathematics
Games
Mathematics
Partition games
Partitions (mathematics)
Progressions
Take-and-break games
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We introduce cut, the class of 2-player partition games. These are nim type games, played on a finite number of heaps of beans. The rules are given by a set of positive integers, which specifies the number of allowed splits a player can perform on a single heap. In normal play, the player with the last move wins, and the famous Sprague–Grundy theory provides a solution. We prove that several rulesets have a periodic or an arithmetic periodic Sprague–Grundy sequence (i.e. they can be partitioned into a finite number of arithmetic progressions of the same common difference). This is achieved directly for some infinite classes of games, and moreover we develop a computational testing condition, demonstrated to solve a variety of additional games. Similar results have previously appeared for various classes of games of take-and-break, for example octal and hexadecimal; see e.g. Winning Ways by Berlekamp, Conway and Guy (1982). In this context, our contribution consists of a systematic study of the subclass ‘break-without-take’.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2020.05.032