Solve Squares & Numbers Homework: Diff > 5

[lolerlol]

Homework Statement

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.

Homework Equations

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

i.e.

1/5
6/11 will not work, but

1/5/9
6/10 will.

That's as far as I've gotten. Do i just continue doing that? Or is there another way?

 

[Dick]

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.

 

[lolerlol]

I don't quite understand. Could you explain further?

 

[Dick]

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.

 

[Kummer]

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).