# Homework Help: Squares and Numbers

1. Nov 14, 2007

### lolerlol

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

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

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?

2. Nov 14, 2007

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

3. Nov 15, 2007

### lolerlol

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

4. Nov 15, 2007

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

5. Nov 15, 2007

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