Detone M as the total number of dominoes on the board (aka. 2*(2n)(2n-1)), so the total number of non colourful dominoes is M-k. It’s quite easy to prove, that there exist 4 partitions of the board into dominoes such that every domino is present in at least one partition. What follows, is that one partition, has at least (M-k)/4 no colourful dominoes and hence l <= 2n^2 - (M-k)/4. Plugging this value in we get a desired inequality. It holds, for instance, when the whole board is coloured the same.

What is the answer?

Answer: $4n$ Notice that $4n$ is achieved when every cell is a different color, we now show it is the maximum. Consider the following four partitions (we set $n=4$ for illustration). [asy][asy] size(400, 200); pen gridPen = gray + linewidth(1); // Thicker gridlines pen borderPen = black + linewidth(1); // Black border for the dominoes pen dominoPen1 = lightgray; pen dominoPen2 = lightblue; pen dominoPen3 = lightgreen; pen dominoPen4 = lightyellow; // Function to draw an empty 8x8 grid at position (xShift, yShift) void drawGrid(real xShift, real yShift) { for (int i = 0; i <= 8; ++i) { draw((i + xShift, 0 + yShift) -- (i + xShift, 8 + yShift), gridPen); // Vertical lines draw((0 + xShift, i + yShift) -- (8 + xShift, i + yShift), gridPen); // Horizontal lines } } // First square: Vertically placed dominoes void verticalDominoes(real xShift, real yShift, pen fillColor) { drawGrid(xShift, yShift); // Draw grid first, so it's in the background for (int i = 0; i < 8; ++i) { for (int j = 0; j < 8; j += 2) { filldraw((i + xShift, j + yShift) -- (i + 1 + xShift, j + yShift) -- (i + 1 + xShift, j + 2 + yShift) -- (i + xShift, j + 2 + yShift) -- cycle, fillColor, borderPen); } } } // Second square: Horizontally placed dominoes void horizontalDominoes(real xShift, real yShift, pen fillColor) { drawGrid(xShift, yShift); // Draw grid first, so it's in the background for (int i = 0; i < 8; i += 2) { for (int j = 0; j < 8; ++j) { filldraw((i + xShift, j + yShift) -- (i + 2 + xShift, j + yShift) -- (i + 2 + xShift, j + 1 + yShift) -- (i + xShift, j + 1 + yShift) -- cycle, fillColor, borderPen); } } } // Third square: Vertical dominoes in the first and last columns, horizontal dominoes in the inner columns void shiftedVerticalAndHorizontalDominoes(real xShift, real yShift, pen fillColor) { drawGrid(xShift, yShift); // Draw grid first, so it's in the background // Fill the first and last columns with vertical dominoes for (int j = 0; j < 8; j += 2) { filldraw((0 + xShift, j + yShift) -- (1 + xShift, j + yShift) -- (1 + xShift, j + 2 + yShift) -- (0 + xShift, j + 2 + yShift) -- cycle, fillColor, borderPen); // First column filldraw((7 + xShift, j + yShift) -- (8 + xShift, j + yShift) -- (8 + xShift, j + 2 + yShift) -- (7 + xShift, j + 2 + yShift) -- cycle, fillColor, borderPen); // Last column } // Fill the inner columns with horizontal dominoes for (int i = 1; i < 7; i += 2) { for (int j = 0; j < 8; ++j) { filldraw((i + xShift, j + yShift) -- (i + 2 + xShift, j + yShift) -- (i + 2 + xShift, j + 1 + yShift) -- (i + xShift, j + 1 + yShift) -- cycle, fillColor, borderPen); } } } // Fourth square: Horizontal dominoes in the top and bottom rows, vertical dominoes in the inner rows void shiftedHorizontalAndVerticalDominoes(real xShift, real yShift, pen fillColor) { drawGrid(xShift, yShift); // Draw grid first, so it's in the background // Fill the top and bottom rows with horizontal dominoes for (int i = 0; i < 8; i += 2) { filldraw((i + xShift, 0 + yShift) -- (i + 2 + xShift, 0 + yShift) -- (i + 2 + xShift, 1 + yShift) -- (i + xShift, 1 + yShift) -- cycle, fillColor, borderPen); // Top row filldraw((i + xShift, 7 + yShift) -- (i + 2 + xShift, 7 + yShift) -- (i + 2 + xShift, 8 + yShift) -- (i + xShift, 8 + yShift) -- cycle, fillColor, borderPen); // Bottom row } // Fill the inner rows with vertical dominoes for (int i = 0; i < 8; ++i) { for (int j = 1; j < 7; j += 2) { filldraw((i + xShift, j + yShift) -- (i + 1 + xShift, j + yShift) -- (i + 1 + xShift, j + 2 + yShift) -- (i + xShift, j + 2 + yShift) -- cycle, fillColor, borderPen); } } } // Draw the four grids with different colors and black borders verticalDominoes(0, 0, dominoPen1); // First grid with lightgray dominoes (vertical) horizontalDominoes(10, 0, dominoPen2); // Second grid with lightblue dominoes (horizontal) shiftedVerticalAndHorizontalDominoes(0, -10, dominoPen3); // Third grid with mixed directions shiftedHorizontalAndVerticalDominoes(10, -10, dominoPen4); // Fourth grid with mixed directions [/asy][/asy] Each domino appears one time in these partitions, except for the $4n$ dominoes which lie along the border and who are at an 'even' position, which all appear twice. Thus there can be at most $k+4n$ colorful dominoes in these partitions. However these partitions must contain at least $4l$ colorful dominoes so $$4l\leq k+4n\iff 4l-k\leq 4n$$

I might be misunderstanding the problem, but if the grid is all one colour, shouldn't $k=l=0$?

Yes, you are right. It should be that every cell is colored with a different color. I fixed my mistake