Think of the matrix as being made up of an *n × n* collection of
unit squares. Consider the boundary of the set of squares along the diagonal.
This boundary (call it *B*) consists of *4n* unit line segments.
Now consider the boundaries of the squares that John requests. Call that
set of boundaries *J*. We know that each *b ∈ B *is a subsegment
of some* j ∈ J.* Suppose not. Then there exists a pair of unit squares
*u*, *v* with *u* on the diagonal and *v* adjacent
to it, such that every square that John chooses contains both *u*
and *v*, or contains neither *u* nor *v*. If we replace
*u* by *u+1* and *v* by *v −1*, then the diagonal
sum increases by 1, but the value of all of the squares that John requested
are exactly the same. So the answer he gets, which is a function of the
square sums, cannot be guaranteed to be correct. But any square John requests
can cover at most 4 elements of *B*. Therefore John must have selected
at least *n* squares. Note that this solution assumes that John is
only allowed to choose contiguous submatrices i.e. the sets of rows and
columns must both be of the form {*x, x+ 1, . . . , y*}.

Mike Schuresko sent in an alternative solution.