Some results on LCTR, an impartial game on partitions

DOI10.2140/INVOLVE.2023.16.529MaRDI QIDQ6174698zbMATH OpenOpenAlexFDO

Authors Eric Gottlieb, Jelena Ilić, Matjaž Krnc

Publication date 17 August 2023

Published in Involve (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.04990

combinatorial game theory Grundy partition Sprague

Combinatorial aspects of partitions of integers (05A17) Combinatorial games (91A46) Algorithmic game theory and complexity (91A68)

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

l a m b d a

of

n

, determines the corresponding Sprague-Grundy value in

O (n)

time.

Review text

In this paper, the authors study a new impartial game called LCTR and played on integer partitions. Positions of LCTR are partitions (i.e., Young diagrams). Players take turns removing either the left-most column or the top row of the corresponding Young diagram, normal play convention is considered. They determine Sprague-Grundy values for certain infinite families of partitions (these values are bounded by \(2\) for any partition) and prove some complexity results. By analyzing the sparseness of the positions reachable from a given partition of \(n\), they use a dynamic programming approach which determines the corresponding Sprague-Grundy value in \(O(n)\) time.

Recommendations

Cited in

(4)

This page was built for publication: Some results on LCTR, an impartial game on partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6174698)