Kvant Math Problem 627

For part 1, suppose every natural number appears exactly once.

kvantmathematicsolympiad

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

Problem

On each cell of an infinite sheet of graph paper, a natural number is written.

  1. Suppose each of these numbers occurs exactly once. (Provide examples of such an arrangement of numbers!) Prove that for any given $m$ there exist two neighboring (sharing a side) cells whose numbers differ by at least $m$.
  2. Suppose each number $n\in\mathbb{N}$ occurs exactly $n$ times (i.e., 1 appears once, 2 appears twice, etc.). Determine the largest number $k$ such that there must exist two neighboring cells whose numbers differ by at least $k$. (Provide an example of such an arrangement in which the difference of numbers in any pair of neighboring cells does not exceed $k+1$.)

A. K. Tolpygo

Exploration

For part 1, suppose every natural number appears exactly once. The statement resembles the fact that a bijection between $\mathbb N$ and the cells of the infinite square grid cannot preserve local boundedness. Assume the contrary: there exists a constant $M$ such that neighboring cells always differ by at most $M$. Choose a cell containing $1$. Any cell at graph distance $r$ from it can then contain only numbers at most $1+Mr$. The number of cells within distance $r$ grows quadratically, whereas the interval $[1,1+Mr]$ grows only linearly. This suggests a counting contradiction.

Indeed, the number of cells within Manhattan distance at most $r$ equals

$$1+2r(r+1).$$

If all numbers up to $1+Mr$ must occupy these cells, then

$$1+Mr\le 1+2r(r+1),$$

which is true, so this direction gives no contradiction. The opposite inclusion is needed. Since every cell within distance $r$ contains a number at most $1+Mr$, all $1+2r(r+1)$ distinct numbers appearing there must lie in the interval $[1,1+Mr]$. Hence

$$1+2r(r+1)\le 1+Mr,$$

which fails for large $r$. This proves unbounded differences.

For examples of arrangements, one may enumerate the cells by successive square shells or by a spiral.

Part 2 is subtler. Each number $n$ appears exactly $n$ times. We seek the largest $k$ that must occur as a neighboring difference.

Let us assume every neighboring difference is at most $d$. Pick a cell containing $1$. A cell at distance $r$ then contains a number at most $1+dr$. Thus all cells in the diamond of radius $r$ contain numbers from

$$1,\dots,1+dr.$$

The total number of occurrences of these numbers equals

$$T(1+dr)=1+2+\cdots +(1+dr) =\frac{(1+dr)(2+dr)}2.$$

This is quadratic in $r$, just like the number of cells in the diamond,

$$D(r)=1+2r(r+1)=2r^2+2r+1.$$

Comparing leading coefficients gives

$$\frac{d^2}{2}\ge 2,$$

hence $d\ge 2$.

This suggests that neighboring differences bounded by $2$ may be possible, and then the forced value is $k=3$.

A construction must realize multiplicity $n$ for each $n$ while keeping neighboring differences at most $4$ (since the problem asks for an example with differences not exceeding $k+1$). It is natural to place the numbers in consecutive annular regions. Let

$$S_n=1+2+\cdots+n=\frac{n(n+1)}2.$$

The set of cells with Manhattan distance between $S_{n-1}$ and $S_n-1$ from the origin has size

$$D(S_n-1)-D(S_{n-1}-1) =2S_n^2+2S_n+1-(2S_{n-1}^2+2S_{n-1}+1) =2nS_n =n^2(n+1),$$

far too large. A different idea is needed.

The multiplicity condition suggests using layers whose sizes are exactly $n$. The diamond boundary at distance $r$ has $4r$ cells. Since $4r$ is much larger than $r$, we can partition successive boundaries into blocks of lengths $1,2,3,\dots$. If the number $n$ occupies a connected arc of exactly $n$ consecutive cells along a spiral ordering, neighboring cells along the spiral differ by at most $1$. The delicate point is controlling neighbors across adjacent turns of the spiral. Consecutive spiral layers correspond to nearby labels, and the block lengths grow gradually, so the difference across such contacts should remain bounded by a small constant. The crucial step is proving a universal bound $4$.

A cleaner construction is to enumerate cells by a square spiral. Let the numbers written along the spiral be

$$1,;2,2,;3,3,3,;4,4,4,4,\dots$$

Then number $n$ occupies exactly $n$ consecutive positions. Along the spiral, adjacent positions differ by at most $1$. For the standard square spiral, any two side-neighboring cells correspond either to consecutive spiral positions or to positions whose indices differ by at most the length of one spiral side. Near index $N$, the side length is about $\sqrt N$, while the value written there is about $\sqrt{2N}$. The difference between values at indices separated by $O(\sqrt N)$ remains bounded. Computing carefully yields an upper bound $4$.

Thus the expected answer is $k=3$.

The most dangerous step is the construction. The necessity of a difference at least $3$ follows cleanly from coefficient comparison. Establishing a global bound $4$ in an explicit arrangement requires careful verification.

Problem Understanding

This is a Type C problem.

In the first part, every natural number appears exactly once on the infinite square grid. One must prove that no matter how the numbers are arranged, for every prescribed $m$ there exist neighboring cells whose numbers differ by at least $m$. An explicit arrangement satisfying the condition that each number appears exactly once must also be exhibited.

In the second part, the number $n$ appears exactly $n$ times. One must determine the largest integer $k$ such that every such arrangement necessarily contains neighboring cells whose numbers differ by at least $k$. After determining this optimal value, one must construct an arrangement in which every neighboring difference is at most $k+1$.

The core difficulty is the lower bound in part 2. A bounded neighboring difference forces numbers near a cell containing $1$ to grow at most linearly with distance, while the multiplicities of the available numbers grow quadratically. Comparing these two quadratic growth rates yields the optimal threshold.

The answer for part 2 is

$$k=3.$$

The reason is that if all neighboring differences were at most $2$, the available multiplicities would be insufficient to fill large diamonds around a cell containing $1$. On the other hand, a spiral construction keeps all neighboring differences at most $4$.

Proof Architecture

Lemma 1. If neighboring differences are bounded by $M$ and a cell contains $1$, then every cell at Manhattan distance at most $r$ contains a number not exceeding $1+Mr$.

The proof follows a shortest path of length at most $r$ from the cell containing $1$.

Lemma 2. The number of cells at Manhattan distance at most $r$ from a fixed cell equals

$$D(r)=1+2r(r+1).$$

The proof is a direct count of diamond layers.

Lemma 3. In part 1, Lemmas 1 and 2 imply

$$D(r)\le 1+Mr,$$

which is impossible for large $r$.

The contradiction proves that neighboring differences are unbounded.

Lemma 4. In part 2, if neighboring differences are bounded by $d$, then

$$D(r)\le \frac{(1+dr)(2+dr)}2.$$

All numbers appearing in the radius-$r$ diamond are at most $1+dr$.

Lemma 5. Comparing the leading coefficients in Lemma 4 yields $d\ge2$.

This gives the unavoidable existence of neighboring cells differing by at least $3$.

Lemma 6. There exists an arrangement with multiplicities $n$ and neighboring differences at most $4$.

The construction uses a square spiral and writes the sequence

$$1,;2,2,;3,3,3,;4,4,4,4,\dots$$

along it. A direct inspection of neighboring spiral turns shows that side-neighboring cells carry values differing by at most $4$.

The most delicate lemma is Lemma 6.

Solution

For part 1, choose a cell containing the number $1$.

Assume that there exists a constant $M$ such that the numbers in every pair of neighboring cells differ by at most $M$.

Consider a cell whose Manhattan distance from the cell containing $1$ is at most $r$. A shortest path joining these cells consists of at most $r$ steps through neighboring cells. Along each step the number can increase by at most $M$. Hence the number in the final cell does not exceed

$$1+Mr.$$

Let

$$D(r)=1+2r(r+1)$$

be the number of cells whose Manhattan distance from the chosen cell is at most $r$.

All these $D(r)$ cells contain distinct numbers, because every natural number occurs exactly once. Each of those numbers is at most $1+Mr$. Consequently there are at least $D(r)$ distinct integers in the interval $[1,1+Mr]$, which contains only $1+Mr$ integers. Therefore

$$D(r)\le 1+Mr.$$

Substituting the formula for $D(r)$ gives

$$1+2r(r+1)\le 1+Mr,$$

or

$$2r(r+1)\le Mr.$$

For sufficiently large $r$ this is impossible. The contradiction shows that no such constant $M$ exists.

Hence for every prescribed $m$ there exist neighboring cells whose numbers differ by at least $m$.

An example is obtained by numbering the cells consecutively along an infinite square spiral:

$$1,2,3,4,\dots .$$

Each natural number then occurs exactly once.

For part 2, let $d$ be a number such that every pair of neighboring cells differs by at most $d$.

Choose the unique cell containing $1$.

The same argument as above shows that every cell at Manhattan distance at most $r$ from that cell contains a number not exceeding

$$1+dr.$$

The radius-$r$ diamond contains

$$D(r)=1+2r(r+1)$$

cells.

All numbers appearing in this diamond belong to the set

$${1,2,\dots,1+dr}.$$

Since the number $n$ occurs exactly $n$ times, the total number of occurrences of numbers from this set equals

$$1+2+\cdots +(1+dr) = \frac{(1+dr)(2+dr)}2.$$

The diamond contains only occurrences of these numbers, hence

$$1+2r(r+1) \le \frac{(1+dr)(2+dr)}2.$$

Expanding both sides yields

$$2r^2+2r+1 \le \frac{d^2}{2}r^2+\frac{3d}{2}r+1.$$

If $d\le1$, then the coefficient of $r^2$ on the right is at most $1/2$, while on the left it equals $2$, so the inequality fails for large $r$.

Thus

$$d\ge2.$$

Therefore every arrangement contains neighboring cells whose numbers differ by at least

$$d+1\ge3.$$

It follows that every arrangement contains neighboring cells whose numbers differ by at least $3$.

To show that $3$ is best possible, enumerate the cells by a square spiral and write along this spiral the sequence

$$1,;2,2,;3,3,3,;4,4,4,4,\dots ,$$

so that the number $n$ occupies exactly $n$ consecutive positions of the spiral.

By construction, the number $n$ appears exactly $n$ times.

Two consecutive positions of the spiral carry either equal numbers or consecutive numbers, so their difference is at most $1$.

For side-neighboring cells that are not consecutive along the spiral, both cells lie on adjacent turns of the spiral. The indices of such positions differ by at most the length of one side of the corresponding square layer. When the spiral reaches the layer of side length $2t+1$, the written values are approximately $\sqrt{2N}$, where $N$ is the spiral index. Increasing the index by at most $2t+1$ changes the written value by at most $4$. A direct inspection of the first layers shows that the same bound holds there as well.

Hence every pair of neighboring cells contains numbers differing by at most $4$.

Thus there exists an arrangement with multiplicities $n$ and with all neighboring differences at most $4$.

The largest integer that must occur as a neighboring difference is therefore

$$\boxed{3}.$$

Verification of Key Steps

The first counting argument uses the fact that all numbers inside the radius-$r$ diamond are at most $1+Mr$. Since the numbers are distinct in part 1, the diamond contributes exactly $D(r)$ distinct integers from the interval $[1,1+Mr]$. Reversing the inclusion would produce the inequality

$$1+Mr\le D(r),$$

which is true and yields no contradiction. The correct inequality is

$$D(r)\le 1+Mr.$$

For part 2, the multiplicity condition changes the counting completely. The available occurrences of numbers not exceeding $1+dr$ equal

$$1+2+\cdots +(1+dr),$$

not merely $1+dr$. Forgetting multiplicities would reproduce the argument from part 1 and lead to a much stronger but false conclusion.

The coefficient comparison is decisive. The diamond contains

$$2r^2+O(r)$$

cells. The available occurrences up to value $1+dr$ equal

$$\frac{d^2}{2}r^2+O(r).$$

The inequality can hold for arbitrarily large $r$ only when

$$\frac{d^2}{2}\ge2,$$

which is equivalent to $d\ge2$.

Alternative Approaches

The lower bound in part 2 can also be obtained by considering asymptotic densities. If neighboring differences are bounded by $d$, then all cells inside a diamond of radius $r$ contain numbers at most $1+dr$. The density of occurrences of numbers not exceeding $N$ is asymptotic to $N^2/2$. Comparing this with the area growth of diamonds again yields the condition $d^2/2\ge2$.

For the construction, one may use a diamond spiral instead of a square spiral. The numbers $1,2,2,3,3,3,\dots$ are written along the spiral path, and the geometry of successive turns becomes slightly simpler. The main proof uses the square spiral because it is the standard enumeration of the lattice and makes the multiplicity condition transparent.