1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

We can achieve

8 colors

with the following pattern:

enter image description here

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.

enter image description here

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

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

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.

$\endgroup$
1
$\begingroup$

The minimum is

8, attained as follows:

enter image description here

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – Bubbler Jan 22 at 2:12
  • $\begingroup$ I added numbers. $\endgroup$ – RobPratt Jan 22 at 2:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.