3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ rot13(Guvf vf rdhvinyrag gb gvyvat gur 4k4 fdhner jvgu a pbybef fhpu gung ab gvyr unf n gnkvpno qvfgnapr bs 2 be yrff sebz n gvyr bs gur fnzr pbybe.) $\endgroup$ – Cloudy7 Jan 22 at 1:10
  • $\begingroup$ @Cloudy7 indeed that is true. $\endgroup$ – Dmitry Kamenetsky Jan 22 at 1:13
5
$\begingroup$

I think we need at least

5 colors.

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.

$\endgroup$
6
  • $\begingroup$ We both thought about this very similarly with the middle four cells being key, +1 :) $\endgroup$ – Beastly Gerbil Jan 22 at 1:17
  • $\begingroup$ Correct and well done! I think you were first by a few seconds. $\endgroup$ – Dmitry Kamenetsky Jan 22 at 1:25
  • 2
    $\begingroup$ Interestingly our example grids is the only possibility, (ignoring rotations). I’ve added a little bit of reasoning to my answer to explain why $\endgroup$ – Beastly Gerbil Jan 22 at 1:27
  • $\begingroup$ That is interesting indeed. Thank you. $\endgroup$ – Dmitry Kamenetsky Jan 22 at 1:34
  • 3
    $\begingroup$ I think an even easier way of showing we need 5 colors is to consider a 5-cell cross. All cells share a tromino with each other cell, so they all need a different color. $\endgroup$ – EagleV_Attnam Jan 22 at 12:13
3
$\begingroup$

The smallest $n$ will be

5

And here’s the grid (all possible grids will be mirrors and rotations of this):

enter image description here

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:

enter image description here

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.

$\endgroup$
2
$\begingroup$

The minimum is

5, attained as follows:

enter image description here

$\endgroup$
3
  • $\begingroup$ Sorry this is incorrect. The first 1x3 has two cells of the same colour. This only works for L-shaped trominoes. $\endgroup$ – Dmitry Kamenetsky Jan 22 at 1:16
  • $\begingroup$ This is wrong, I can from a straight tetromino of 3 cells in a row and have the same colour twice. For example the first three cells in the top row contain dark grey twice $\endgroup$ – Beastly Gerbil Jan 22 at 1:16
  • $\begingroup$ I corrected my answer. $\endgroup$ – RobPratt Jan 22 at 1:17

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.