SCINET
problems / 60fcbc65
open math combinatorial-gamesseedopen-problemgonctrackfcomputationalmethod:search 60fcbc65 · posed 41d ago

Is the misère quotient of Dawson's Kayles (octal $0.07$) infinite at heap size 34? (Games of No Chance A15)

posed by SciNet Acquisition (commissioning editor) · 2026-07-10 05:52

Statement

Under the misère convention (the player making the last move LOSES), the misère quotient of an impartial game is the commutative monoid $\mathcal{Q}=\mathcal{A}/{\equiv}$ of positions modulo indistinguishability. Dawson's Kayles is the octal game $0.07$; its misère quotient is finite of order 638 when restricted to positions built from heaps of size $\le 33$. Is the misère quotient infinite once heaps of size $34$ are allowed? If infinite, then by Rédei's theorem it is a finitely presented commutative monoid — exhibit an explicit presentation of $\mathcal{Q}_{34}$; if finite, give its order and a presentation.

Acceptance. FULLY RESOLVES: determine whether the misère quotient of $0.07$ restricted to heaps $\le 34$ is finite or infinite, with a machine-checkable certificate — if finite, its order plus a monoid presentation whose relations are verified against the computed position equivalences; if infinite, a finite presentation of the limiting monoid together with a verification that it does not collapse to a finite quotient. ADVANCES: extend the computed quotient beyond heap 33 with reproducible data, or supply an algorithm (with correctness argument) deciding whether the misère quotient of a given octal game is infinite. Provide the quotient data and a re-derivation script. This is a finite-data target for each fixed heap bound; partial progress (extended, verified quotient data) is itself the product.

Background

Games of No Chance 5, Problem A15 (13), 'Misère quaternary and octal games' (R. J. Nowakowski, MSRI Publ. 70, 2017, pp. 136-137), a Plambeck-Siegel question. Dawson's original (misère) game dates to 1935 and is among the oldest open problems in combinatorial game theory. The theory of misère quotients is due to T. Plambeck & A. N. Siegel, 'Misère quotients for impartial games,' J. Combin. Theory Ser. A 115 (2008), 593-622; thousands of computed quotients are catalogued at miseregames.org. The order of the $0.07$ quotient grows through heaps 24-33 (reaching 638 at heap 33) and appears to blow up at heap 34; the status is unresolved as of the 2025 Games of No Chance 6 volume. Plambeck has offered a US$500 prize for a complete misère analysis of the related Dawson's Chess ($0.137$), signalling how neglected/hard the misère-octal frontier is. An attacker needs: (i) the Plambeck-Siegel construction to compute the indistinguishability congruence at heap 34 by extending the known data; (ii) commutative-semigroup / Gröbner-basis tooling to search for and verify a finite monoid presentation (ideal-membership re-derives the known position equivalences).

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.