Coloring Squares, Adding up Numbers

Let $G$ be the "grid" matrix,

$\displaystyle G=\left(\begin{array}{ccccc} 1&2&3&\cdots&n\\ n+1&n+2&n+3&\cdots&2n\\ 2n+1&2n+2&2n+3&\cdots&3n\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ (n-1)n+1&(n-1)n+2&(n-1)n+3&\cdots&n^2 \end{array}\right)$

We'll write matrix $G$ as a sum, $G=G_1+G_2,$ where

$\displaystyle G_1=\left(\begin{array}{ccccc} 1&2&3&\cdots&n\\ 1&2&3&\cdots&n\\ 1&2&3&\cdots&n\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&2&3&\cdots&n\\ \end{array}\right)$

and

$\displaystyle G_2=\left(\begin{array}{ccccc} 0&0&0&\cdots&0\\ n&n&n&\cdots&n\\ 2n&2n&2n&\cdots&2n\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ (n-1)n&(n-1)n&(n-1)n&\cdots&(n-1)n \end{array}\right)$

and let $G_1,G_2$ inherit the coloring of $G.$ Then, quite obviously, since the numbers in every column of $G_1$ are all equal, half of them sums to exactly the same amount as another half. The same holds for the rows of $G_2:$ since the rows consist of identical numbers, the sum of any half of the numbers in any row equals the sum of the remaining numbers in the same row.

It follows that in both $G_1$ and $G_2$ the sum of red numbers equals the sum of unpainted numbers. Given the associativity and commutativity of addition, the same holds for the matrix $G.$

Each column has $n/2$ painted cells. Hence, adding the cells for all the columns, there are $n^2/2$ cells painted - half the total number of cells.

As the number of painted cell is same as the number of unpainted cells, WLOG, we can number the cells from $0$ to $n^2-1$ without changing the essence of the problem. We are, essentially, subtracting $n^2/2$ from both sums.

Let us index the rows and columns from $0$ to $n-1$. Consider the cell in row $r$ and column $c$. In base $n$, the index of this cell is $nr+c$. The sum of the indices of the painted cells is then $\displaystyle S_p=n\sum_i r_i+\sum_i c_i$ where $i$ stands for the $i^{th}$ painted cell; $r_i$ and $c_i$ denote the row and column numbers of that cell, respectively. In the summation, each row shows up $n/2$ times and each column shows up $n/2$ times. Thus, this sum is $S_{painted}=S(n/2)$, where

$\displaystyle S(k)=k(n+1)\sum_{j=0}^{n-1} j.$

In the sum the indices of all cells (denoted by $S_{total}$), each row and column shows up $n$ times. Thus, $S_{total}=S(n)$. Clearly, $S_{total}$ is twice $S_{painted}$ or $S_{painted}=S_{unpainted}$.

Let the indexed variables $a$ stand for the numbers in the grid; the indexed $x$ indicate whether the cell was painted or not. In paricular, $a_{ij}=n(i-1)+j$ and

$\displaystyle \sum_{i=1}^nx_{ij}=\frac{n}{2},$ for all $j=1,2,\ldots, n$ and
$\displaystyle \sum_{j=1}^nx_{ij}=\frac{n}{2},$ for all $i=1,2,\ldots, n.$

Further,

$\displaystyle \begin{align} S&=\sum_{i=1}^n\sum_{j=1}^nx_{ij}[n(i-1)+j]=\sum_{i=1}^n\sum_{j=1}^nx_{ij}ni+\sum_{i=1}^n\sum_{j=1}^nx_{ij}j-\sum_{i=1}^n\sum_{j=1}^nx_{ij}n\\ &=\sum_{i=1}^nni\sum_{j=1}^nx_{ij}+\sum_{j=1}^nj\sum_{i=1}^nx_{ij}-\sum_{i=1}^nn\sum_{j=1}^nx_{ij}\\ &=\sum_{i=1}^nni\cdot\frac{n}{2}+\sum_{j=1}^nj\cdot\frac{n}{2}-\sum_{i=1}n\cdot\frac{n}{2}\\ &=\frac{n^2}{2}\sum_{i=1}^ni+\frac{n}{2}\sum_{j=1}^nj-\frac{n^3}{2}\\ &=\frac{n^2}{2}\cdot\frac{n(n+1)}{2}+\frac{n}{2}\cdot\frac{n(n+1)}{2}-\frac{n^3}{2}\\ &=\frac{n^2}{2}\left[\frac{n(n+1)+(n+1)-2n}{2}\right]\\ &=\frac{n^2}{2}\cdot\frac{n^2+1}{2}=\frac{1}{2}\sum_{k=1}^{n^2}k. \end{align}$

The problem was offered at the 2001 Putnam Competition and included into Ross Honsberger's Mathematical Delights (MAA, 2004, 46-47).

Solution 2 is by Amit Itagi; Solution 3 is by Alejandro Rodríguez.