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: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:
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.