4
$\begingroup$

Given a $7\times 7$ Board with corners removed ($45$ squares in total), each square contains a natural number.

The difference between the numbers inside squares with shared sides isn't bigger than $4$.

Prove that $2$ squares on board share the same number.

Have been wondering about this one for a while without any success, any hints ?

$\endgroup$
  • $\begingroup$ yes, corners would be more correct, natural numbers only. $\endgroup$ – Yariv Levy Dec 29 '17 at 20:59
  • 1
    $\begingroup$ This is just as true without removing the corners, albeit a bit less obvious. $\endgroup$ – Brilliand Dec 29 '17 at 22:04
  • $\begingroup$ Indeed, the max distance would be 12 steps, but that distance is realised only on the opposite corners, which would force both pairs of the opposite corners to contain the min/max values. $\endgroup$ – user491874 Dec 29 '17 at 22:17
9
$\begingroup$

From any square to any other square on the board, you can get in at most 10 moves. (A move is horizontal or vertical, by one place.)

This means that, from a square with the smallest number to the square with the largest number, you can move in at most 10 moves. This in turn means that the difference between the largest and the smallest number is at most 40.

Thus, there can be only up to 41 different numbers on the board, and as the board has 45 fields, two will contain the same number.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.