AMC 2011 Coloring Problem

User Samwise posted a solution with $420$ red squares at this Yahoo link 9 years ago. The idea is to start at the top left, and write the pattern R R w w in a spiral, leaving a blank row between consecutive turns of the spiral. Here it is for a $16\times 16$ board:

R R w w R R w w R R w w R R w w    8
. . . . . . . . . . . . . . . R    1
w w R R w w R R w w R R w w . R    7
R . . . . . . . . . . . . R . w    2
R . w w R R w w R R w w . R . w    6
w . R . . . . . . . . R . w . R    3
w . R . w w R R w w . R . w . R    5
R . w . R . . . . R . w . R . w    4
R . w . R . w . . R . w . R . w    4
w . R . w . R R w w . R . w . R    5
w . R . w . . . . . . R . w . R    3
R . w . R R w w R R w w . R . w    6
R . w . . . . . . . . . . R . w    2
w . R R w w R R w w R R w w . R    7
w . . . . . . . . . . . . . . R    1
R R w w R R w w R R w w R R w w    8

On the right are the numbers of red squares in each row. They add up to $8\cdot 9=72$ (note that the odd-numbered rows decrease from $8$ to $1$, and the even-numbered rows increase from $1$ to $8$). For a $40\times 40$ board, we get $20\cdot 21=420$ red squares.

In fact this procedure works for a square board of any size. Here it is for a $9\times 9$ board:

R R w w R R w w R    5
. . . . . . . . R    1
w w R R w w R . w    3
R . . . . . R . w    2
R . w w R . w . R    3
w . R . . . w . R    2
w . R w w R R . w    3
R . . . . . . . w    1
R w w R R w w R R    5

There are $25$ red squares. In general, for an even-sized board of size $2n$ we get $n(n+1)$ red squares; and for an odd sized board of size $2n+1$ we get $(n+1)^2$ red squares if $n$ is even and $n(n+2)$ if $n$ is odd.

It still remains to be shown whether these patterns are the best possible.

In a separate answer, user TonyK has shown that it is possible to have as many as $420$ red squares on the board, and that it remains to show that the number of red squares is strictly less than $421$. Below I will complete the proof by showing that the number of red squares must be strictly less than $421$. To see how it is possible to have $420$ red squares, you can look at user TonyK's answer, or you can click the link in his answer, which will take you to this website on Yahoo.

Suppose we have a $40\times40$ white board, and we color some of the squares red, so that each square shares a side with at most one red square. Let $R$ be the number of red squares. It has been shown that there is a way of doing this with $R=420$. Our goal is to show that $R<421$.

Since the board is $40\times40$, the board consists of $1600$ $1\times1$ squares. Let $\mathcal{S}$ be the set of all $1600$ of these $1\times1$ squares. For each $x\in\mathcal{S}$, let $f(x)$ be the number of red squares that share a side with $x$. We'll start be examining the sum

$$\sum_{x\in\mathcal{S}}f(x).$$

The number of times a red square is counted in this sum depends on whether the red square is a corner square, an edge square, or an interior square. So let $C$ be the number of red corner squares. Let $E$ be the number of red edge squares, and let $I$ be the number of red interior squares. In the above sum, red corner squares are counted twice; red edge squares are counted three times, and red interior squares are counted four times. Hence

$$\sum_{x\in\mathcal{S}}f(x)=2C+3E+4I.$$

Since each squares shares a side with at most one red square, we have that $f(x)\le1$ for each $x\in\mathcal{S}$. So

$$\sum_{x\in\mathcal{S}}f(x)\le1600.$$

Hence $2C+3E+4I\le1600$. We want to maximize $R=C+E+I$ subject to the constraint that $2C+3E+4I\le1600$. We haven't gotten enough information yet to show that $R<421$ so we will have to examine the problem further to come up with some additional constraints.

We can get the constraints we need by considering the squares on the border of the board, i.e. the corner and edge squares. In user TonyK's answer, it is shown that is possible to have as many as $78$ red squares on the border. This is done by working your way around the border, coloring two squares red and then leaving two squares white, until half the border is red. If the border had more than $78$ red squares, then it follows from the pigeon-hole principle that there would be $4$ consecutive border squares, $3$ of which are red, which would contradict the fact that no square shares a side with more than one red square. Hence $C+E\le78$.

For our last constraint, we can use the fact that there are four corners. So $C\le4$.

So we want to maximize

$$R=C+E+I$$

given that

$$2C+3E+4I\le1600$$ $$C+E\le78$$ $$C\le4$$ $$C,E,I\ge0.$$

Readers familiar with linear programming will recognize that this a problem that can be solved with the simplex method. However, our goal is just to show that $R<421$, which can be done without the simplex method. If we add the the three $\le$ constraints, we get that $4C+4E+4I\le1682$.

Hence $R=C+E+I\le\frac{1681}{4}=420.5.\;$ So $R<421$. $\;\square$

Acknowledgments: I would like to thank user TonyK for showing me that it was possible to have $R=420$. Without his help, I may not have been to get this problem. I would also like to thank user Rob Pratt, who provided a substantial simplification.

Closing Remark: If we modify the problem slightly, then the configuration mentioned in the original problem will in fact be optimal. Suppose that the original $40\times40$ board were inscribed on a torus instead of a just a $40\times40$ square. Now the squares on the bottom row share sides with squares on the top row, and squares on the leftmost column share sides with squares on the rightmost column. It follows that

$$\sum_{x\in\mathcal{S}}f(x)=4R.$$

Hence $R\le400$. So the configuration mentioned in the original problem would be optimal.