Chessboard problem. Olympiad question.

**abhishekkgp** · Mar 8th 2012, 09:48 AM

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?

**awkward** · Mar 10th 2012, 05:13 AM

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

**abhishekkgp** · Mar 10th 2012, 05:32 AM

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!

**godelproof** · Mar 10th 2012, 08:09 AM

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

**abhishekkgp** · Mar 10th 2012, 08:16 AM

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.

Thread: Chessboard problem. Olympiad question.

LinkBack

Thread Tools

Display

Chessboard problem. Olympiad question.

Re: Chessboard problem. Olympiad question.

Re: Chessboard problem. Olympiad question.

Re: Chessboard problem. Olympiad question.

Re: Chessboard problem. Olympiad question.

Similar Math Help Forum Discussions

An interesting Korean math olympiad problem about exponents

A olympiad question

Tough Problem from an olympiad

Olympiad Problem- I am stuck

Inequality, not very hard but nice olympiad problem

Search Tags