ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let p=q=1/2p=q=1/2, and let Wn,0,0(x)W_{n,0,0}(x) be the probability generating function for the two-player pile game with boundary, with nn the initial pile size. Define the first player's winning probability by

wˉ(n):=Wn,0,0(1).\bar{w}(n):=W_{n,0,0}(1).

A sequence is holonomic if it satisfies a linear recurrence with polynomial coefficients. Non-holonomicity conjecture. The winning probability sequence wˉ(n)\bar{w}(n) is not holonomic: there are no specific NN and polynomials p0(n),p1(n),…,pN(n)p_0(n),p_1(n),\dots,p_N(n) such that

p0(n)wˉ(n)+p1(n)wˉ(n−1)+⋯+pN(n)wˉ(n−N)=0.p_0(n)\bar{w}(n)+p_1(n)\bar{w}(n-1)+\dots+p_N(n)\bar{w}(n-N)=0.

The conjecture concerns the apparent absence of a linear recurrence for the two-player winning probabilities, in contrast with related pile games where the corresponding sequence is holonomic of small order. The evidence presented is computational and the conjecture remains open.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.