# Chessboard problem. Olympiad question.

• Mar 8th 2012, 09:48 AM
abhishekkgp
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?
• Mar 10th 2012, 05:13 AM
awkward
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$?
• Mar 10th 2012, 05:32 AM
abhishekkgp
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!
• Mar 10th 2012, 08:09 AM
godelproof
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!!
• Mar 10th 2012, 08:16 AM
abhishekkgp
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.