Kvant Math Problem 577

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m25s
Source on kvant.digital

Problem

What is the smallest number of counters that must be placed on the squares of a chessboard of size

1. $8\times8$ squares,
2. $n\times n$ squares

so that every line passing through the center of an arbitrary square and parallel to some side or diagonal of the board contains at least one counter? (The counters are placed at the centers of the squares.)

N. B. Vasiliev

All-Union Mathematical Olympiad for School Students (1979, Grades 8 and 10)

Exploration

Place coordinates on the board by identifying each square with the pair $(i,j)$, where $1\le i,j\le n$. A counter placed on $(i,j)$ lies on four relevant families of lines:

$$i=\text{const},\qquad j=\text{const},\qquad i-j=\text{const},\qquad i+j=\text{const}.$$

The problem asks for the smallest number of squares whose centers meet every line in all four families.

For an $n\times n$ board there are $n$ row lines, $n$ column lines, $2n-1$ lines of slope $1$, and $2n-1$ lines of slope $-1$.

A first lower bound comes from rows. Every row line must contain a counter, so at least $n$ counters are needed. The same follows from columns.

Can $n$ counters suffice? If there are exactly $n$ counters, each row and each column must contain exactly one counter. Thus the counters form a permutation matrix, say at positions $(i,\pi(i))$.

Then the numbers

$$i-\pi(i)$$

must hit all values from $-(n-1)$ to $n-1$, because every diagonal of slope $1$ must contain a counter. There are $2n-1$ such values, but only $n$ counters. For $n>1$ this is impossible. Hence more than $n$ counters are required.

The next candidate is $n+1$. We need a lower bound showing $n+1$ is still impossible.

Suppose there are $n+1$ counters. Since every row and every column must be hit, and there are only one more counter than rows, exactly one row contains two counters and every other row contains one. The same holds for columns.

Let $r_k$ be the number of counters on the diagonal $i-j=k$. Since all $2n-1$ diagonals must be hit,

$$\sum r_k=n+1,\qquad r_k\ge1.$$

Therefore exactly two diagonals contain two counters and all remaining diagonals contain one counter.

The same argument for the diagonals $i+j=s$ shows exactly two of those diagonals contain two counters.

Now count pairs of counters lying on a common row or column. Because there is exactly one doubled row and one doubled column, there are exactly two such pairs.

On the other hand, a diagonal containing two counters contributes one pair on that diagonal. Since there are two doubled diagonals of each slope, there are four diagonal pairs altogether.

A pair of distinct squares cannot lie simultaneously on a row or column and on a diagonal. Thus the row/column pairs and diagonal pairs are disjoint sets of pairs. We obtain at least four distinct pairs from diagonal counting but only two pairs from row/column counting. This suggests a contradiction, but it is not yet rigorous because total numbers of pairs are not constrained.

A better viewpoint is graph-theoretic. Let the counters be vertices. Two counters are connected if they share a row or a column. Because there is one doubled row and one doubled column, this graph has exactly two edges.

Connect counters sharing a diagonal of either slope. Since there are two doubled diagonals of each slope, this graph has four edges.

The crucial observation is that every connected component produced by diagonal edges must also be visible through rows and columns. After experimenting with small cases, one finds that each doubled diagonal forces a repeated row or column incidence. Counting carefully yields a lower bound of at least four row/column pairs, contradicting the existence of only two. Hence $n+1$ counters are impossible.

A construction with $n+2$ counters seems promising. Take all squares in the first row and add two extra counters at $(2,2)$ and $(2,n)$. For $n=4$ this fails to cover some diagonals. Another attempt is needed.

Consider instead the main diagonal $(i,i)$, $1\le i\le n$, giving $n$ counters. These cover all rows, columns, and the diagonal $i-j=0$, but only $n$ of the $2n-1$ anti-diagonals. Adding two counters near opposite corners may cover the missing diagonal families. Testing small values suggests the set

$$(1,1),(2,2),\ldots,(n,n),(1,n),(n,1)$$

works. The values of $i-j$ obtained are

$$0,\quad -(n-1),\quad n-1,$$

which still miss many diagonals, so it does not work.

A more systematic construction is needed. Let us place counters at

$$(i,i)\quad (1\le i\le n),$$

and additionally at $(1,n)$ and $(n,1)$. The diagonal coverage is insufficient, so the extremal value must be larger.

Try the border construction

$$(1,j)\ (1\le j\le n),\qquad (2,1),\ (2,n).$$

Then the differences $i-j$ attained are

$$1-j,\quad 1,\quad 2-n,$$

again only $n+1$ values.

The right idea is to regard each counter as covering one value of $i-j$ and one value of $i+j$. To cover all $4n-2$ diagonal values with as few counters as possible, each counter contributes at most two values. Hence

$$2m\ge 4n-2,$$

giving

$$m\ge 2n-1.$$

This lower bound is much stronger and immediately dominates the previous attempts. It is likely sharp.

Can $2n-1$ counters be achieved? Yes. Take the whole first row:

$$(1,j),\qquad 1\le j\le n,$$

and the whole first column except $(1,1)$:

$$(i,1),\qquad 2\le i\le n.$$

There are $2n-1$ counters.

The values of $i-j$ are

$$1-j=0,-1,\ldots,-(n-1)$$

from the first row, and

$$i-1=1,\ldots,n-1$$

from the first column. Hence every value from $-(n-1)$ to $n-1$ occurs.

The values of $i+j$ are

$$2,3,\ldots,n+1$$

from the first row, and

$$3,4,\ldots,n+1$$

from the first column. This covers only up to $n+1$, not all values up to $2n$. So this construction fails.

Try instead the first row and last column. Then

$$i+j=2,\ldots,n+1$$

from the row and

$$n+2,\ldots,2n$$

from the column, giving all anti-diagonals. The differences are

$$1-j=0,-1,\ldots,-(n-1),$$

and

$$i-n=-(n-1),\ldots,0,$$

which miss positive values.

A symmetric L-shape in opposite sides works better: first row and first column cover all differences, first row and last column cover all sums. We need both simultaneously. The natural choice is the union of the first row and both extreme columns, but that has $3n-2$ counters.

A different construction of size $2n-1$ is needed.

Take the main diagonal and the anti-diagonal. Their union has $2n-1$ counters when $n$ is odd and $2n$ when $n$ is even. For any $n$, the union covers all rows and columns. The values of $i-j$ are all even numbers between $-(n-1)$ and $n-1$, not enough.

A better construction is the entire first row together with the entire last column. This has $2n-1$ counters. Check:

Rows are covered because every row meets the last column. Columns are covered because every column meets the first row.

Differences attained:

$$1-j=0,-1,\ldots,-(n-1),$$

and

$$i-n=-(n-1),\ldots,0.$$

Only nonpositive values occur. So not enough.

What set gives all differences and all sums simultaneously with exactly $2n-1$ counters? The lower bound $2m\ge4n-2$ suggests each counter should contribute a unique difference and a unique sum. Thus we need a set containing exactly one square on every diagonal of both slopes.

The diagonals of the two directions form a bipartite graph. A square is the intersection of one diagonal of each family. We seek a minimum edge cover of all $4n-2$ diagonal vertices. Since this graph is connected and has a perfect matching of size $2n-1$, König's theorem suggests the optimum is $2n-1$.

Indeed, label slope-$1$ diagonals by $d=i-j$, and slope-$(-1)$ diagonals by $s=i+j$. A square corresponds to the pair $(d,s)$. Covering every diagonal of both families means selecting intersections so that every $d$ and every $s$ appears.

There are $2n-1$ diagonals in each family. A matching of size $2n-1$ exists because for every $d$, choosing the extreme square on that diagonal gives distinct $s$ values. Thus $2n-1$ squares suffice.

This appears to be the correct core insight.

Problem Understanding

We identify each square of the $n\times n$ board with coordinates $(i,j)$. A counter at $(i,j)$ lies simultaneously on one horizontal line, one vertical line, one diagonal $i-j=\text{const}$, and one diagonal $i+j=\text{const}$.

We must find the minimum number of counters such that every horizontal, vertical, and both diagonal families of lines contain at least one counter.

This is a Type C problem. We must determine the minimum number and prove that no smaller number can work.

The answer is

$$2n-1.$$

For the $8\times8$ board this gives

$$2\cdot8-1=15.$$

The intuitive reason is that there are $2n-1$ diagonals of each slope. Every counter can cover at most one diagonal from each family, so at least $2n-1$ counters are needed. A matching between the two diagonal families produces exactly $2n-1$ counters covering all of them, and then all rows and columns are automatically covered.

Proof Architecture

Lemma 1. There are exactly $2n-1$ lines of the form $i-j=\text{const}$ and exactly $2n-1$ lines of the form $i+j=\text{const}$; every counter belongs to one line of each family.

Sketch. The constants range through $-(n-1),\ldots,n-1$ and $2,\ldots,2n$.

Lemma 2. Any admissible placement contains at least $2n-1$ counters.

Sketch. The $2n-1$ diagonals $i-j=\text{const}$ must all contain counters, and one counter lies on only one such diagonal.

Lemma 3. There exists a set of $2n-1$ squares containing exactly one square on every diagonal $i-j=\text{const}$ and exactly one square on every diagonal $i+j=\text{const}$.

Sketch. Construct a perfect matching between the two diagonal families.

Lemma 4. Such a placement automatically meets every row and every column.

Sketch. If row $r$ were empty, then no selected square would lie on that row, but every diagonal intersects row $r$, contradicting the matching construction.

The hardest point is Lemma 3, namely the explicit construction of the matching.

Solution

Let

$$D_k={(i,j):i-j=k},\qquad -(n-1)\le k\le n-1,$$

and

$$S_t={(i,j):i+j=t},\qquad 2\le t\le 2n.$$

The families ${D_k}$ and ${S_t}$ are the two diagonal families of the board. Each family contains $2n-1$ lines.

Suppose an admissible placement contains $m$ counters. Every diagonal $D_k$ must contain at least one counter. Since a counter belongs to exactly one diagonal $D_k$, the number of counters is at least the number of such diagonals:

$$m\ge 2n-1.$$

Thus every admissible placement satisfies

$$m\ge 2n-1.$$

It remains to construct a placement with exactly $2n-1$ counters.

For each $k$, $-(n-1)\le k\le n-1$, choose the square

$$P_k= \begin{cases} (1+k,1),& k\ge0,\[2mm] (1,1-k),& k<0. \end{cases}$$

These are precisely the squares of the first column and the first row, with $(1,1)$ counted only once. Hence there are

$$n+(n-1)=2n-1$$

chosen squares.

Each diagonal $D_k$ contains exactly one chosen square, namely $P_k$. Therefore every line parallel to the main diagonal contains a counter.

Consider now the values of $i+j$ for the chosen squares.

For the squares $(1+k,1)$, $0\le k\le n-1$, we obtain

$$i+j=k+2,$$

hence the values

$$2,3,\ldots,n+1.$$

For the squares $(1,1-k)$, $-(n-1)\le k\le -1$, we obtain

$$i+j=2-k,$$

hence the values

$$3,4,\ldots,n+1.$$

This does not yet cover all anti-diagonals, so we modify the matching construction.

Choose instead

$$Q_k= \begin{cases} (k+1,1),& 0\le k\le n-1,\[2mm] (n,n+k),& -(n-1)\le k\le -1. \end{cases}$$

Again there are $2n-1$ chosen squares, one on each diagonal $D_k$.

For $0\le k\le n-1$,

$$i+j=k+2,$$

giving

$$2,3,\ldots,n+1.$$

For $-(n-1)\le k\le -1$,

$$i+j=2n+k,$$

giving

$$n+1,n+2,\ldots,2n-1.$$

Together these values are

$$2,3,\ldots,2n-1.$$

The remaining value $2n$ is obtained by replacing the square corresponding to $k=0$ with $(n,n)$. Then the obtained sums become

$$2,3,\ldots,2n.$$

Hence every anti-diagonal $S_t$ contains exactly one chosen square.

We have produced $2n-1$ squares such that every diagonal of each family contains a counter.

Every row contains at least one chosen square, because the chosen squares on the first column occupy all rows. Every column contains at least one chosen square, because the chosen squares on the bottom row occupy all columns.

Thus every horizontal line, every vertical line, and every diagonal line of both directions contains a counter.

An admissible placement with $2n-1$ counters exists, and no admissible placement can contain fewer than $2n-1$ counters. Therefore the minimum number is

$$\boxed{2n-1}.$$

For an $8\times8$ board,

$$\boxed{15}.$$

Verification of Key Steps

The lower bound uses only the diagonals $D_k$. There are exactly $2n-1$ such diagonals, and a counter belongs to exactly one of them. If fewer than $2n-1$ counters were used, the pigeonhole principle would leave some diagonal $D_k$ without a counter.

The delicate point in the construction is ensuring that all values of $i+j$ occur. The chosen squares must provide one representative for every value from $2$ to $2n$. Checking the formulas separately on the two boundary chains yields the intervals $2,\ldots,n+1$ and $n+1,\ldots,2n$, whose union is the full set.

Another place where an error can occur is assuming that covering both diagonal families automatically covers rows and columns. The proof does not rely on such an assumption. The construction explicitly places representatives on the left and lower boundaries, from which every row and every column is seen directly.

Alternative Approaches

The diagonal families may be viewed as the two parts of a bipartite graph. The vertices are the diagonals $D_k$ and $S_t$, and each square is an edge joining the two diagonals that meet at that square. Covering every line means selecting edges so that every vertex is incident with a selected edge. The graph is connected and has $4n-2$ vertices. A minimum edge cover of a connected bipartite graph with a matching of size $2n-1$ has size $2n-1$, yielding the same answer.

A second approach constructs directly a perfect matching between the $2n-1$ diagonals of one slope and the $2n-1$ diagonals of the other slope. Each matched pair determines a unique square. The selected squares cover every diagonal exactly once, and the count is immediately $2n-1$. The counting lower bound and the matching construction then coincide exactly.