Some results on LCTR, an impartial game on partitions

DOI10.2140/INVOLVE.2023.16.529zbMATH Open1521.91050arXiv2207.04990OpenAlexW4385737211MaRDI QIDQ6174698FDOQ6174698

Authors: Eric Gottlieb, Jelena Ilić, Matjaž Krnc 

Publication date: 17 August 2023

Published in: Involve (Search for Journal in Brave)

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 $lambda$ of $n$, determines the corresponding Sprague-Grundy value in $O(n)$ time.

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

Recommendations

• Partition games
• scientific article; zbMATH DE number 7306571
• Partizan octal games: Partizan subtraction games
• On pruning search trees of impartial games
• scientific article; zbMATH DE number 7674558

zbMATH Keywords

partitioncombinatorial game theoryGrundySprague

Mathematics Subject Classification ID

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

Cited In (2)

• Title not available (Why is that?)
• Sprague-Grundy values and complexity for LCTR

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)