Results 1 to 5 of 5

Math Help - Chessboard problem. Olympiad question.

  1. #1
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1

    Chessboard problem. Olympiad question.

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1

    Re: Chessboard problem. Olympiad question.

    Quote Originally Posted by abhishekkgp View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1

    Re: Chessboard problem. Olympiad question.

    Quote Originally Posted by awkward View Post
    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!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    May 2009
    Posts
    146

    Re: Chessboard problem. Olympiad question.

    Quote Originally Posted by abhishekkgp View Post
    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!!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1

    Re: Chessboard problem. Olympiad question.

    Quote Originally Posted by godelproof View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: January 13th 2010, 07:42 AM
  2. A olympiad question
    Posted in the Algebra Forum
    Replies: 1
    Last Post: September 30th 2009, 07:43 AM
  3. Tough Problem from an olympiad
    Posted in the Algebra Forum
    Replies: 7
    Last Post: February 15th 2009, 06:20 PM
  4. Olympiad Problem- I am stuck
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 28th 2007, 09:53 AM
  5. Replies: 21
    Last Post: November 11th 2007, 08:20 AM

Search Tags


/mathhelpforum @mathhelpforum