In each square in a table $10\times 10$ we write a whole number so the difference between any two numbers by the neighboring squares must be no more than $5$ (two squares are neighboring if they have a common side). Show that two of the numbers must be equal. Please help me!
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Suppose all the numbers were different (say, numbered from 1 to 100, because anything farther is automatically impossible if that case is). How would you place the numbers down to minimize their differences? Are all these differences less than 5? Can you prove that it's impossible?
Solution: Write the number 1 on the top-left corner, and the number 100 on the bottom-right. The distance between 1 and 100 is 18 squares. So, trace out any path from 1 to 100 that is 18 squares long. Since the difference between consecutive squares is at most 5, the difference between the first and last squares along this path is at most 90, so a difference of 99 (from 1 to 100) is impossible.