Conjectural formula for optimal solutions with k-1 clean columns

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.