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.
Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this communityWe 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 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.