AMC 2011 Coloring Problem

coloringcontest-math

A 40 X 40 white square is divided into 1 X 1 squares by lines parallel to its sides. Some of these 1 X 1 squares are coloured red so that each of the 1 X 1 squares, regardless of whether it is coloured red or not, shares a side with at most one red square (not counting itself). What is the largest possible number of red squares?

What I did is as following(R is red, w is white), There are only 400 red squares. The answer should be more. (Sorry, the previous diagram was wrong, I missed every empty White lines. Now I fixed it. ):
RRwwRRwwRRww...RRww
wwwwwwwwwwww...wwww
wwRRwwRRwwRR...wwRR
wwwwwwwwwwww...wwww
RRwwRRwwRRww...RRww
wwwwwwwwwwww...wwww
wwRRwwRRwwRR...wwRR
...................
RRwwRRwwRRww...RRww
wwwwwwwwwwww...wwww
wwRRwwRRwwRR...wwRR
wwwwwwwwwwww...wwww

Best Answer

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.

Related Question