MathDB

Let

n \ge 2

be a positive integer. Each square of an n\times n board is coloured red or blue. We put dominoes on the board, each covering two squares of the board. A domino is called even if it lies on two red or two blue squares and colourful if it lies on a red and a blue square. Find the largest positive integer

k

having the following property: regardless of how the red/blue-colouring of the board is done, it is always possible to put

k

non-overlapping dominoes on the board that are either all even or all colourful.

Problem Statement