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.