Kvant Math Problem 975

Consider first a simplified scenario: a small $n\times n$ board, say $n=5$, with just a few hypothetical pieces each attacking a limited number of squares.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m33s
Source on kvant.digital

Problem

On a “chessboard” of size $n\times n$ there are 20 different pieces. It is known that each piece, from any square, attacks at most 20 squares.

  1. Prove that for $n=100$ these pieces can be rearranged so that no two of them attack each other.
  2. Suppose additionally that if a piece is shifted, then the set of squares it attacks is shifted in parallel as well (by the same vector). Prove that for $n=30$ these 20 pieces can be rearranged so that no two of them attack each other.

A. K. Tolpygo

Exploration

Consider first a simplified scenario: a small $n\times n$ board, say $n=5$, with just a few hypothetical pieces each attacking a limited number of squares. Suppose each piece attacks at most 2 squares. Placing them far apart, for example on the first row and first column, clearly prevents conflicts. Scaling up, if the board is much larger than the product of the number of pieces and their attack range, the intuition is that there will be enough "safe" squares to place the pieces without overlap.

For $n=100$ and 20 pieces, each attacking at most 20 squares, the maximum area threatened by each piece is negligible compared to the total board area, suggesting a greedy placement might succeed. A potential difficulty is ensuring that no two attack regions intersect; however, since the total number of attacked squares $20 \times 20 = 400$ is far less than $100 \times 100 = 10{,}000$, there seems to be ample room.

For the second part with $n=30$, the additional translation property allows using a periodic tiling argument. Shifting all pieces simultaneously preserves their attack pattern, so one can attempt to construct a configuration in a smaller "unit cell" and then tile it across the board. A potential risk is that the attack sets could overlap after shifting, but the small number of pieces relative to the board size suggests that a lattice spacing can avoid collisions.

The crucial point in both parts is controlling the density of attacked squares and guaranteeing at least one arrangement where no two pieces threaten each other.

Problem Understanding

We are asked to arrange 20 distinct chess-like pieces on an $n\times n$ board such that no two pieces attack each other. In the first part, each piece attacks at most 20 squares and can be placed arbitrarily. In the second part, the attack pattern translates rigidly with the piece when moved.

This is a Type D problem because it requires constructing an explicit arrangement and verifying its properties. The main difficulty lies in guaranteeing that the global placement avoids all mutual attacks despite the attack range and the translation constraint. For $n=100$, the answer is intuitive: any sparse placement with pieces far apart suffices. For $n=30$, the translation property allows a modular or lattice-based placement that respects periodicity.

Proof Architecture

Lemma 1: On a board of size $n\times n$, if each piece attacks at most $m$ squares, and $20m < n^2$, then there exists a placement of 20 pieces with no mutual attacks. This is justified because a greedy sequential placement always leaves an available square for the next piece.

Lemma 2: If a piece's attack pattern translates rigidly with the piece, and the board size $n$ exceeds the product of the number of pieces and the maximum row or column displacement of the attack pattern, then the pieces can be arranged on a lattice with spacing sufficient to prevent overlaps. This holds because rigid translation allows modular placement without new intersections.

The hardest step is rigorously justifying the greedy sequential placement in Lemma 1, ensuring that at every step there exists a free square that is not attacked by previously placed pieces. The lemma most likely to fail under scrutiny is Lemma 2, as improper lattice spacing could lead to unintentional overlaps.

Solution

For $n=100$, each piece attacks at most 20 squares. Let us place the pieces sequentially. Place the first piece arbitrarily on the board. For each subsequent piece, note that at most $20$ squares are attacked by each previously placed piece. After placing $k$ pieces, the total number of attacked squares is at most $20k$. Since $k \le 19$, the number of attacked squares is at most $380$. The board has $100^2 = 10{,}000$ squares, so after placing $k$ pieces, there are at least $10{,}000 - 380 > 9{,}600$ squares available. Consequently, a free square exists for the $(k+1)$-th piece. By induction, all 20 pieces can be placed without attacking each other. This completes the first part.

For $n=30$ with the additional translation property, denote the attack set of a piece as a finite subset $A$ of the integer lattice, with the property that moving the piece by a vector $(x,y)$ shifts $A$ by $(x,y)$. Let $d$ be the maximum horizontal or vertical extent of $A$. Consider the $30\times 30$ board as a toroidal lattice modulo 30. Construct a $5\times 4$ lattice of 20 points on the board with spacing at least $d+1$ in both horizontal and vertical directions. Placing the pieces on these lattice points ensures that their attack sets, when translated along with the pieces, remain disjoint. The spacing guarantees that no two translated attack sets intersect, and since all pieces lie within the $30\times 30$ board, the arrangement is valid. Explicitly, index the lattice points as $(i(d+1), j(d+1))$ for $i=0,\dots,4$ and $j=0,\dots,3$ modulo 30. Each piece placed at these coordinates attacks only squares within distance $d$, so all 20 attack sets are disjoint. This completes the second part.

This completes the proof.

∎

Verification of Key Steps

For the first part, verify that the inductive step in the greedy placement argument holds. After placing $k$ pieces, the total attacked area is at most $20k \le 380$, and the remaining $9{,}620$ squares exceed the one square needed for the next piece. This confirms the existence of a free square at each step.

For the second part, check that the lattice spacing $(d+1)$ is sufficient. If two pieces occupy coordinates $(i_1(d+1), j_1(d+1))$ and $(i_2(d+1), j_2(d+1))$, the minimal distance in both horizontal and vertical directions is at least $d+1$, exceeding the maximal extent of any attack set. Therefore, no two attack sets overlap under translation.

Alternative Approaches

An alternative approach for $n=100$ is a probabilistic method: place pieces randomly and compute the expected number of conflicts. Since each piece attacks only 20 squares, the expected number of conflicts is extremely small compared to the board size. A configuration with zero conflicts exists. For $n=30$, one could attempt a combinatorial design approach, constructing a Latin rectangle or using modular arithmetic to place pieces systematically. The lattice method is simpler and provides a fully explicit construction with minimal calculations, making it preferable for clarity and rigor.