MathDB

Let

n

be a positive integer. Each cell of an

n \times n

table is coloured in one of

k

colours where every colour is used at least once. Two different colours

A

and

B

are said to touch each other, if there exists a cell coloured in

A

sharing a side with a cell coloured in

B

. The table is coloured in such a way that each colour touches at most

2

other colours. What is the maximal value of

k

in terms of

n

Problem Statement