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 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\pm1\pmod{2011}$, or if $y=y'$ and $x-x'\equiv\pm1\pmod{2011}$.) (Romania) Dan Schwarz
Problem
Source:
Tags: analytic geometry, modular arithmetic, combinatorics proposed, combinatorics
19.03.2012 10:14
what RMM stands for ?
19.03.2012 10:58
Romanian Master of Mathematics competition.
16.10.2014 23:17
Here's an outline for a rather sketchy solution that I think works. The answer is $2n-1=4021$, just as it is $n$ in the non torus case (which I have seen before). The idea is sort of isoperimetric one from the non torus case where the answer is $n$. The construction (which I did not come up with) is on the official solution. Basically, this question is equivalent to asking whether or not you can write $1$, $2$, ... $n^2$ in that order down on a torus such that at any point the existing cells touch (with a side) less than $2n$ other squares. However, if $a_i$ squares are written in row $a_i$ then the total number of adjacent squares is sum $f(a_i)$, where $f(a_i)=2011-a_i$ for $a_i=0$ or $a_i=1$, and for smaller values it's $max(2,a_{i+1}-a_i,a_{i-1}-a_i$ (equality can hold when $a_i=k$ means that in row $i$ the numbers in columns $1$, $2$, ... $k$ exactly are covered). If we have a total of $\frac {2011^2-1} {2}$ squares, so that's sum $a_i$. Through a bunch of sketchy smoothing with a lot of details we're done. The idea is to group together all the $a_i$ that are $2011$ (moving an $a_i$ bigger than its neighbors next to an even bigger one does not hurt anything), and sort of "build around" so the big things are concentrated on one end and the small are on the other. If $a_{i+1}>a_i+2$, $a_{j+1}>a_j+2$, and $a_{i+1}>a_j$ then giving from $a_{i+1}$ to $a_j$ does not increase sum $f(a_i)$. Also if $a_{i+1}>a_i+3$ then giving from $a_{i+1}$ to $a_i$ does not increase the sum either. All this decreases the sum of squares so eventually it stops and we can see that sum $f(a_i)$ is at least $2n-1$. OK here is the rest of my solution, in a PM to the author. We assume $a_1+...a_2011=\frac {2011^2-1} {2}$, and show these squares touch at least $4021$ squares. This is very long but I think it works. Hidden for length.
Of course the official solution is much nicer than the whole sum $f(a_i)$ thing even though (as I pointed out), it leaves out some details... http://rmms.lbi.ro/rmm2011/_dwl/Sols2011D2.pdf
20.01.2016 11:40
Generalization to a $ k $ dimension. The cells of a $ k $-dimension space $ 2011^{k}$ array are labelled with the integers $1,2,\ldots, 2011^k$, 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_k$ such that, no matter which labelling we choose, there exist two neighbouring cells with the difference of their labels at least $M_k$. (Cells with coordinates $(x_1,x_2,...x_k)$ and $(x'_1,x'_2,...x'_k)$ are considered to be neighbours if there exixts an $ 1\leq i \leq k $ such that $x_j=x'_j$ for all $ j \neq i $ and $x_i-x'_i\equiv\pm1\pmod{2011}$.)
23.02.2021 20:20