Problem

Source:

Tags: combinatorics, Coloring



Each cell of a $10 \times 10$ board is painted red, blue or white, with exactly twenty of them red. No two adjacent cells are painted in the same colour. A domino consists of two adjacent cells, and it is said to be good if one cell is blue and the other is white. (a) Prove that it is always possible to cut out $30$ good dominoes from such a board. (b) Give an example of such a board from which it is possible to cut out $40$ good dominoes. (c) Give an example of such a board from which it is not possible to cut out more than $30$ good dominoes.