Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Squares and Numbers

  1. Nov 14, 2007 #1
    1. The problem statement, all variables and given/known data

    A square is divided into 81 smaller squares by lines parallel to its sides. The numbers 1, 2, ..., 81 are entered in an arbitrary fashion, one in each square.

    Show that, however the numbers are entered, it is possible to find two small squares with an edge in common whose entries differ by more than 5.

    2. Relevant equations

    3. The attempt at a solution

    (Proof by contradiction)

    Assume the numbers 1 to 81 have been entered so that any two adjacent squares have entries by at most 5.

    Some of the non-adjacent squares have a common adjacent square.

    Therefore, no squares diagonally opposite from each would have a difference of more than 10. However, all squares have at least two adjacent squares, so the difference of diagonally opposite squares cannot be more than 9


    6/11 will not work, but

    6/10 will.

    That's as far as I've gotten. Do i just continue doing that? Or is there another way?
  2. jcsd
  3. Nov 14, 2007 #2


    User Avatar
    Science Advisor
    Homework Helper

    You could try to consider the big picture. You can travel from any square to any other square by passing through edges. What's the smallest number K such that you can do this by passing through at most K squares? Now consider what happens when you connect the square containing 1 with the square containing 81.
  4. Nov 15, 2007 #3
    I don't quite understand. Could you explain further?
  5. Nov 15, 2007 #4


    User Avatar
    Science Advisor
    Homework Helper

    I'm asking what's the maximum distance between any two squares on the grid, where distance measures how many squares you have to pass through (edgewise) to get from one to the other.
  6. Nov 15, 2007 #5
    In fact we can improve this number. We can show there exists two adjacent squares with difference at least 10 (where adjacent means diagnolly also).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook