Problem

Source: Latvia TST for Baltic Way 2020 P6

Tags: combinatorics



For a natural number $n \ge 3$ we denote by $M(n)$ the minimum number of unit squares that must be coloured in a $6 \times n$ rectangle so that any possible $2 \times 3$ rectangle (it can be rotated, but it must be contained inside and cannot be cut) contains at least one coloured unit square. Is it true that for every natural $n \ge 3$ the number $M(n)$ can be expressed as $M(n)=p_n+k_n^3$, where $p_n$ is a prime and $k_n$ is a natural number?