Chessboard problem. Olympiad question.

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

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

Re: Chessboard problem. Olympiad question.

Quote:

Originally Posted by

**abhishekkgp** Place the integers $\displaystyle 1,2,3, \ldots, n^2$(without duplication) on an $\displaystyle n \times n$ chessboard, with one integer per square. Show that there exist two adjacent entries such that their difference is at least $\displaystyle 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 $\displaystyle 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 $\displaystyle n$ from the previous square, so in $\displaystyle k$ moves, the entries increase by at most $\displaystyle kn$. Chessplayers (of the $\displaystyle n=8$ variety, at least) know that the king can move from any square on the board to any other square in at most $\displaystyle n-1$ moves.

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

Re: Chessboard problem. Olympiad question.

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 $\displaystyle 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 $\displaystyle n$ from the previous square, so in $\displaystyle k$ moves, the entries increase by at most $\displaystyle kn$. Chessplayers (of the $\displaystyle n=8$ variety, at least) know that the king can move from any square on the board to any other square in at most $\displaystyle n-1$ moves.

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

A proof from "The Book" ... as Erdos would put it.

Thank you so much!

Re: Chessboard problem. Olympiad question.

Quote:

Originally Posted by

**abhishekkgp** Place the integers $\displaystyle 1,2,3, \ldots, n^2$(without duplication) on an $\displaystyle n \times n$ chessboard, with one integer per square. Show that there exist two adjacent entries such that their difference is at least $\displaystyle 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!!

Re: Chessboard problem. Olympiad question.

Quote:

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.