Baltic Way 2019

No, it is not true. At first we note that $M(n)$ is a nondecreasing function and $M(n)\ge n$ for all $n\ge 2$ what follows from the fact that $6\times n$ rectangle can be cut into $n$ rectangles of size $2\times 3$, each of whom should contain a coloured cell.

Next we show that $M(n+1)\le M(n)+2$ for all $n\ge 2$. Assume that we have the minimal colouring for $6\times n$ grid (blue rectangle in the following figure) and we add one more column to the right. At least one of the red or green cells are coloured. If a red cell is coloured then colouring cells marked A and C will finish the minimal colouring for the $6\times (n+1)$ grid. If a green cell is coloured then colouring B and C is enough.

Neither 35 nor 36 can be expressed in the form $p+k^3$, where $p$ is a prime and $k$ is a nonnegative integer (just check $k\in \{0,1,2,3\}$). As $M(n)$ is an unbounded function which increases in each step by at most two, we will have that either $M(n)=35$ or $M(n)=36$ for some $n$.

Alternatively one can show, that $M(20)=22$, a simple check shows that 22 cannot be expressed in the form $p+k^3$. The following figure shows that 22 coloured cells are enough to cover a $6\times 20$ rectangle. To show that 21 coloured cell is insufficient we will show that $M(10)>10$. Assume, that $M(10)=10$ and notice that $6\times 10$ rectangle can be cut into four $3\times 5$ rectangles. Each $3\times 5$ rectangle should contain at least two coloured cells therefore there will be at least two $3\times 5$ rectangles containing exactly 2 coloured cells. The only way to colour two cells in a $3\times 5$ rectangle is as in the next figure (left), because both red and green squares can contain at most one coloured cell and the only way to colour a single cell in a $3\times 3$ square is to put it in the centre.

There is only one way how two cells can be colored in a $3\times 5$ rectangle (left); two $3\times 5$ rectangles with two coloured cells cannot be placed side by side (right). Now let's see how these two $3\times 5$ rectangles containing two coloured cells can be placed. If they are placed side by side then the red rectangle remains empty (the right figure above), similarly one can show that they cannot be placed one above another. But if they are placed diagonally then the following figure shows how seven $2\times 3$ rectangles can be placed in the remaining space each requiring at least one coloured cell.