# 5x5 grid with no tetrominoes containing repeating colors

Paint the cells of a 5x5 grid with 𝑛 colors, such that every possible tetromino found in the grid uses 4 different colors. What is the smallest value of 𝑛 possible in such a coloring?

Here is a similar question for trominoes in a 4x4 grid.

## 3 Answers

We can achieve

8 colors

with the following pattern:

This is optimal because:

In the portion of the grid highlighted below, all eight cells must be distinct colors, since each of them is within 3 steps of all the others.

(In fact, this pattern can tile the plane - there's no need to restrict it to a 5×5 grid.)

• I failed to notice the specific shape at first, so I went a long-winded way. Also interesting that the final results are different. – Bubbler Jan 22 at 1:41
• Nicely done! Interesting that this can tile the plane. – Dmitry Kamenetsky Jan 22 at 13:36

I think the answer is

8 colors

which can be achieved by coloring the grid like this:

1 4 8 3 1
5 6 2 7 4
8 3 1 5 8
2 7 4 6 3
1 5 8 2 1

First, consider the

plus-shaped region of 5 cells in the center. Every pair in this region is part of a T-tetromino, so we use 5 colors here.

? ? ? ? ?
? ? 2 ? ?
? 3 1 5 ?
? ? 4 ? ?
? ? ? ? ?

Then consider the

center 3x3 region. All the pairs except the opposite corners are part of some tetromino, so we need two more colors here.

? ? ? ? ?
? 6 2 7 ?
? 3 1 5 ?
? 7 4 6 ?
? ? ? ? ?

Finally, consider the

cell on the middle of a side of the grid. For all sides, the cell can be part of a tetromino with all seven colors already used, so it must have the 8th color:

? ? ? ? ?
? X X 7 ?
8 X X X ?
? X X 6 ?
? ? ? ? ?

The rest can be filled as in the top grid.

The minimum is

8, attained as follows:

• Lighter colors are not easily distinguishable. I guess you could add a 3rd color hue (something like yellow or green) or annotate with letters/numbers. – Bubbler Jan 22 at 2:12
• I added numbers. – RobPratt Jan 22 at 2:18