Detailed mathematical approach

Problem Summary

An ant performs a uniform random walk on a \(5\times5\) grid. Initially the five bottom-row cells each contain one seed, the five top-row cells are empty, and the ant starts at the center \((2,2)\). If the ant is not carrying a seed and reaches a bottom cell that still contains one, it picks it up immediately. If it is carrying a seed and reaches an empty top cell, it drops the seed immediately. We want the expected number of steps until all five seeds have been transported to the top row.

Mathematical Approach

1) What information actually matters?

A naive Markov state would record the ant position together with the exact locations of all five seeds. That is far more detailed than necessary, because seeds only matter when they sit in the bottom row waiting to be picked up, or in the top row after being delivered.

So a state is completely described by:

$B\subseteq\{0,1,2,3,4\}\quad\text{: columns whose bottom seed is still present},$

$T\subseteq\{0,1,2,3,4\}\quad\text{: columns already occupied in the top row},$

the ant position \(p\in\{0,\dots,24\}\), and a carrying flag.

The code stores \(B\) and \(T\) as 5-bit masks. This is already a major reduction: there are only \(25\) possible positions and \(32\) masks per row.

2) The popcount invariant, and how many valid compressed states exist

When the ant is not carrying, every undelivered seed is still sitting at the bottom, and every delivered seed already occupies one top slot. Therefore

$|B|+|T|=5.$

When the ant is carrying, one seed has already been removed from the bottom but has not yet been placed on the top, so

$|B|+|T|=4.$

This gives the exact set of valid compressed states. Their counts are

$25\sum_{t=0}^{5}\binom{5}{t}\binom{5}{5-t}=25\binom{10}{5}=6300$

for non-carrying states, and

$25\sum_{t=0}^{4}\binom{5}{t}\binom{5}{4-t}=25\binom{10}{4}=5250$

for carrying states, for a total of

$6300+5250=11550$

compressed Markov states. The code does not solve one giant \(11550\times11550\) linear system. It uses a better decomposition.

3) The key idea: jump from one meaningful event to the next

Suppose the current state is \((B,T,p,\text{not carrying})\). Then the next meaningful event is:

the first time the random walk hits one of the active bottom cells

$bot(B)=\{b_j:\ j\in B\},$

where \(b_j\) is the bottom cell in column \(j\).

Similarly, in a carrying state \((B,T,p,\text{carrying})\), the next meaningful event is the first time the walk hits one of the still-empty top cells

$top(\overline T)=\{t_j:\ j\notin T\},$

where \(t_j\) is the top cell in column \(j\).

This jump is exact, not heuristic. Let \(\tau\) be that first hitting time. By the strong Markov property of the random walk, once the process reaches the event cell, the future depends only on the new compressed state, not on the detailed path used to get there. So we may split the expectation into:

expected travel time to the next event

plus

expected continuation value from the event state.

4) Hitting-time and first-hit-column data

Fix any target set \(S\) contained in the top row or bottom row. For each start cell \(u\), define

$H_u^{S}=\mathbb E_u[\tau_S],$

where \(\tau_S\) is the first time the walk hits \(S\). Also define, for each target column \(j\),

$P_{u\to j}^{S}=\Pr_u(\text{the first hit in }S\text{ occurs at the target cell in column }j).$

These are determined by first-step decomposition. If \(u\in S\), then the hitting time is already zero. If \(u\notin S\), the first move consumes one step and then averages over neighbors:

$H_u^{S}=\begin{cases} 0,&u\in S,\\ 1+\dfrac1{\deg(u)}\sum_{v\sim u}H_v^{S},&u\notin S. \end{cases}$

Likewise, the first-hit-column probabilities satisfy

$P_{u\to j}^{S}=\begin{cases} 1,&u\text{ is the target cell of column }j,\\ 0,&u\in S\text{ but in a different target column},\\ \dfrac1{\deg(u)}\sum_{v\sim u}P_{v\to j}^{S},&u\notin S. \end{cases}$

The important structural point is that the coefficient matrix is the same for all right-hand sides. So for each mask the code solves one \(25\times25\) system with 6 right-hand sides: one for the expected time and five for the first-hit probabilities of the five columns.

5) Event-level dynamic programming recurrences

Let \(E_{nc}(B,T,p)\) be the expected remaining number of steps from a non-carrying state, and \(E_c(B,T,p)\) the corresponding quantity from a carrying state.

If the ant is not carrying, the next event is the first hit of \(bot(B)\). Therefore

$E_{nc}(B,T,p)=H_p^{bot(B)}+\sum_{j\in B}P_{p\to j}^{bot(B)}\,E_c(B\setminus\{j\},T,b_j).$

The term \(H_p^{bot(B)}\) counts the expected number of ordinary walk steps until pickup. The sum averages over which bottom seed is picked up first. After reaching \(b_j\), the seed is removed from the bottom immediately, so the next state is carrying with bottom mask \(B\setminus\{j\}\).

If the ant is carrying, the next event is the first hit of an empty top slot. Hence

$E_c(B,T,p)=H_p^{top(\overline T)}+\sum_{j\notin T}P_{p\to j}^{top(\overline T)}\,E_{nc}(B,T\cup\{j\},t_j).$

Again, the first term is the expected travel time until drop, and the sum averages over which empty top column is reached first. Once \(t_j\) is reached, that top slot becomes occupied immediately.

6) Why this DP has a clean evaluation order

The carrying recurrence increases \(|T|\) by one:

$E_c(\cdots,T,\cdots)\longrightarrow E_{nc}(\cdots,T\cup\{j\},\cdots).$

The non-carrying recurrence keeps \(|T|\) unchanged:

$E_{nc}(\cdots,T,\cdots)\longrightarrow E_c(\cdots,T,\cdots).$

So if we process states by

$top\_count=|T|$

from \(4\) down to \(0\), then:

carrying states at level \(top\_count\) depend only on non-carrying states at level \(top\_count+1\), which are already known;

non-carrying states at level \(top\_count\) depend only on carrying states at the same level, which have just been computed.

That is why the code has a simple layer-by-layer order and never needs iterative relaxation.

7) Base case and initial state

When all five seeds have already been delivered, we must be in a non-carrying state with

$B=\varnothing,\qquad T=\{0,1,2,3,4\}.$

No further steps are needed, so

$E_{nc}(\varnothing,\text{full},p)=0$

for every position \(p\).

The initial state is

$B=\text{full},\qquad T=0,\qquad p=\text{center},\qquad \text{not carrying},$

so the answer is

$E_{nc}(\text{full},0,\text{center}).$

8) Worked one-seed sanity check

Suppose only one bottom seed remains, in column \(s\), and only one top slot is still empty, in column \(t\). Then there is no branching left.

If the ant is non-carrying at position \(p\), it must first hit \(b_s\), pick up the seed, and then hit \(t_t\). Therefore

$E_{nc}(\{s\},\text{full}\setminus\{t\},p)=H_p^{\{b_s\}}+H_{b_s}^{\{t_t\}}.$

If the ant is already carrying, then only the second part remains:

$E_c(\varnothing,\text{full}\setminus\{t\},p)=H_p^{\{t_t\}}.$

The program checks exactly these identities numerically for every choice of \(s\), \(t\), and \(p\). This is a strong checkpoint because it tests both the hitting systems and the event-level DP.

Code Logic

1) Grid construction. build_grid() stores the neighbors and degrees of the 25 cells.

2) Linear algebra core. solve_hitting_data() builds the common coefficient matrix for a target mask on the top or bottom row. solve_linear_system() performs Gaussian elimination with partial pivoting.

3) Precomputation. For every nonempty mask, the code stores hitting-time and first-hit-column data for top targets and bottom targets separately.

4) DP tables. expected_nc[bottom_mask][top_mask][pos] and expected_c[...] implement the two recurrences above.

5) Layer order. The loop over top_count runs from 4 down to 0. For each layer the carrying table is filled first, then the non-carrying table.

6) Checkpoints. The code verifies two invariants: the hit probabilities for an active target mask always sum to \(1\), and the one-seed formulas above agree with the DP tables.

Complexity Analysis

There are only \(31\) nonempty masks per row that need hitting data. Each one solves a \(25\times25\) linear system with 6 right-hand sides, which is tiny. After that, the dynamic program visits only the valid \((B,T,p)\) states described above. So the computation is exact enough for floating-point arithmetic and dramatically smaller than solving a single giant Markov-chain system on the full state space.

Further Reading

1. Problem page: https://projecteuler.net/problem=280
2. Absorbing Markov chains: https://en.wikipedia.org/wiki/Absorbing_Markov_chain
3. Random-walk hitting times: https://en.wikipedia.org/wiki/Random_walk