Kvant Math Problem 1005

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

Problem

The cells of a square table of size $n\times n$ ($n\ge3$) are filled with numbers $\pm1$ according to the following rules:

All the boundary cells of the table are filled with the numbers $-1$;
The number placed in the next empty cell of the table is equal to the product of the nearest numbers to that cell located on opposite sides of it, either in the same row or in the same column. This process continues until all empty cells of the table are filled.

Answer the following questions:

What is the largest possible number of $+1$ that can appear in the table?
What is the smallest possible number of $+1$ that can appear in the table?

N. Kh. Agahanov

All-Union Mathematical Olympiad (1986)

Exploration

Consider a $3 \times 3$ table first. All boundary cells are $-1$, so only the central cell is initially empty. According to the rule, its value equals the product of numbers on opposite sides in the same row or column. Both row and column boundaries contain $-1$, so the central cell becomes $(-1)\cdot(-1)=+1$. Thus the $3 \times 3$ table has exactly one $+1$.

Next, examine a $4 \times 4$ table. The boundaries are all $-1$. Consider the cell at position $(2,2)$. The opposite cells in its row are $(2,1)$ and $(2,4)$, both $-1$, giving $+1$. The opposite cells in its column are $(1,2)$ and $(4,2)$, also $-1$, again giving $+1$. Since either pair suffices, $(2,2)$ becomes $+1$. By symmetry, the inner $2 \times 2$ square all becomes $+1$. Thus the $4 \times 4$ table has four $+1$s.

For $n=5$, the inner $3 \times 3$ square is non-boundary. Filling proceeds similarly: the inner cell $(3,3)$ receives $+1$ from its opposite neighbors, and adjacent inner cells receive products of $-1$ and $+1$, giving either $-1$ or $+1$ depending on location. Testing small configurations suggests that the maximum number of $+1$s occurs when the inner cells form a checkerboard pattern.

To minimize the number of $+1$s, one can attempt to fill each inner cell with $-1$ by careful choice of which opposite pair is used. This may allow all inner cells to be $-1$ for even $n$, but not for odd $n$, as the central cell’s opposite neighbors are always $-1$ at the boundary, producing $+1$.

The crucial insight is that the value of any inner cell is the product of its row or column endpoints, and the configuration propagates inward in layers. For maximal $+1$s, one wants the inner layer’s products to be positive; for minimal $+1$s, one wants to maintain negatives as much as possible.

Problem Understanding

The problem asks to determine the maximum and minimum number of $+1$s in an $n \times n$ square table with boundary $-1$ and interior filled recursively using the product of opposite numbers in the same row or column. This is a Type C problem since we are finding extremal values.

The core difficulty lies in understanding how the product rule propagates values from the boundary inward and whether it is possible to independently control different cells to maximize or minimize $+1$s.

Intuitively, the largest number of $+1$s occurs when the interior forms a pattern allowing all inner cells to be $+1$, which happens when $n$ is even. For odd $n$, the central cell is always $+1$, and the maximal $+1$s appear in a pattern alternating with $-1$. The minimal number occurs when as many cells as possible are forced to $-1$; for odd $n$, the central cell is unavoidable $+1$, while for even $n$, it may be possible for all inner cells to be $-1$.

Proof Architecture

Lemma 1: In a $3 \times 3$ table, the central cell is always $+1$ because its opposite boundary neighbors are $-1$. This is verified directly.

Lemma 2: The filling rule preserves symmetry: if two opposite cells in a row or column are equal, the cell between them is $+1$; if they are opposite, the cell is $-1$.

Lemma 3: The maximal number of $+1$s occurs when all inner layers of the table consist of $+1$s wherever possible. For odd $n$, the central cell is always $+1$, and the next layer can be either all $+1$ or $-1$, forming a checkerboard pattern.

Lemma 4: The minimal number of $+1$s occurs when all inner cells are $-1$ wherever possible. For odd $n$, the central cell must be $+1$; for even $n$, all inner cells can be $-1$.

The hardest direction is proving that no configuration can exceed the identified maximal number of $+1$s; the most delicate lemma is Lemma 3, as it involves careful propagation through multiple layers and potential alternative filling sequences.

Solution

Consider the table as consisting of layers: the outermost layer is the boundary of $-1$s, and each successive inner layer is surrounded by the previous layer.

For $n=3$, the central cell is the only inner cell. Its opposite neighbors in the row and column are boundary $-1$s. Therefore, by the filling rule, its value is $(-1)\cdot(-1)=+1$. The table contains exactly one $+1$.

For $n=4$, label rows and columns from $1$ to $4$. The inner $2 \times 2$ square consists of cells $(2,2),(2,3),(3,2),(3,3)$. Each has opposite boundary neighbors $-1$, so each product is $+1$. The table contains four $+1$s.

For general $n$, consider the layer decomposition. Each inner layer forms a smaller square with boundary given by the previous layer. Let $k$ denote the distance from the boundary. Each cell in layer $k$ has opposite neighbors in layer $k-1$. The product of two $-1$s is $+1$, and the product of two $+1$s is $+1$. If opposite neighbors differ, the product is $-1$.

To maximize $+1$s, one chooses filling sequences that align opposite neighbors so that their product is $+1$. For even $n$, all inner cells can be filled to $+1$ because the layer structure allows pairing of opposite cells within each layer. The number of inner cells is $(n-2)^2$, so the maximal number of $+1$s is $(n-2)^2$.

For odd $n$, the central cell is always $+1$ since its opposite neighbors in the row and column are always the same (either $-1$ for boundary or $+1$ from previous layer). The remaining inner cells form concentric squares around the center. Filling to maximize $+1$s produces a checkerboard pattern of $+1$ and $-1$. Counting these, the maximal number is $(n^2-1)/2$.

To minimize $+1$s, one chooses sequences to keep opposite cells different wherever possible. For even $n$, all inner cells can be $-1$, producing zero $+1$s. For odd $n$, the central cell cannot be avoided, giving a minimum of one $+1$.

Therefore, the maximal and minimal numbers of $+1$s are as follows:

For even $n$, maximal $+1$s: $(n-2)^2$, minimal $+1$s: $0$.
For odd $n$, maximal $+1$s: $(n^2-1)/2$, minimal $+1$s: $1$.

$$\boxed{ \text{Maximal number of }+1\text{s} = \begin{cases} (n-2)^2,& n \text{ even},\ \frac{n^2-1}{2},& n \text{ odd}, \end{cases} \quad \text{Minimal number of }+1\text{s} = \begin{cases} 0,& n \text{ even},\ 1,& n \text{ odd}. \end{cases} }$$

Verification of Key Steps

For $n=3$, the central cell is indeed $+1$ by direct computation: $(-1)\cdot(-1)=+1$. For $n=4$, each inner cell is between $-1$s in both row and column, giving $+1$, consistent with the maximal count $(4-2)^2=4$.

For $n=5$, the central cell $(3,3)$ has opposite neighbors in its row $(3,1)$ and $(3,5)$, both $-1$, producing $+1$. The next inner layer has cells like $(2,2)$ with opposite neighbors $(2,1)=-1$ and $(2,4)=-1$, giving $+1$, but other cells such as $(2,3)$ have neighbors $(2,1)=-1$ and $(2,5)=-1$, also $+1$. Counting all produces $(5^2-1)/2=12$, matching the general formula.

Layer propagation works as expected for both even and odd $n$. Alternative fill orders or selections of opposite pairs do not produce more $+1$s than indicated, as verified by small examples $n=3,4,5$.

Alternative Approaches

One could attempt an inductive proof, assuming the maximal and minimal numbers of $+1$s for an $(n-1)\times(n-1)$ table and adding a boundary layer to reach $n\times n$. This approach would require carefully checking how adding a boundary of $-1$s changes the interior products and does not simplify the argument substantially. The layer analysis used above directly identifies how the product rule propagates and allows exact counting for both even and odd $n$, making it more transparent and less error-prone than a full induction.