While playing chess Parcly and Tori Taxel, best friends and genies, got bored and transformed all the pieces into pawns to make pretty patterns. They found this 22-pawn arrangement where every 3×3 submatrix (not necessarily contiguous) has at least one pawn.
"But," Tori asked Parcly. "What if I remove one pawn?"
Is it possible to arrange 21 pawns so that every 3×3 submatrix is non-empty?
This puzzle was inspired by an MSE question.
You can solve this set covering problem via integer linear programming as follows. Let binary decision variable $x_{i,j}$ indicate whether cell $(i,j)$ contains a pawn. The problem is to minimize $\sum_{i=1}^8 \sum_{j=1}^8 x_{i,j}$ subject to linear constraints $$\sum_{i\in\{i_1,i_2,i_3\}} \sum_{j\in\{j_1,j_2,j_3\}} x_{i,j} \ge 1 \quad \text{for $1\le i_1<i_2<i_3 \le 8$ and $1\le j_1<j_2<j_3 \le 8$}$$ The minimum turns out to be
$22$.
It is
not possible.
(Ugly) proof:
Assume to reach a contradiction it were possible. Let WLOG ranks 1 and 2 be the two ranks with the smallest number of pawns in them. It is easily verified that the combined number is 4 or less. In other words k>=4 files (WLOG the first k files) have no pawns in the first two ranks. To preclude all 3x3 submatrices in the first k files each of rows 3-8 must have at least k-2 pawns in the first k files. If k>5 that's impossible. If k=5 it's all the pawns left and there would be no pawn at all in ranks 3-8 x files f-h, contradiction. So k must be 4, leaving 5 pawns to cover the 6-by-4 rectangle 3-8 x e-h. If 3 of its ranks are empty we are done. If two, one of the others can only have one pawn and we are done. Therefore there can only be one empty rank (WLOG rank 3) and 5 ranks with exactly one pawn. By pigeon hole principle two of these pawns are on the same file WLOG e4 and e5. But that leaves 3-5 x f-h uncovered. Contradiction.
