Detailed mathematical approach

Problem Summary

For every positive triple \((a,b,k)\) with \(a+b+k\le W\), the problem defines one staircase component of Young's Game B. Each component is a short partizan game, and \(S(m,W)\) counts ordered \(m\)-tuples of such components whose disjunctive sum is winning for Left, with the final answer taken modulo \(10^9+7\).

The target value is \(S(8,64)\). The compiled implementations first verify the smaller checkpoints \(S(2,4)=7\) and \(S(3,9)=315319\), then reuse the same machinery for the main case.

Mathematical Approach

The solution has two distinct layers. First, every staircase component is canonically reduced to a very restricted family of game values. Second, once that catalogue is known, the ordered \(m\)-tuples are counted by frequency distributions and a sparse dynamic program instead of explicit enumeration.

Staircase Components and Boundary Recursion

Fix positive integers \(a\), \(b\), and \(k\). For \(0\le i\lt a\) and \(0\le j\lt b\), let \(G_{a,b,k}(i,j)\) be the game state in row \(i\), column \(j\), and layer \(k\). Left moves in the \(j\)-direction, while Right moves in the \(i\)-direction. If a move would step past the boundary, play drops to the next smaller layer.

That gives the recursive options

$ G_{a,b,k}(i,j)=\{L_{a,b,k}(i,j)\mid R_{a,b,k}(i,j)\}, $

with

$ L_{a,b,k}(i,j)= \begin{cases} G_{a,b,k}(i,j+1), & j\lt b-1,\\ G_{a,b,k-1}(i,0), & j=b-1,\ k>1,\\ \varnothing, & j=b-1,\ k=1, \end{cases} $

and

$ R_{a,b,k}(i,j)= \begin{cases} G_{a,b,k}(i+1,j), & i\lt a-1,\\ G_{a,b,k-1}(0,j), & i=a-1,\ k>1,\\ \varnothing, & i=a-1,\ k=1. \end{cases} $

The staircase component associated with the triple \((a,b,k)\) is the top-left state \(G_{a,b,k}=G_{a,b,k}(0,0)\). Enumerating all triples with \(a,b,k\ge 1\) and \(a+b+k\le W\) produces the full catalogue of components.

Canonical Reduction and the Stop-Pair Invariant

Every raw game is reduced by the standard short-game rules: dominated options are removed, reversible moves are bypassed, and if all surviving left and right options are numbers with a gap between them, the game is replaced by the simplest dyadic rational in that interval. So the reduction engine is general enough to create arbitrary dyadic numbers if needed.

After reduction, the solver computes the left and right stops recursively:

$ L^{*}(G)=\max_{G^L} R^{*}(G^L), \qquad R^{*}(G)=\min_{G^R} L^{*}(G^R). $

The decisive empirical invariant for this problem is that every staircase component ends up in one of only two forms:

$ n\in\mathbb{Z}, \qquad\text{or}\qquad X(R,w)=\{R+w\mid R\}, \quad R\in\mathbb{Z},\ w\in\mathbb{Z}_{\ge 0}. $

In other words, the reduced non-numeric components are always single switches with integer stops. This is not treated as a vague heuristic; the compiled implementations explicitly check for it and stop if a staircase component falls outside that family.

Separating Integer Shifts from Switch Weights

Write

$ X(R,w)=R+U_w, \qquad U_w=\{w\mid 0\}. $

Now two frequency tables are enough to describe the whole catalogue:

$ f_{\mathrm{num}}(n)=\#\{\text{components equal to }n\}, $

and, for each weight \(w\),

$ f_w(R)=\#\{\text{components equal to }X(R,w)\}. $

The problem is therefore no longer about individual triples \((a,b,k)\); it becomes a counting problem over integers and switches classified by their weight and right endpoint.

Why Sorted Switches Collapse to Alternating Weights

The non-numeric part of any tuple sum is a sum of basic switches \(U_w\). When \(w_1\ge w_2\), canonical addition gives

$ U_{w_1}+U_{w_2}\equiv w_1. $

So if the selected switch weights are sorted in nonincreasing order,

$ w_1\ge w_2\ge \cdots \ge w_s, $

the top two switches collapse to the integer \(w_1\), the next two collapse to \(w_3\), and so on. If we also sum the right endpoints \(R_1,\dots,R_s\), then

$ R_\Sigma=\sum_{t=1}^{s}R_t, \qquad W_{\mathrm{odd}}=w_1+w_3+w_5+\cdots. $

The whole switch contribution becomes

$ \sum_{t=1}^{s}X(R_t,w_t)\equiv \begin{cases} R_\Sigma+W_{\mathrm{odd}}, & s\equiv 0 \pmod 2,\\ \{R_\Sigma+W_{\mathrm{odd}}\mid R_\Sigma+W_{\mathrm{odd}}-w_s\}, & s\equiv 1 \pmod 2. \end{cases} $

That is the key simplification behind the counting stage: after sorting by weight, the switch part remembers only \(s\), the sum of right endpoints, and the sum of the weights sitting in odd positions.

Counting Ordered Tuples by Frequency Distributions

For the purely numeric components, the implementations build ordered convolution tables

$ N_n(\sigma)=\sum_{x_1+\cdots+x_n=\sigma}\prod_{t=1}^{n}f_{\mathrm{num}}(x_t), $

which count ordered \(n\)-tuples of integers with total \(\sigma\).

For a fixed switch weight \(w\), they also build

$ D_{w,c}(\rho)=\sum_{R_1+\cdots+R_c=\rho}\prod_{t=1}^{c}f_w(R_t), $

the number of ordered \(c\)-tuples of weight-\(w\) switches whose right endpoints add to \(\rho\).

The sparse dynamic program processes weights from large to small. A state records

$ (s,\pi,\Sigma_R,\Sigma_{\mathrm{odd}}), \qquad \pi=s\bmod 2, $

where \(s\) is the number of chosen switches, \(\Sigma_R\) the accumulated sum of right endpoints, and \(\Sigma_{\mathrm{odd}}\) the accumulated odd-position contribution. If \(c\) new switches of weight \(w\) are added after the already processed heavier weights, the number of newly occupied odd positions is

$ \ell(c,\pi)= \begin{cases} \left\lceil\dfrac{c}{2}\right\rceil, & \pi=0,\\[4pt] \left\lfloor\dfrac{c}{2}\right\rfloor, & \pi=1. \end{cases} $

So the transition is

$ (s,\pi,\Sigma_R,\Sigma_{\mathrm{odd}}) \longrightarrow \bigl(s+c,\ \pi\oplus(c\bmod 2),\ \Sigma_R+\rho,\ \Sigma_{\mathrm{odd}}+\ell(c,\pi)w\bigr), $

with multiplicity \(\binom{s+c}{c}D_{w,c}(\rho)\). The binomial factor is required because the original tuples are ordered: the newly chosen weight-\(w\) switches can be interleaved with the already chosen heavier switches in \(\binom{s+c}{c}\) ways while preserving the internal order of each group.

After all switch weights have been processed, the remaining \(m-s\) entries must be integers. Interleaving those integers with the \(s\) switches contributes an additional factor \(\binom{m}{s}\). If the numeric part contributes \(\sigma\), define

$ T=\Sigma_R+\Sigma_{\mathrm{odd}}+\sigma. $

If \(s\) is even, the total game is the integer \(T\), so Left wins exactly when \(T>0\). If \(s\) is odd, the total game is the switch \(\{T\mid T-w_s\}\), so Left has a move to \(T\) and wins when \(T\ge 0\). Combining both cases gives the final criterion

$ \text{Left wins}\iff \bigl(T>0\bigr)\lor\bigl(T=0\land s\equiv 1 \pmod 2\bigr). $

Worked Example: The Checkpoint \(S(2,4)=7\)

For \(W=4\), the admissible triples produce exactly four staircase values:

$ G_{1,1,1}=0,\qquad G_{1,1,2}=\{0\mid 0\},\qquad G_{1,2,1}=1,\qquad G_{2,1,1}=-1. $

So the catalogue is \(\{0,\{0\mid 0\},1,-1\}\). The ordered pairs that are winning for Left are

$ (0,\{0\mid0\}),\ (\{0\mid0\},0),\ (0,1),\ (1,0),\ (1,\{0\mid0\}),\ (\{0\mid0\},1),\ (1,1). $

Hence

$ S(2,4)=7, $

exactly the checkpoint used by the solver before it tackles the larger inputs.

How the Code Works

Generating and Reducing Every Staircase Family

The C++ and Java implementations iterate over all \(a\) and \(b\). For fixed \(a\) and \(b\), they fill a three-dimensional table over \((k,i,j)\), working backward so that every left and right option has already been constructed when the current state is reduced. This directly implements the staircase recursion above.

Compressing the Catalogue into Integers and Switches

After each component \(G_{a,b,k}(0,0)\) is canonically reduced, the implementations compute its stop pair. Numeric components are counted by their integer value. Non-numeric components are required to have exactly one left option and one right option, both numbers, so they can be recorded as a switch \(X(R,w)\) using its right endpoint \(R\) and weight \(w\).

Convolutions, Sparse DP, and the Final Win Test

Once the catalogue has been compressed into frequency tables, the implementations precompute ordered convolutions for integers and for each switch weight, run the sparse DP over descending weights, and finally combine each reachable switch state with the appropriate numeric distribution. The Python implementation does not rebuild the game engine itself; it delegates to the compiled solver and returns the parsed result.

Complexity Analysis

The structural bottleneck is catalogue generation. For fixed \(a\) and \(b\), the temporary table has \((K+1)ab\) states, where \(K=W-a-b\). Summing that over all admissible pairs gives

$ \sum_{a=1}^{W-2}\sum_{b=1}^{W-a-1}ab(W-a-b)=\Theta(W^5). $

This stage uses \(O(W^3)\) temporary space for one staircase family at a time, plus memoized storage for canonical game values. The counting stage is polynomial in \(m\) and in the support sizes of the integer distributions, switch distributions, and reachable sparse-DP states. In practice, that is what makes \(S(8,64)\) feasible: the code counts frequency patterns instead of enumerating astronomical numbers of ordered tuples.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=923
2. Combinatorial game theory: Wikipedia - Combinatorial game theory
3. Disjunctive sum: Wikipedia - Disjunctive sum
4. Surreal number: Wikipedia - Surreal number
5. Dyadic rational: Wikipedia - Dyadic rational