Paint the cells of a 4x4 grid with 𝑛 colors, such that every possible tromino found in the grid uses 3 different colors. What is the smallest value of 𝑛 possible in such a coloring?
I think we need at least
with the example coloring of
4 5 2 3 3 1 4 5 5 2 3 1 1 4 5 2
where the colors 1, 2, 3, 4 occupy three cells each and the color 5 occupies four cells, and all the same colored cells are at least one knight's move apart.
To see this is the minimum, first consider
the center four cells. Every pair in this region is part of an L-tromino, so all four cells must have distinct colors.
Then, consider one of the colors used to color a center cell:
X X X ? X 1 X X X X X ? ? X ? ?
In this situation, the only way to color four cells with 1 is the following:X X X 1 X 1 X X X X X X 1 X X 1
Obviously, this cannot be done for all four colors, which means we can't cover 16 cells with four colors.
Therefore, we conclude that
it is impossible to color the grid with four colors, so we need at least 5 colors, which is achieved with the top grid.
The smallest $n$ will be
And here’s the grid (all possible grids will be mirrors and rotations of this):
This is because
It is immediately obvious the middle 4 must all be different colours. So $n$ already cannot be less than 4, and we have this grid:
But now we have the same in each corner. Each corner must have at least 4 colours, but they are restricted by the middle.
For instance, in the bottom right hand corner, blue would have to go bottom right cell. Green then cannot go in either without a tromino containing two greens.
Therefore $n$ is at least 5, and this can be easily achieved as shown in the example grid.
Now to find the grid
We know there must be one extra colour. Each other colour can only fill 2 others, in a knights move pattern. So the fifth colour will have to fill 4 cells. The only way to add this in a way that works is in the pattern of the orange. The rest of the colours can then only fill in that one way.