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.
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ Sidenote: a chessboard has 8x8 squares $\endgroup$– fondorMay 10, 2016 at 7:58
-
$\begingroup$ @fondor. I know...that's why i put chessboard in brackets. Just so people can visualize it better. $\endgroup$– MariusMay 10, 2016 at 8:10
-
$\begingroup$ @fondor - see chessboard description; size and shape may be altered from the classical 8 by 8 square. $\endgroup$– Jonathan AllanMay 10, 2016 at 15:53
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
