8
$\begingroup$

You are given an empty $9\times9$ grid (sort-of like a blank Sudoku grid, or sort-of like a chessboard, but with one extra row and one extra column).
You fill in these cells randomly with all the integers between 1 and 81 (inclusive).
Prove that there is at least one $2\times2$ square where the sum of the numbers is more than 137.

$\endgroup$
  • 1
    $\begingroup$ Sidenote: a chessboard has 8x8 squares $\endgroup$ – fondor May 10 '16 at 7:58
  • $\begingroup$ @fondor. I know...that's why i put chessboard in brackets. Just so people can visualize it better. $\endgroup$ – Marius May 10 '16 at 8:10
  • $\begingroup$ @fondor - see chessboard description; size and shape may be altered from the classical 8 by 8 square. $\endgroup$ – Jonathan Allan May 10 '16 at 15:53
9
$\begingroup$

The 4 corner squares are part of 1 2x2 square each, the 28 edge squares are part of 2 2x2 squares each, and the 49 center squares are part of 4 2x2 squares each.

To minimize the sum of the 2x2 squares we put the higher numbers in the corners first and then at the edges, for a total sum of all 2x2 squares of 8774

The average of the 2x2 squares are then

8774/64=137.09375

Which proves it because

not every 2x2 square can be smaller then this, so there must be some equal or higer, and since all numbers are integers, there must be a 2x2 square of at least 138.

$\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.