• Mar 8th 2012, 09:48 AM
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?
• Mar 10th 2012, 05:13 AM
awkward
Quote:

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$?
• Mar 10th 2012, 05:32 AM
abhishekkgp
Quote:

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!
• Mar 10th 2012, 08:09 AM
godelproof
Quote:

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!!
• Mar 10th 2012, 08:16 AM
abhishekkgp