Your problem is equivalent to the following: We label the vertces of the nxn grid graph with distinct elements from the set [n^2]. Then there are adjacent vertices such that their labels differ by at least n. I think i found a solution. The key related result is the vertex isoperimetric inequality in the grid. For our problem it is enough to consider the corollary 12 in the following .pdf:
With parameters: n=2 since we are in a 2 dimensional grid. Let A be the set which have the labels: 1,2,..., n(n-1)/2. Clearly then we can set r=n-1 and with t=1 we obtain that there are at least n neighbors of this set. This finishes our proof since one of these neighbors will have a label of at least n(n-1)/2+n.
login/create account
Drupal
CSI of Charles University
Solution
Dear Dr. Lioubimov
Your problem is equivalent to the following: We label the vertces of the nxn grid graph with distinct elements from the set [n^2]. Then there are adjacent vertices such that their labels differ by at least n. I think i found a solution. The key related result is the vertex isoperimetric inequality in the grid. For our problem it is enough to consider the corollary 12 in the following .pdf:
https://www.dpmms.cam.ac.uk/~par31/notes/extcomb.pdf
With parameters: n=2 since we are in a 2 dimensional grid. Let A be the set which have the labels: 1,2,..., n(n-1)/2. Clearly then we can set r=n-1 and with t=1 we obtain that there are at least n neighbors of this set. This finishes our proof since one of these neighbors will have a label of at least n(n-1)/2+n.
Sincerely Daniel Soltész