4. We place the numbers 1 through 9 one by one in a $3 \times 3$ grid. The number 1 can be placed in any cell; each subsequent number must be placed in a cell that is horizontally or vertically adjacent to the cell containing the previous number. See the example picture below. We call such a grid a snake grid. The score of a cell in a snake grid is the sum of the numbers in all cells that share a side with it. The total score of a snake grid is the sum of the scores of all its cells.

| 1 | 2 | 9 |
| :---: | :---: | :---: |
| 4 | 3 | 8 |
| 5 | 6 | 7 |

In the example snake grid (adding row by row, from left to right), the total score is $6+13+10+9+20+19+10+15+14=116$.

How many possible total scores can such a snake grid have?
A) 1
B) 2
C) 3
D) 4
E) 5
A4. E) 5

We color the cells of the $3 \times 3$ grid alternately gray and white and assign each cell a letter, as shown in the figure below. A snake always alternates between the white and gray cells, and thus alternates between even and odd numbers. Since there are five odd numbers and five white cells, the odd numbers will be placed on the white cells, at positions $a, c, e, g$, and $i$. We calculate the total score of this grid as follows:

| $a$ | $b$ | $c$ |
| :--- | :--- | :--- |
| $d$ | $e$ | $f$ |
| $g$ | $h$ | $i$ |

$$
\begin{array}{r}
(b+d)+(a+e+c)+(b+f)+(a+e+g)+(b+d+f+h) \\
+(c+e+i)+(d+h)+(e+g+i)+(f+h) \\
=2(a+b+c+d+e+f+g+h+i)+(b+d+f+h)+2 e
\end{array}
$$

This is equal to twice the sum of all numbers, plus the sum of all even numbers, plus twice $e$. The first two terms are the same for every snake. The total score of the grid thus depends only on the number that ends up in position $e$. This is an odd number, as we have already seen, and there are five possibilities for it. The examples below show that each odd number can indeed end up in the middle.

| 5 | 4 | 3 |
| :---: | :---: | :---: |
| 6 | 1 | 2 |
| 7 | 8 | 9 |


| 1 | 2 | 9 |
| :---: | :---: | :---: |
| 4 | 3 | 8 |
| 5 | 6 | 7 |


| 1 | 2 | 3 |
| :---: | :---: | :---: |
| 6 | 5 | 4 |
| 7 | 8 | 9 |


| 1 | 2 | 3 |
| :---: | :---: | :---: |
| 8 | 7 | 4 |
| 9 | 6 | 5 |


| 1 | 2 | 3 |
| :---: | :---: | :---: |
| 8 | 9 | 4 |
| 7 | 6 | 5 |