Conjectural formula for optimal solutions with k-1 clean columns

Let $\alpha_{n,m}$ denote the number of optimal solutions for the $n\times m$ grid in the paper's notation. In the case of a grid with $2$ rows and $2k+1$ columns, where $k\geq 0$ , the clean-column counting conjecture. For all integers $k\geq 0$ ,

\alpha_{2,2k+1}=(k+1)(3k+2)\,2^{k-1}.

The formula is proposed because the authors' counting argument for solutions with exactly $k-1$ clean columns is incomplete, and they identify the resulting values with the OEIS sequence A084857. The status of this enumeration remains open in the supplied text.

References

Primary source

El-Mehdi Mehiri and Mohammed L. Nadji, “The Power Contamination Problem on Grids Revisited: Optimality, Combinatorics, and Links to Integer Sequences”, arXiv:2509.12756 (2026).

enumerative-combinatorics grid-graphs

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

The formula remains unverified: the 2025 paper left its key count open, while a reader has posted a complete proof that has not been independently checked.

The conjecture proposes $\alpha_{2,2k+1}=(k+1)(3k+2)2^{k-1}$ for odd two-row grids. Mehiri and Nadji (2025) identify the formula with OEIS A084857 but state that the enumeration for exactly $k-1$ clean columns remains unresolved.

Known results

The contribution from solutions with exactly $k$ clean columns is $(k+1)2^k$ .
Conditional on the conjecture, the unresolved contribution is $\beta_k=3k(k+1)2^{k-1}$ .
The primary paper proves the exact contamination number for grid graphs, but not this enumeration.

Posted attempt

A posted argument claims a complete proof by characterizing successful two-row configurations and counting the cases with and without a full column. The argument has not been independently verified and conflicts with the primary paper’s statement that this count is open.

Current status (as of August 2026): The formula is open in the primary source, but a complete-proof claim has been posted and remains unverified.

Sources

arxiv.org

ProofThis solution needs a summarySee full solutionHide full solution

On a two-row grid the applicable contamination rules are precisely the threshold-two rule on the ladder: an uncontaminated vertex becomes contaminated when at least two horizontal or vertical neighbors are contaminated. Encode initial column states by $0,T,B,F$ (empty, top only, bottom only, full).

A configuration fully contaminates the ladder if and only if (i) its first and last columns are nonempty; (ii) no two consecutive columns are empty; and (iii) there is an $F$ column or an adjacent $TB$ or $BT$ pair. Necessity of (i)–(ii) follows because an empty boundary column or two consecutive empty columns never receive their first contamination. If (iii) fails, the only possible new contamination fills an empty column situated between two same-row singleton columns; it produces another singleton in that same row, preserving the absence of full columns and opposite-row adjacent singletons. Thus full contamination is impossible. Conversely, an $F$ column is already full, while an adjacent $TB$ or $BT$ pair immediately creates a full column. A full column absorbs an adjacent nonempty column. It also crosses a single empty column followed by a nonempty column: infect the intermediate vertex in the farther occupied row using its two horizontal neighbors, then infect the other intermediate vertex using its vertical neighbor and the original full column. Conditions (i)–(ii) propagate this to both boundaries.

For $m=2k+1$ , $k\ge1$ , a minimum contamination set has $k+2$ vertices. If one column is full, there are $k$ singleton and $k$ empty columns. Conditions (i)–(ii) force the unique alternating occupied/empty pattern. Choose the full column in $k+1$ ways and assign the remaining $k$ singleton rows freely, giving $(k+1)2^k$ configurations.

Otherwise all $k+2$ occupied columns are singletons and the $k-1$ empty columns are nonadjacent interior positions. Their patterns number $\binom{k+1}{2}$ . Each such pattern has $k$ runs of occupied columns, so its singleton adjacency graph has $(k+2)-k=2$ edges. Since these two edges form a forest, exactly $2^k$ of the $2^{k+2}$ top/bottom assignments are constant along both edges. Condition (iii) accepts the other $2^{k+2}-2^k=3\cdot2^k$ assignments. Hence the number with $k-1$ clean columns is

\beta_k=\binom{k+1}{2}\cdot3\cdot2^k =3k(k+1)2^{k-1}.

Therefore

\alpha_{2,2k+1} =(k+1)2^k+3k(k+1)2^{k-1} =(k+1)(3k+2)2^{k-1}.

For $k=0$ , the one-column ladder has exactly one minimum contamination set, also agreeing with the same formula.