mathematics - Coloring an n by n grid with four colors

This is a generalization of Place 4x12 detainees on a 7x7 grid of cells.

---

The goal is to color the squares of an $n\times n$ grid with four colors such that

• 
  

  at most one square is uncolored

  
  


• 
  
  

  no two squares of the same color touch at an edge or corner

  
  


• 
  

  there are an equal number of squares of each color.

  
  

For which values of $n$ is this possible?

Answer

$n$ even

A solution is possible for

all even $n$.

Proof is as follows.

Let the four colours be A, B, C, D, and simply alternate AB-rows with CD-rows while alternating A,B and C,D within each row. For instance:

A B A B A B A B
C D C D C D C D
A B A B A B A B

C D C D C D C D
A B A B A B A B
C D C D C D C D
A B A B A B A B
C D C D C D C D

This fills in all cells of the $n\times n$ square, uses each colour exactly the same number of times, and no two same-colour squares touch at edge or corner.

$n$ odd

A solution is possible for

all odd $n$.

Proof is as follows.

$n=3$ was already covered in the question, so we start with the following solution for $n=5$:

A B C D C
C D A B A
A B   C D
D C D A B
B A B C D

Then simply extend this solution outwards by continuing each row and column in a pattern of the form ABAB... or BABA... or CDCD... or ACAC... or whatever, according to the way that row or column has already started when reading from the centre outwards.

• For instance, how do we extend the first row to the right? We read rightwards from the centre column: D, C, so the next one must be D, then C again, and so on.
  


• How do we extend the second column downwards? Again, read downwards from the centre row: C, A, so the next one must be C, then A again, and so on.

The corners are then filled in in the only way they can be: once the rest of the $2\times2$ square starting from that corner are filled in, there's only one way the corner can be done.

E.g. for $n=7$, this construction works as follows:

                     C D A B A            D C D A B A B
A B C D C          B A B C D C D          B A B C D C D
C D A B A          D C D A B A B          D C D A B A B
A B   C D   --->   B A B   C D C   --->   B A B   C D C
D C D A B          C D C D A B A          C D C D A B A

B A B C D          A B A B C D C          A B A B C D C
                     D C D A B            C D C D A B A

How did I find this? (SPOILERS)

Well, let's start with $n=5$. Now we know that every $2\times2$ square must contain exactly one cell of each colour. WLOG, let's say the top row starts off with AB and the second row starts with CD. That means the third row must start with C and D, the fourth with A and B, the fifth with C and D (in each case, the order is unknown). So maybe we have something like this:

A B * * *
C D * * *
A B   * * 
C D * * * 
A B * * *

That takes care of the left-hand side of the square. The right-hand side must be filled in in the same pattern, up to some relabelling of the four colours. But the left-hand side contains three A's and B's and only four C's and D's. To maintain symmetry between the four colours, we'll want to right-hand side to reverse these counts. So (again, up to reordering of adjacent pairs) we have:

A B * C D
C D * A B
A B   C D 
C D * A B 
A B * C D

Now there are five of each colour filled in, so the remaining four cells must contain exactly one of each. But if those AB pairs on the left are all aligned the same way, then none of those four can be B; similarly, if the CD pairs on the left are both aligned the same way, then none of them can be D; and similarly for the pairs on the right. So we need to swap some pairs. How about this?

A B * D C
C D * B A
A B   C D 
D C * A B 

B A * C D

Now there's exactly one way to fill in those four remaining cells, which gives us the solution written above for $n=5$.

For $n=7$, we could apply much the same argument starting with something like

A B A * C D C
C D C * A B A
A B A * C D C
C D C   A B A
A B A * C D C
C D C * A B A
A B A * C D C

and changing ABA's and CDC's to BAB's and DCD's as required before filling in the central column. I was going to try to construct a general argument along these lines for odd $n$ (perhaps splitting into separate cases for $n\equiv1\;(mod\;4)$ and $n\equiv3\;(mod\;4)$) when I noticed that the solution we already have for $n=5$ can be thought of as a central cross with something like the solution for even $n$ extending out in each direction from there:

   . . | . .
   : : | : :
...A B | D C...
...C D | B A...
------   ------
...D C | A B...
...B A | C D...
   : : | : :
   . . | . .

... and that this extension outwards from the centre cross can be used to construct a solution for all odd $n$ simply by extending further and further, one outer layer at a time.