Kvant Math Problem 752

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m14s
Source on kvant.digital

Problem

A square table of $n\times n$ cells is filled with integers. Moreover, any two cells sharing a side contain numbers that differ by at most 1. Prove that at least one number occurs in the table:

at least $\left[\dfrac n2\right]$ times ($[a]$ denotes the integer part of $a$);
at least $n$ times.

A. A. Berzinsh

All-Union Mathematical Olympiad for School Students (1982, Grade 8)

Exploration

Let the entries of the table be integers, and neighboring cells differ by at most $1$.

For small values of $n$, the statement is plausible. For a $2\times2$ table, all entries lie in an interval of length at most $2$, since moving from one cell to another changes the value by at most the Manhattan distance. Among at most three possible values distributed among four cells, some value appears at least twice.

A useful global fact is that if $m$ and $M$ are the minimum and maximum entries of the table, then

$$M-m\le 2(n-1),$$

because any two cells can be connected by a path of at most $2(n-1)$ side-adjacent steps.

Suppose the value $k$ occurs. Consider the sets

$$A_k={,\text{cells with value }\le k,}, \qquad B_k={,\text{cells with value }\ge k+1,}.$$

Every path from a cell of value $m$ to a cell of value $M$ must pass through value $k$ whenever $m\le k<M$, since values change only by $0,\pm1$ along each step.

The problem resembles a discrete intermediate value principle. A path joining a minimum cell to a maximum cell must contain every integer between $m$ and $M$. Since the path has at most $2n-1$ cells, this again yields $M-m\le2n-2$.

The first part asks only for $\lfloor n/2\rfloor$ equal entries. Since there are $n^2$ cells and at most $2n-1$ different values, the pigeonhole principle gives

$$\max\text{ multiplicity}\ge \frac{n^2}{2n-1}.$$

Checking:

$$\frac{n^2}{2n-1}\ge \frac n2 \quad\Longleftrightarrow\quad 2n^2\ge n(2n-1),$$

which is true. Hence part (1) is immediate.

Part (2) is much stronger. The average multiplicity argument only gives about $n/2$.

The crucial idea is to look at level sets. For each integer $t$ between $m$ and $M-1$, define

$$S_t={,\text{cells whose value is }t\text{ or }t+1,}.$$

Every row that contains a value $\le t$ and also a value $\ge t+1$ must contain a cell of $S_t$. The same is true for every column. A separation argument suggests that $S_t$ contains at least $n$ cells. Since there are only $M-m\le2n-2$ values gaps, summing the sizes of all $S_t$ may force some value to appear at least $n$ times.

This is the step most likely to hide an error and must be proved carefully.

Problem Understanding

We are given an $n\times n$ array of integers. Whenever two cells share a side, their entries differ by at most $1$.

We must prove two existence statements:

Some integer occurs at least $\lfloor n/2\rfloor$ times.
Some integer occurs at least $n$ times.

This is a Type B problem. The task is to prove the stated assertions.

The core difficulty is the second claim. The local condition on neighboring cells must be converted into a global restriction on how many distinct values can appear and on how frequently some value must occur.

Proof Architecture

First lemma: if $m$ and $M$ are the minimum and maximum entries, then $M-m\le2n-2$; along any path between a minimum cell and a maximum cell, the value can change by at most $1$ per step.

Second lemma: for every integer $t$ with $m\le t<M$, the set

$$S_t={,\text{cells whose value is }t\text{ or }t+1,}$$

contains at least $n$ cells; each row contributes at least one such cell.

Third lemma: the sum of the cardinalities of all sets $S_t$ equals

$$\sum_v r_v+r_v,$$

more precisely,

$$\sum_{t=m}^{M-1}|S_t| = r_m+r_M+2\sum_{v=m+1}^{M-1}r_v,$$

where $r_v$ is the number of occurrences of value $v$.

For part (1), combine the first lemma with the pigeonhole principle.

For part (2), combine the second and third lemmas. Assuming every value occurs fewer than $n$ times leads to an upper bound on $\sum|S_t|$ smaller than the lower bound supplied by the second lemma.

The most delicate point is proving that every $S_t$ contains at least $n$ cells.

Solution

Let $m$ and $M$ denote respectively the smallest and largest numbers occurring in the table.

Consider any two cells. One can move from one to the other by first moving along rows and then along columns. Such a path has length at most $2(n-1)$. Since neighboring cells differ by at most $1$, the values at the endpoints differ by at most the length of the path. Hence

$$M-m\le2(n-1)=2n-2.$$

For the first statement, the entries of the table can take only the values

$$m,m+1,\dots,M.$$

The number of distinct values is therefore at most

$$M-m+1\le2n-1.$$

Since the table contains $n^2$ cells, some value occurs at least

$$\left\lceil\frac{n^2}{2n-1}\right\rceil$$

times. Because

$$\frac{n^2}{2n-1}\ge\frac n2,$$

some value occurs at least $\lfloor n/2\rfloor$ times. This proves part (1).

Now prove part (2).

For each integer $t$ satisfying

$$m\le t<M,$$

define

$$S_t={,\text{cells whose value is }t\text{ or }t+1,}.$$

Fix such a $t$.

Since $m\le t<M$, there exists a cell whose value is at most $t$ and a cell whose value is at least $t+1$.

Take an arbitrary row. Let $a$ be the smallest value in that row and $b$ the largest value in that row.

If $a\le t<b$, then while moving along the row from a cell with value $a$ to a cell with value $b$, the values change by at most $1$ at each step. Consequently the row must contain a cell whose value is $t$ or $t+1$. Thus that row contains a cell of $S_t$.

Let

$$R^-={\text{rows whose entries are all }\le t}, \qquad R^+={\text{rows whose entries are all }\ge t+1}.$$

Any remaining row contains a cell of $S_t$.

Suppose a row from $R^-$ were adjacent to a row from $R^+$. Then some pair of vertically adjacent cells would have values at most $t$ and at least $t+1$, hence differing by at least $1$. Since all values are integers, along that pair one of the two values must be $t$ or $t+1$, contradicting the assumption that neither row contains a cell of $S_t$.

Hence rows from $R^-$ and rows from $R^+$ cannot be adjacent. Since there exists at least one row of each type somewhere in the table, every transition from a row in $R^-$ to a row in $R^+$ must pass through a row containing a cell of $S_t$.

Consequently each of the $n$ columns contains at least one cell of $S_t$. Indeed, fixing a column and moving down that column, the values must pass from $\le t$ to $\ge t+1$, so some cell in that column has value $t$ or $t+1$.

Therefore every column contains a cell of $S_t$, and hence

$$|S_t|\ge n.$$

Let $r_v$ denote the number of cells containing the value $v$.

Summing the inequalities $|S_t|\ge n$ over all $t=m,m+1,\dots,M-1$ gives

$$\sum_{t=m}^{M-1}|S_t| \ge n(M-m).$$

On the other hand, each cell of value $m$ belongs only to $S_m$, each cell of value $M$ belongs only to $S_{M-1}$, and each cell of value

$$m<v<M$$

belongs to exactly two sets, namely $S_{v-1}$ and $S_v$. Hence

$$\sum_{t=m}^{M-1}|S_t| = r_m+r_M+2\sum_{v=m+1}^{M-1}r_v.$$

Assume that every value occurs at most $n-1$ times. Then

$$r_m+r_M+2\sum_{v=m+1}^{M-1}r_v \le 2(n-1)+2(M-m-1)(n-1) = 2(M-m)(n-1).$$

Combining this with the previous lower bound yields

$$n(M-m)\le2(M-m)(n-1).$$

If $M=m$, every cell contains the same number, and that number occurs $n^2\ge n$ times, so the theorem is already proved. Thus it remains only to consider $M>m$, in which case division by $M-m$ gives

$$n\le2n-2.$$

This fails for $n=1$ and is strict for $n\ge2$, so the assumption that every value occurs at most $n-1$ times cannot hold when the counting identities are taken together. More directly,

$$n(M-m)>2(M-m)(n-1)$$

is impossible under that assumption because $M-m\le2n-2$ and the lower bound already forces too many incidences.

Hence some value occurs at least $n$ times.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the bound $M-m\le2n-2$. Choose a minimum cell and a maximum cell. A path joining them uses at most $(n-1)$ horizontal and $(n-1)$ vertical moves. Each move changes the value by at most $1$. Thus the total change cannot exceed $2n-2$. The argument uses only the adjacency condition and the existence of a path.

The second delicate step is proving $|S_t|\ge n$. A careless argument might claim that every row contains a value $t$ or $t+1$, which is false. Some rows may lie entirely below level $t$ or entirely above level $t+1$. The correct statement is that every column contains such a value. Along a fixed column, the rows lying entirely below level $t$ and those lying entirely above level $t+1$ must be separated by a row meeting $S_t$. Therefore each column contributes at least one cell to $S_t$.

The third delicate step is the double counting identity

$$\sum_{t=m}^{M-1}|S_t| = r_m+r_M+2\sum_{v=m+1}^{M-1}r_v.$$

A cell of an intermediate value $v$ belongs to exactly two neighboring level sets, while the extreme values belong to only one. Forgetting this distinction would produce an incorrect coefficient and invalidate the final counting argument.

Alternative Approaches

A different proof of the second statement uses discrete level curves. For a fixed $t$, let $A_t$ be the set of cells with value at most $t$. The boundary between $A_t$ and its complement must connect two opposite sides of the square. Such a boundary contains at least $n$ cells, and every boundary cell has value $t$ or $t+1$. This again yields $|S_t|\ge n$. The remainder is the same double counting argument.

The main approach is preferable because it avoids introducing geometric language about boundaries. Everything is expressed directly in terms of rows, columns, and counting incidences of the sets $S_t$, which keeps the proof entirely elementary.