C2. Let $m, n \geq 2$ be positive integers. Each entry of an $m \times n$ grid contains a real number in the range $[-1,1]$, i.e. between -1 and 1 inclusively. The grid also has the property that the sum of the four entries in every $2 \times 2$ subgrid is equal to 0 . (A $2 \times 2$ subgrid is the intersection of two adjacent rows and two adjacent columns of the original grid.) Let $S$ be the sum of all of the entries in the grid.
a. Suppose $m=6$ and $n=6$. Explain why $S=0$.
b. Suppose $m=3$ and $n=3$. If the elements of the grid are
\begin{tabular}{|l|l|l|}
\hline$a$ & $b$ & $c$ \\
\hline$d$ & $e$ & $f$ \\
\hline$g$ & $h$ & $i$ \\
\hline
\end{tabular}
show that $S+e=a+i=c+g$.
c. Suppose $m=7$ and $n=7$. Determine the maximum possible value of $S$.
Solution:
a. A $6 \times 6$ grid can be partitioned into $2 \times 2$ subgrids, because there is an even number of squares along each side of the grid. Since the sum of the entries of each of the subgrids is 0 , the sum of all of the entries of the grid is 0 . Therefore, $S=0$.
b. We have $S=a+b+c+d+e+f+g+h+i$ and the sum of the four entries in every $2 \times 2$ subgrid is equal to 0 . Thus,
$$
\begin{array}{l}
S+e=(b+c+e+f)+(d+e+g+h)+a+i=0+0+a+i=a+i . \\
S+e=(a+b+d+e)+(e+f+h+i)+c+g=0+0+c+g=c+g .
\end{array}
$$
c. The sum of all of the entries of the grid can be determined more simply with the following fact.
Fact: In the following $3 \times 3$ grid, where $a+b+d+e=e+f+h+i=0$,
\begin{tabular}{|l|l|l|}
\hline$a$ & $b$ & $c$ \\
\hline$d$ & $e$ & $f$ \\
\hline 0 & $h$ & $i$ \\
\hline
\end{tabular}
the sum of the entries is $S=c-e$. The proof is similar to (b), setting $g=0$ :
$$
S+e=(a+b+d+e)+(e+f+h+i)+c=0+0+c=c .
$$

We can partition the $7 \times 7$ grid as follows:
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline$\cdots$ & $\cdots$ & $\cdots$ & $\cdots$ & $a_{4}$ & $b_{4}$ & $c_{4}$ \\
\hline$\cdots$ & $\cdots$ & $\cdots$ & $\cdots$ & $d_{4}$ & $e_{4}$ & $f_{4}$ \\
\hline$\cdots$ & $\cdots$ & $a_{3}$ & $b_{3}$ & $c_{3}$ & $g_{4}$ & $h_{4}$ \\
\hline$\cdots$ & $\cdots$ & $d_{3}$ & $e_{3}$ & $f_{3}$ & $\cdots$ & $\cdots$ \\
\hline$a_{2}$ & $b_{2}$ & $c_{2}$ & $g_{3}$ & $h_{3}$ & $\cdots$ & $\cdots$ \\
\hline$d_{2}$ & $e_{2}$ & $f_{2}$ & $\cdots$ & $\cdots$ & $\cdots$ & $\cdots$ \\
\hline$c_{1}$ & $g_{2}$ & $h_{2}$ & $\cdots$ & $\cdots$ & $\cdots$ & $\cdots$ \\
\hline
\end{tabular}

The entries not labeled can be broken down into $2 \times 2$ grids, so their sum is 0 .
From (b) and the fact we used above, the sums of elements in the overlapping $3 \times 3$ grids
\begin{tabular}{|c|c|c|}
\hline$a_{2}$ & $b_{2}$ & $c_{2}$ \\
\hline$d_{2}$ & $e_{2}$ & $f_{2}$ \\
\hline$c_{1}$ & $g_{2}$ & $h_{2}$ \\
\hline
\end{tabular}
\begin{tabular}{|c|c|c|}
\hline$a_{3}$ & $b_{3}$ & $c_{3}$ \\
\hline$d_{3}$ & $e_{3}$ & $f_{3}$ \\
\hline 0 & $g_{3}$ & $h_{3}$ \\
\hline
\end{tabular}
\begin{tabular}{|c|c|c|}
\hline$a_{4}$ & $b_{4}$ & $c_{4}$ \\
\hline$d_{4}$ & $e_{4}$ & $f_{4}$ \\
\hline 0 & $g_{4}$ & $h_{4}$ \\
\hline
\end{tabular}
are
$c_{1}-e_{2}+c_{2}, c_{3}-e_{3}$ and $c_{4}-e_{4}$ respectively.
Hence, the sum of all of the entries of the $7 \times 7$ grid is
$$
c_{1}-e_{2}+c_{2}-e_{3}+c_{3}-e_{4}+c_{4} \text {. }
$$

An alternative way to show that $S$ in a $7 \times 7$ grid can be expressed as the alternating sum of the diagonal elements is as follows.

The $7 \times 7$ square is covered by two $3 \times 3$ squares (with diagonal elements $a, b, c$ and $e, f, g$ respectively) and by two $4 \times 4$ squares (overlapping in one element $d$ ). By part (b), the $3 \times 3$ squares have element sums of $a-b+c$ and $e-f+g$ respectively. The $4 \times 4$ squares can each be partitioned into four $2 \times 2$ squares and thus each has element sum 0 . Thus we get
$$
S=a-b+c+e-f+g+0+0-d=a-b+c-d+e-f+g .
$$

Since each entry lies between -1 and 1 inclusively, this sum is at most 7. Hence, the sum of all the entries is at most 7. This maximum sum can be obtained as follows:
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline 1 & 0 & 1 & 0 & 1 & 0 & 1 \\
\hline 0 & -1 & 0 & -1 & 0 & -1 & 0 \\
\hline 1 & 0 & 1 & 0 & 1 & 0 & 1 \\
\hline 0 & -1 & 0 & -1 & 0 & -1 & 0 \\
\hline 1 & 0 & 1 & 0 & 1 & 0 & 1 \\
\hline 0 & -1 & 0 & -1 & 0 & -1 & 0 \\
\hline 1 & 0 & 1 & 0 & 1 & 0 & 1 \\
\hline
\end{tabular}
or
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline 1 & -1 & 1 & -1 & 1 & -1 & 1 \\
\hline 1 & -1 & 1 & -1 & 1 & -1 & 1 \\
\hline 1 & -1 & 1 & -1 & 1 & -1 & 1 \\
\hline 1 & -1 & 1 & -1 & 1 & -1 & 1 \\
\hline 1 & -1 & 1 & -1 & 1 & -1 & 1 \\
\hline 1 & -1 & 1 & -1 & 1 & -1 & 1 \\
\hline 1 & -1 & 1 & -1 & 1 & -1 & 1 \\
\hline
\end{tabular}

Answer: 7 .