1. ## Chessboard problem. Olympiad question.

Place the integers $1,2,3, \ldots, n^2$(without duplication) on an $n \times n$ chessboard, with one integer per square. Show that there exist two adjacent entries such that their difference is at least $n+1$. (Adjacent means horizontally, vertically or diagonally adjacent.)

I tried using "extreme principle" but that doesn't lead me anywhere. Any ideas?

2. ## Re: Chessboard problem. Olympiad question.

Originally Posted by abhishekkgp
Place the integers $1,2,3, \ldots, n^2$(without duplication) on an $n \times n$ chessboard, with one integer per square. Show that there exist two adjacent entries such that their difference is at least $n+1$. (Adjacent means horizontally, vertically or diagonally adjacent.)

I tried using "extreme principle" but that doesn't lead me anywhere. Any ideas?
Assume the contrary, so there is a numbering of the squares in which the difference between any two adjacent entries is at most $n$. Suppose we move a king from one square to another. (Kings in chess move one square horizontally, vertically, or diagonally.) The number on the square he moves to increases by at most $n$ from the previous square, so in $k$ moves, the entries increase by at most $kn$. Chessplayers (of the $n=8$ variety, at least) know that the king can move from any square on the board to any other square in at most $n-1$ moves.

So what does this say about a king moving from square $1$ to square $n^2$?

3. ## Re: Chessboard problem. Olympiad question.

Originally Posted by awkward
Assume the contrary, so there is a numbering of the squares in which the difference between any two adjacent entries is at most $n$. Suppose we move a king from one square to another. (Kings in chess move one square horizontally, vertically, or diagonally.) The number on the square he moves to increases by at most $n$ from the previous square, so in $k$ moves, the entries increase by at most $kn$. Chessplayers (of the $n=8$ variety, at least) know that the king can move from any square on the board to any other square in at most $n-1$ moves.

So what does this say about a king moving from square $1$ to square $n^2$?
A proof from "The Book" ... as Erdos would put it.
Thank you so much!

4. ## Re: Chessboard problem. Olympiad question.

Originally Posted by abhishekkgp
Place the integers $1,2,3, \ldots, n^2$(without duplication) on an $n \times n$ chessboard, with one integer per square. Show that there exist two adjacent entries such that their difference is at least $n+1$. (Adjacent means horizontally, vertically or diagonally adjacent.)

I tried using "extreme principle" but that doesn't lead me anywhere. Any ideas?
Is this really an Olympiad question, abhishekkgp???? The answer is so straight forward!!

5. ## Re: Chessboard problem. Olympiad question.

Originally Posted by godelproof
Is this really an Olympiad question, abhishekkgp???? The answer is so straight forward!!
No. I don't think this is an Olympiad question. But its in an Olympiad training book. Its supposed to be among the harder ones.