Problem 308

Solution:
The following diagram is the entire $16 \times 16$ groovy grid computed out. However, one will not need to write out every single entry to obtain the answer.

| 16 | 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| 15 | 16 | 13 | 14 | 11 | 12 | 9 | 10 | 7 | 8 | 5 | 6 | 3 | 4 | 1 | 2 |
| 14 | 13 | 16 | 15 | 10 | 9 | 12 | 11 | 6 | 5 | 8 | 7 | 2 | 1 | 4 | 3 |
| 13 | 14 | 15 | 16 | 9 | 10 | 11 | 12 | 5 | 6 | 7 | 8 | 1 | 2 | 3 | 4 |
| 12 | 11 | 10 | 9 | 16 | 15 | 14 | 13 | 4 | 3 | 2 | 1 | 8 | 7 | 6 | 5 |
| 11 | 12 | 9 | 10 | 15 | 16 | 13 | 14 | 3 | 4 | 1 | 2 | 7 | 8 | 5 | 6 |
| 10 | 9 | 12 | 11 | 14 | 13 | 16 | 15 | 2 | 1 | 4 | 3 | 6 | 5 | 8 | 7 |
| 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 16 | 15 | 14 | 13 | 12 | 11 | 10 | 9 |
| 7 | 8 | 5 | 6 | 3 | 4 | 1 | 2 | 15 | 16 | 13 | 14 | 11 | 12 | 9 | 10 |
| 6 | 5 | 8 | 7 | 2 | 1 | 4 | 3 | 14 | 13 | 16 | 15 | 10 | 9 | 12 | 11 |
| 5 | 6 | 7 | 8 | 1 | 2 | 3 | 4 | 13 | 14 | 15 | 16 | 9 | 10 | 11 | 12 |
| 4 | 3 | 2 | 1 | 8 | 7 | 6 | 5 | 12 | 11 | 10 | 9 | 16 | 15 | 14 | 13 |
| 3 | 4 | 1 | 2 | 7 | 8 | 5 | 6 | 11 | 12 | 9 | 10 | 15 | 16 | 13 | 14 |
| 2 | 1 | 4 | 3 | 6 | 5 | 8 | 7 | 10 | 9 | 12 | 11 | 14 | 13 | 16 | 15 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |

We prove the following key claim.

Claim 1. In the $2^{n} \times 2^{n}$ groovy grid, each row and column is a permutation of the numbers from $1$ to $2^{n}$.

Proof. We use induction on $n$. The base case $n=0$ is clear. Now, assume that we know this for a $2^{n} \times 2^{n}$ groovy grid, and we will prove it for a $2^{n+1} \times 2^{n+1}$ grid. To that end, we divide the $2^{n+1} \times 2^{n+1}$ grid into four subgrids of size $2^{n} \times 2^{n}$.

The subgrid labeled $A$ is the groovy grid of size $2^{n} \times 2^{n}$, so by induction, each row and column is a permutation of $\{1, \ldots, 2^{n}\}$. Thus, the bottom left corner of the subgrid labeled $B$ is $2^{n}+1$, and so the subgrid labeled $B$ is the groovy grid where each entry is added by $2^{n}$. Hence, by induction hypothesis, each row and column of the subgrid labeled $B$ is a permutation of $\{2^{n}+1,2^{n}+2, \ldots, 2^{n}+2^{n}\}$. The same argument applies for the subgrid labeled $C$.

Finally, the subgrid labeled $D$ has enough numbers from $1,2, \ldots, 2^{n}$ and does not need any number greater than $2^{n}$. The bottom left corner is $1$. Hence, it must be a groovy grid. Thus, the induction hypothesis applies, and each row and column of the subgrid labeled $D$ is a permutation of $\{1,2, \ldots, 2^{n}\}$. By considering all subgrids together, we find that each row and column of the entire grid is a permutation of $\{1,2, \ldots, 2^{n+1}\}$.

In particular, we have that every row and column of the $16 \times 16$ grid is a permutation of $\{1,2, \ldots, 16\}$. To compute the sum of entries of the $14 \times 14$ grid, we can take out $2$ rows and $2$ columns and add back the top right $2 \times 2$ which we know entries $1,2,2,1$ by following the proof of the claim. This gives the final answer of
$$16 \cdot \frac{16 \cdot 17}{2}-2 \cdot \frac{16 \cdot 17}{2}-2 \cdot \frac{16 \cdot 17}{2}+(1+2+2+1)=1638.$$