MathDB
Problems
Contests
International Contests
Baltic Way
2023 Baltic Way
6
6
Part of
2023 Baltic Way
Problems
(1)
Colored grid
Source: Baltic Way 2023/6
11/11/2023
Let
n
n
n
be a positive integer. Each cell of an
n
×
n
n \times n
n
×
n
table is coloured in one of
k
k
k
colours where every colour is used at least once. Two different colours
A
A
A
and
B
B
B
are said to touch each other, if there exists a cell coloured in
A
A
A
sharing a side with a cell coloured in
B
B
B
. The table is coloured in such a way that each colour touches at most
2
2
2
other colours. What is the maximal value of
k
k
k
in terms of
n
n
n
?
combinatorics