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.
$\begingroup$
$\endgroup$
asked Jan 22, 2021 at 1:24
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
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.)
-
$\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$– BubblerJan 22, 2021 at 1:41
-
$\begingroup$ Nicely done! Interesting that this can tile the plane. $\endgroup$ Jan 22, 2021 at 13:36
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
2
The minimum is
8, attained as follows:
-
$\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$– BubblerJan 22, 2021 at 2:12
-