, 2011

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it Romania

The cells of a square $2011 \times 2011$ array are labelled with the integers $1, 2, \dots, 2011^2$ , in such a way that every label is used exactly once. We then identify the left-hand 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$ .

Cells with coordinates $(x, y)$ and $(x', y')$ are considered to be neighbours if $x = x'$ and $y - y' \equiv \pm 1 \pmod{2011}$ , or if $y = y'$ and $x - x' \equiv \pm 1 \pmod{2011}$ .

Solution

For the toroidal case, it is clear the statement of the problem is referring to the cells of a $\mathbb{Z}_N \times \mathbb{Z}_N$ lattice on the surface of the torus, labeled with the numbers $1, 2, \dots, N^2$ , where one has to determine the least possible maximal absolute value $M$ of the difference of labels assigned to orthogonally adjacent cells.

The toroidal $N = 2$ case is trivially seen to be $M = 2$ (thus coinciding with the planar case).

1	2
3	4

The unique

2 \times 2

toroidal array.

For $N \ge 3$ we will prove that value to be at least $M \ge 2N - 1$ . Consider such a configuration, and color all cells of the square in white. Go along the cells labeled 1, 2, etc. coloring them in black, stopping just on the cell bearing the least label $k$ which, after assigned and colored in black, makes that all lines of a same orientation (rows, or columns, or both) contain at least two black cells (that is, before coloring in black the cell labeled $k$ , at least one row and at least one column contained at most one black cell). Wlog assume this happens for rows. Then at most one row is all black, since if two were then the stopping condition would have been fulfilled before cell labeled $k$ (if the cell labeled $k$ were to be on one of these rows, then all rows would have contained at least two black cells before, while if not, then all columns would have contained at least two black cells before).

Now color in red all those black cells adjacent to a white cell. Since each row, except the potential all black one, contained at least two black and one white cell, it will now contain at least two red cells. For the potential all black row, any of the neighbouring rows contains at least one white cell, and so the cell adjacent to it has been colored red. In total we have therefore colored red at least $2(N-1)+1 = 2N-1$ cells.

The least label of the red cells has therefore at most the value $k + 1 - (2N - 1)$ . When the white cell adjacent to it will eventually be labeled, its label will be at least $k+1$ , therefore their difference is at least $(k+1) - (k+1 - (2N-1)) = 2N - 1$ .

The models are kind of hard to find, due to the fact that the direct proof offers little as to their structure (it is difficult to determine the equality case during the argument involving the inequality with the bound, and then, even this is not sure to be prone to being prolonged to a full labeling of the array).

The weaker fact the value $M$ is not larger than $2N$ is proved by the general model exhibited below (presented so that partial credits may be awarded).

$N+1$	$N+2$	...	$2N$
$3N+1$	$3N+2$	...	$4N$
...	...	...	...
$(2\ell-1)N+1$	$(2\ell-1)N+2$	...	$2\ell N$
...	...	...	...
$2kN+1$	$2kN+2$	...	$(2k+1)N$
...	...	...	...
$2N+1$	$2N+2$	...	$3N$
1	2	...	$N$

A general model for

M = 2N

in a

N \times N

array.

By examining some small $N > 2$ cases, one comes up with the idea of spiral models for the true value $M = 2N - 1$ . The models presented are for odd $N$ (since 2011 is odd); similar models exist for even $N$ (but are less symmetric).

7	2	6
3	1	5
8	4	9

The spiral

3 \times 3

array.

23	16	7	15	22
17	8	2	6	14
9	3	1	5	13
18	10	4	12	21
24	19	11	20	25

The spiral

5 \times 5

array.

47	40	29	16	28	39	46
41	30	17	7	15	27	38
31	18	8	2	6	14	26
19	9	3	1	5	13	25
32	20	10	4	12	24	37
42	33	21	11	23	36	45
48	43	34	22	35	44	49

The spiral

7 \times 7

array.

$(2n+1)^2-2$	$(2n+1)^2-9$	...	$n(2n-1)+1$	...	$(2n+1)^2-10$	$(2n+1)^2-3$
$(2n+1)^2-8$		...	$n(2n-1)+2$	$n(2n-1)$	...	$(2n+1)^2-11$
...	...	...	...	...	...	...
	$2n^2$	...	8	2	6	$2n(n+1)+3$
$2n^2 + 1$	...	...	3	1	5	$2n(n-1)+2$
	$2n^2+2$	...	10	4	12	$2n(n+1)$
...	...	...	...	...	...	...
$(2n+1)^2-7$	...	$n(2n+1)$	$n(2n+1)+2$	...	$(2n+1)^2-5$	$(2n+1)^2-4$
$(2n+1)^2-1$	$(2n+1)^2-6$	...	$n(2n+1)+1$	...	$(2n+1)^2-5$	$(2n+1)^2$

The general spiral

N \times N

array for

N = 2n + 1 \ge 5

Thus, for $N = 2011$ , the answer is $M = 2 \times 2011 - 1 = 4021$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.

47	40	29	16	28	39	46
41	30	17	7	15	27	38
31	18	8	2	6	14	26
19	9	3	1	5	13	25
32	20	10	4	12	24	37
42	33	21	11	23	36	45
48	43	34	22	35	44	49

47	40	29	16	28	39	46
41	30	17	7	15	27	38
31	18	8	2	6	14	26
19	9	3	1	5	13	25
32	20	10	4	12	24	37
42	33	21	11	23	36	45
48	43	34	22	35	44	49

47	40	29	16	28	39	46
41	30	17	7	15	27	38
31	18	8	2	6	14	26
19	9	3	1	5	13	25
32	20	10	4	12	24	37
42	33	21	11	23	36	45
48	43	34	22	35	44	49