Some results on LCTR, an impartial game on partitions

Gottlieb, Eric; Ilić, Jelena; Krnc, Matjaž

doi:10.2140/involve.2023.16.529

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

Some results on LCTR, an impartial game on partitions

Eric Gottlieb, Jelena Ilić and Matjaž Krnc

Vol. 16 (2023), No. 3, 529–546

DOI: 10.2140/involve.2023.16.529

Abstract

We apply the Sprague–Grundy theorem to LCTR, a new impartial game on partitions in which players take turns removing either the left column or the top row of the corresponding Young diagram. We establish that the Sprague–Grundy value of any partition is at most $2$ and determine Sprague–Grundy values for several infinite families of partitions. Finally, we devise a dynamic programming approach which, for a given partition $λ$ of $n$ , determines the corresponding Sprague–Grundy value in $O (n)$ time.

Keywords

combinatorial game theory, Sprague, Grundy, partition

Mathematical Subject Classification

Primary: 05A17, 91A46, 91A68

Milestones

Received: 12 July 2022

Accepted: 16 July 2022

Published: 10 August 2023

Communicated by Arthur T. Benjamin

Authors

Eric Gottlieb
Department of Mathematics and Computer Science Rhodes College Memphis, TN United States

Jelena Ilić
Faculty of Mathematics Natural Sciences and Information Technologies University of Primorska Koper Slovenia

Matjaž Krnc
Faculty of Mathematics Natural Sciences and Information Technologies University of Primorska Koper Slovenia

Vol. 16, No. 3, 2023