MathDB

Let

n

be a positive integer. Each cell of a

2n\times 2n

square is painted in one of the

4n^2

colors (with some colors may be missing). We will call any two-cell rectangle a domino[/I], and a domino is called colorful[/I] if its cells have different colors. Let

k

be the total number of colorful dominoes in our square;

l

be the maximum integer such that every partition of the square into dominoes contains at least

l

colorful dominoes. Determine the maximum possible value of

4l-k

over all possible colourings of the square.

Problem Statement