Does anyone have a solution to this problem? I have worked on it for some time and not found a solution.

The idea is to consider an interval of $ n-1$ consecutive integers which divides $ \{1,2,\ldots,n^2\}$ into integer sequences of length $ \binom{n}{2}$ and $ \binom{n}{2}+1$. $ n-1$ integers cannot contain a full row or column, so the two intervals must border one another, which gives the desired result. Not very rigorous, but it's only an outline. I tried finding a nicer argument with something like expected value, coloring, or paths, but it i'didn't work out.

We can prove more general result(*): Let the cells of an $n \times n$ board be filled with an integer, such that the difference of numbers in any two neighbouring (with common edge) squares is at most $d$. Then there exists a number that appears in the board at least $\frac{n}{d}$ times. From this result, if the difference of numbers in any two neighbouring (with common edge) squares is at most $n-1$. Then there exists a number that appears in the board at least $\left\lceil{\frac{n}{{n - 1}}}\right\rceil=2$ times, contradiction. Proof of (*):We point out the biggest number of each rows, and the biggest number of each columns, suppose $m$ is the smallest one of these pointed out numbers. Without loss of generality, we can suppose $m$ is the biggest number of row $i$. For any column $j$, suppose the biggest number of column $j$ is $M$, ${a_{ij}} = p$, then $M \geqslant m\geqslant p$ , because the difference of numbers in any two neighbouring (with common edge) squares is at most $d$. So in column $j$ there exist a number of $\left[ {m,m+d-1}\right]$ between $p$ and $M$. So there are at least $n$'s numbers of $\left[ {m,m+d-1} \right]$ appear in the board, one of these number must appears at least $\frac{n}{d}$ times.

Attachments:

Is there another solution to this problem? The solution above seems vague and non-intuitive. Why is this particular statement from the above solution true ? - "So in column $j$ there exist a number of $\left[ {m,m+d-1}\right]$ between $p$ and $M$."

consider the subset {1,2,3,...,(n/2)^2} as A and other numbers as B. A and B has more than n common edges. But only n-1 numbers in B that differ less than n from numbers in A ( from (n/2)^2+1 to (n/2)^2+n-1 ). So there must be a common edge of A&B that the two numbers share this edge has difference more than n-1. To prove A and B has more than n common edges. We can consider A in 4 different situation. 1. A has x full rows and y full columns. (xy>0) 2. A has x full rows and 0 full columns. 3. A has 0 full rows and y full columns. 4. A has 0 full rows and 0 full columns. for each square, up and bottom edges are row edges, left and right edges are column edges. 1. row edges of A >= n-y column edges of A >= n-x edges of A >= 2n-x-y ∵ number of squares of A in full rows and full columns are: n*x+n*y-xy<=(n/2)^2, and 0<x<=n, 0<y<=n x+y<n/2 so, edges of A >= 2n-x-y >= 3n/2 2. row edges of A =n so, edges of A >=n 3. column edges of A =n so, edges of A >=n 4. if x row has squares in A and y columns has squares in A. Then, row edges of A >=y, and columb edges of A >=x. So, edges of A>=x+y ∵x*y>=(n/2)^2 So, x+y>=n edges of A >=n Sorry for my bad English expression.

Here's an alternate way to use the idea in love_sc1's solution, where it suffices to partition the board into two consecutive intervals of numbers with at least $n$ borders. Let $S_k$ be the set of squares containing a number at most $k$. We consider the maximal $k$ such that $S_k$ contains neither a full row or a full column. WLOG $S_{k+1}$ contains a full row, and $k+1$ is in row $r$, column $c$. The missing square in row $r$ gives us one vertical border between $S_k$ and its complement. We also know that $S_k$ has no full columns, so the other $n-1$ columns besides column $c$ are missing at least one square but do have a square in row $r$. We get at least one horizontal border in each of those $n-1$ columns. That's at least $n$ borders total.

Ramchandran wrote: Is there another solution to this problem? The solution above seems vague and non-intuitive. Why is this particular statement from the above solution true ? - "So in column $j$ there exist a number of $\left[ {m,m+d-1}\right]$ between $p$ and $M$." Because “such that the difference of numbers in any two neighbouring (with common edge) squares is at most $d$.”

Can someone please post another solution or clarify the solutions posted here already. Even the official solution from the IMO compendium is not explained well and unnatural.

We write $1$~$n^2$ step by step.We consider the number of empty squares which neighbor on written squares.If this number is not less than $n$ at a moment,the proof is completed.We consider the moment some row(or some column) is completed(written numbers). Case1:only some row is completed Since any column isn't completed,there is at least one empty square on each column which neighbors on written square.Thus the number of empty squares which neighbor on written squares is not less than $n$. Case2:only some column is completed This is the same as Case1. Case3:some row and some column are completed simultaneously Just before some row and some column are completed simultaneously,there is at least one empty square on each column which neighbors on written squares in the same way as Case1.Thus the number of empty squares which neighbor on written squares is not less than $n$. From Case1,2,3,the proof is completed.$\blacksquare$

Takeya.O wrote: We write $1$~$n^2$ step by step.We consider the number of empty squares which neighbor on written squares.If this number is not less than $n$ at a moment,the proof is completed.We consider the moment some row(or some column) is completed(written numbers). Case1:only some row is completed Since any column isn't completed,there is at least one empty square on each column which neighbors on written square.Thus the number of empty squares which neighbor on written squares is not less than $n$. Case2:only some column is completed This is the same as Case1. Case3:some row and some column are completed simultaneously Just before some row and some column are completed simultaneously,there is at least one empty square on each column which neighbors on written squares in the same way as Case1.Thus the number of empty squares which neighbor on written squares is not less than $n$. From Case1,2,3,the proof is completed.$\blacksquare$ Amazing solution .

Takeya.O wrote: We write $1$~$n^2$ step by step.We consider the number of empty squares which neighbor on written squares.If this number is not less than $n$ at a moment,the proof is completed.We consider the moment some row(or some column) is completed(written numbers). Case1:only some row is completed Since any column isn't completed,there is at least one empty square on each column which neighbors on written square.Thus the number of empty squares which neighbor on written squares is not less than $n$. Case2:only some column is completed This is the same as Case1. Case3:some row and some column are completed simultaneously Just before some row and some column are completed simultaneously,there is at least one empty square on each column which neighbors on written squares in the same way as Case1.Thus the number of empty squares which neighbor on written squares is not less than $n$. From Case1,2,3,the proof is completed.$\blacksquare$ .We consider the number of empty squares which neighbor on written squares.If this number is not less than $n$ at a moment,the proof is completed.We consider the moment some row(or some column) is completed(written numbers) Why if this number is not less than n at moment, the proof is completed ?

fwolth wrote: The idea is to consider an interval of $ n-1$ consecutive integers which divides $ \{1,2,\ldots,n^2\}$ into integer sequences of length $ \binom{n}{2}$ and $ \binom{n}{2}+1$. $ n-1$ integers cannot contain a full row or column, so the two intervals must border one another, which gives the desired result. Not very rigorous, but it's only an outline. I tried finding a nicer argument with something like expected value, coloring, or paths, but it i'didn't work out. The $n-1$ integers cannot contain a full row of column, but it can certainly divide the $n \cdot n$ board into two non bordering sections. It can trap one corner...

I would like to also ask Lukariman's question. Why if there are more than $n$ unwritten squares in Takeya's solution is it implied that some two adjacent numbers differ by at least $n$?

Plops wrote: I would like to also ask Lukariman's question. Why if there are more than $n$ unwritten squares in Takeya's solution is it implied that some two adjacent numbers differ by at least $n$? I too ask the same question

I got my mistake so please ignore whatever I wrote below as I am not able to delete the post This is wrong, I don't know how to share grid here so I will just write the number in position without grid. 1. 2. 3. 6. 4. 5. 8. 9. 7. No numbers on edge differ by n,i.e., 3

By at least $n$. @above

The Solution can be found in Chapter 4 of Olympiad Combinatorics by Pranav sriram. Example 11

By doing basic combinatorics you can see that the total number of pairs that are possible - the pairs which have atleast n difference < the total number of neighboring squares in the chessboard The left side of the gives the total number of pairs which are allowed in any two neighboring vertices So this means as each and every pair is distinct according to the question therefore This proves that it is not possible to put these number into the chessboard without having the difference of any two squares atleast n.

Suppose all cells of the chessboard are initially white. Color them black, starting from the cell labeled $1$, then the cell labeled $2$, and so on, up to $n^2$. Call a cell peripheral if it is white and adjacent to at least one black cell. Claim: If there are at least $n$ peripheral cells at any point in the process, then we are done. Proof: Suppose there are at least $n$ peripheral cells after the cells numbered $1$ through $k$ are colored. Then, the maximum label of a peripheral cell is at least $k+n$. However, the peripheral cell is adjacent to some cell with label at most $k$ by definition. This means there are two cells with labels that differ by at least $n$. $\square$ Consider when there first exists a row or column that is completely black. If either one row or one column is completely black, assume WLOG it is a row. Then, each column contains at least one black cell and one white cell, so it contains at least one peripheral cell. This gives at least $n$ peripheral cells, so we are done. Otherwise, a row and a column become completely black simultaneously. By a similar argument, we can find at least one peripheral cell in $n-1$ of the columns. If we consider the move before both the row and column became completely black, we find that the cell at their intersection was a peripheral cell. Furthermore, no other peripheral cell becomes not peripheral, so we have found $n$ peripheral cells. $\blacksquare$