Thread: 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?

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$?

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!

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!!

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.