RMM 2011 Problem 6

Day 2
Answer

The cells of a square $2011 \times 2011$ array are labelled with the integers $1,2, \ldots, 2011^{2}$ , in such a way that every label is used exactly once. We then identify the lefthand and right-hand edges, and then the top and bottom, in the normal way to form a torus (the surface of a doughnut).

Determine the largest positive integer $M$ such that, no matter which labelling we choose, there exist two neighbouring cells with the difference of their labels at least M.[4] (ROMANIA) DAN SchwarZ Preamble. For a planar $N \times N$ array, it is folklore that this value is $M=N$ , with some easy models shown below. As such, the problem is mentioned in [Béla Bollobás - The Art of Mathematics], 21. Neighbours in a Matrix.

This is not necessarily a flaw on the actual problem, which is presented in a brand novel setting; on the contrary, some general previous knowledge on such type of problems (which we think must be encouraged) is beneficial in searching for the right ideas of a proof.

The idea for a proof goes along the lines of finding a moment in the consecutive filling with numbers of the array, when there are at least $N$ pairs of adjacent filled/yet-unfilled cells (with either distinct filled cells or distinct yet-unfilled cells). Then, when the cell next to that bearing the least label is filled, the difference between its label and the one being filled will be at least $N$ .

1	2	$\ldots$	N
$\mathrm{~N}+1$	$\mathrm{~N}+2$	$\ldots$	2 N
$\vdots$	$\vdots$	$\ddots$	$\vdots$
$(\mathrm{~N}-1) \mathrm{N}+1$	$(\mathrm{~N}-1) \mathrm{N}+2$	$\ldots$	$\mathrm{~N}^{2}$

A planar parallel $N \times N$ model array.

1	2	4	$\ldots$		$\mathrm{~N}(\mathrm{~N}-1) / 2+1$
3	5	$\ldots$	$\mathrm{~N}(\mathrm{~N}-1) / 2+2$
6		$\ldots$
$\vdots$	$\vdots$	$\vdots$	$\ddots$	$\vdots$	$\vdots$
	$\mathrm{~N}(\mathrm{~N}+1) / 2-1$	$\ldots$		$\mathrm{~N}^{2}-2$
$\mathrm{~N}(\mathrm{~N}+1) / 2$		$\ldots$	$\mathrm{~N}^{2}-1$	$\mathrm{~N}^{2}$

A planar diagonal $N \times N$ model array.

Dataset text NuminaMath olympiads. Quoted with source.

Show the answer

2011

Solutions

No solution is on olymmath yet. Official and human solutions come first when they arrive. AI solutions come after them, with a label.

Add a solution

Locator rmm/2011/p6 · Tag HMSH5HFGT7 · Edit this page on GitHub · Keys: j next, k previous