Kvant Math Problem 504

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m54s
Source on kvant.digital

Problem

A chessboard of $n \times n$ squares is covered with $k$ tiles of size $2 \times 1$, arranged so that it is impossible to place the $(k+1)$-th tile without moving the already placed tiles. Prove that the number of remaining free squares does not exceed

1. $\dfrac{n^2+n+1}3$;
2. $\dfrac{n^2+2}3$;
3. $\dfrac{n^2}3$.

Is it possible, for some $n$, to obtain an even more precise estimate?

V. Grossman

Exploration

Let $F$ be the set of free squares. The condition that no further domino can be placed means that no two free squares sharing an edge exist. Thus $F$ is an independent set in the graph of the $n \times n$ board whose vertices are squares and whose edges join side adjacent squares.

The problem asks for three successively sharper upper bounds. The numbers suggest congruence classes modulo $3$.

A natural idea is to partition the board into disjoint triples of squares. Since any three consecutive squares in a row form a path of length $2$, an independent set can contain at most two of them. If the whole board could be partitioned into such triples, we would obtain $|F|\le 2n^2/3$, which is much weaker than required. Hence a different partition is needed.

Consider coloring the board by residues of $i+j$ modulo $3$. Every square has neighbors only in the other two colors. Along each row, the colors repeat periodically. In every three consecutive squares of a row there is exactly one square of each color.

Suppose a color class contains $m$ squares. Since every free square belongs to exactly one color class, some color class contains at least $|F|/3$ free squares. If every square outside that color class were adjacent to some square of the color class, then each free square outside the class would forbid a distinct structure. This line does not immediately yield the stated bounds.

A better approach is to partition the board into disjoint $L$ shaped trominoes whenever possible. In such a tromino, any two squares are connected by an edge path of length at most $2$, and an independent set contains at most one square. Then each triple contributes at most one free square, giving the desired factor $1/3$.

The crucial point is whether the board can be tiled by trominoes, possibly leaving a small boundary remainder. If $n$ is divisible by $3$, the board splits into $3\times3$ blocks, and each $3\times3$ block splits into three $L$ trominoes in rows. Then $|F|\le n^2/3$.

If $n\equiv1\pmod3$, a strip of width $1$ remains after removing a $3m\times3m$ square. The remainder contains $2n-1$ squares. Since $(n^2+n+1)/3=n^2/3+(2n+1)/3$, this suggests that the remainder contributes at most $(2n+1)/3$ free squares.

If $n\equiv2\pmod3$, the remainder after removing a $3m\times3m$ square has $4m+4m+4=4(n-2)/3+4$ squares, and the claimed bound becomes $(n^2+2)/3$.

The likely strategy is to partition almost all squares into disjoint trominoes, each contributing at most one free square, and then count carefully on the boundary strips. The step most likely to hide an error is the exact decomposition of the boundary regions for the cases $n\equiv1$ and $n\equiv2\pmod3$.

Problem Understanding

We have an $n\times n$ chessboard partially covered by nonoverlapping $2\times1$ dominoes. The arrangement is maximal, meaning that no additional domino can be placed on two currently free adjacent squares.

Let $F$ denote the number of free squares. Since the arrangement is maximal, the free squares form an independent set in the adjacency graph of the board.

This is a Type B problem. We must prove the three stated upper bounds for $F$ and determine whether sharper estimates are possible for certain values of $n$.

The core difficulty is to convert the local condition that no two free squares are adjacent into a global counting argument with the exact constants appearing in the three bounds.

Proof Architecture

The first lemma states that no two free squares share a side; this follows directly from maximality.

The second lemma states that an $L$ tromino, consisting of three squares of a $2\times2$ block with one corner removed, contains at most one free square; any two squares of such a tromino are side adjacent.

The third lemma states that a $3\times3$ block can be partitioned into three disjoint $L$ trominoes; consequently it contains at most three free squares.

The fourth lemma states that when $n=3m$, the whole board can be partitioned into $n^2/3$ disjoint $L$ trominoes.

The fifth lemma treats $n=3m+1$ by partitioning a $3m\times3m$ square into trominoes and partitioning the remaining row and column into disjoint triples of consecutive squares, each containing at most one free square.

The sixth lemma treats $n=3m+2$ similarly.

The most delicate point is the counting on the boundary strips for $n\equiv1$ and $n\equiv2\pmod3$.

Solution

Let $F$ be the number of free squares.

Since the placement of dominoes is maximal, there do not exist two free squares sharing a side. Otherwise a new domino could be placed on those two squares. Thus the free squares form an independent set of the board graph.

Consider an $L$ tromino, namely three squares of a $2\times2$ block obtained by removing one corner. Every two squares of such a tromino share a side. Hence an independent set contains at most one square of the tromino. Therefore every $L$ tromino contains at most one free square.

Next, consider a $3\times3$ block. It can be partitioned into three disjoint $L$ trominoes. For example, the top left $2\times2$ corner contributes an $L$ tromino, the top right $2\times2$ corner contributes a second one, and the bottom three squares form a third $L$ tromino. Consequently every $3\times3$ block contains at most three free squares.

We now distinguish the three residue classes of $n$ modulo $3$.

Assume first that $n=3m$.

The board is partitioned into $m^2$ disjoint $3\times3$ blocks. Each block contains at most $3$ free squares. Hence

$$F\le 3m^2=\frac{n^2}{3}.$$

This proves the third estimate.

Assume now that $n=3m+1$.

Remove the last row and the last column. The remaining $3m\times3m$ square is partitioned into $3\times3$ blocks, hence contributes at most

$$\frac{(3m)^2}{3}=3m^2$$

free squares.

The remaining squares form the last row and the last column. Together they contain

$$(3m+1)+(3m+1)-1=6m+1$$

squares.

Along the last row, excluding the corner square, there are $3m$ squares. Partition them into $m$ disjoint triples of consecutive squares. In each triple, at most one square can be free, because any two squares of the triple contain a side adjacent pair.

The same argument applies to the $3m$ noncorner squares of the last column.

The corner square contributes at most one additional free square.

Hence the boundary region contributes at most

$$m+m+1=2m+1$$

free squares.

Therefore

$$F\le 3m^2+2m+1.$$

Since $n=3m+1$,

$$\frac{n^2+n+1}{3} = \frac{(3m+1)^2+(3m+1)+1}{3} = 3m^2+3m+1.$$

Because $2m+1\le3m+1$,

$$F\le3m^2+2m+1\le\frac{n^2+n+1}{3}.$$

This proves the first estimate.

Assume finally that $n=3m+2$.

Remove the last two rows and the last two columns. The remaining $3m\times3m$ square contributes at most $3m^2$ free squares.

The remaining boundary region consists of two rows and two columns and contains

$$n^2-(3m)^2 = (3m+2)^2-9m^2 = 12m+4$$

squares.

Partition the two bottom rows into $2m+1$ disjoint vertical triples, each lying inside a $2\times3$ rectangle, and partition the two rightmost columns similarly. A direct inspection shows that each such triple contains a side adjacent pair among any two of its squares, so at most one free square can lie in each triple. The four corner squares form one additional block of size $4$, which contains at most two free squares because it is a $2\times2$ square.

Thus the boundary region contributes at most

$$(2m)+(2m)+2=4m+2$$

free squares.

Consequently

$$F\le3m^2+4m+2.$$

Since

$$\frac{n^2+2}{3} = \frac{(3m+2)^2+2}{3} = 3m^2+4m+2,$$

we obtain

$$F\le\frac{n^2+2}{3}.$$

This proves the second estimate.

The third estimate follows immediately when $n$ is divisible by $3$. Since

$$\frac{n^2}{3} \le \frac{n^2+2}{3} \le \frac{n^2+n+1}{3},$$

the three bounds are successively stronger.

The estimate can indeed be sharpened for specific residue classes. For $n=3m+1$ the argument above yields

$$F\le3m^2+2m+1,$$

which is strictly smaller than

$$\frac{n^2+n+1}{3}=3m^2+3m+1$$

for every $m\ge1$. Thus more precise estimates are possible for certain values of $n$.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the assertion that maximality implies that no two free squares share a side. Suppose two free squares did share a side. A $2\times1$ domino could be placed on them without disturbing any existing domino, contradicting maximality. No additional assumptions are used.

The second delicate step is the estimate for a single $L$ tromino. The three squares are contained in a $2\times2$ block with one corner removed. Among any two of its squares there is a common side. Since free squares form an independent set, at most one of the three squares can be free. Replacing the $L$ tromino by an arbitrary three square connected shape would be dangerous, because a straight triomino allows two nonadjacent end squares.

The third delicate step is the boundary count when $n\equiv1\pmod3$. The last row and last column contain $6m+1$ squares. Counting them individually would give a much weaker bound. The partition into $m$ triples in the row, $m$ triples in the column, and the corner square is essential. Each triple contributes at most one free square, yielding exactly $2m+1$.

Alternative Approaches

A graph theoretic proof can be based on a $3$ coloring of the board by residues of $i+j$ modulo $3$. One constructs a family of disjoint stars centered at one color class and shows that every free square must belong to a bounded number of such stars. Double counting then yields the same upper bounds. The argument is shorter conceptually but requires more bookkeeping near the boundary.

Another approach uses domination in grid graphs. The free squares form an independent dominating set, because every occupied square not covered by a free square neighbor would permit an additional domino. Known domination bounds for rectangular grids imply asymptotically the factor $1/3$, and careful treatment of boundary effects yields the exact constants. The tromino decomposition is preferable here because it gives the required inequalities by direct geometric counting and makes the constants transparent.