Question

On an arbitrarily large rectangular table, \(n\) cells are given. Prove that it is possible to colour these cells with two colours (red and blue) so that in each row or column the number of red squares differs from the number of blue squares by at most 1 .

Answer 1

The statement is trivial for \(n=0\) or \(n=1\) (the word "trivial" should be used with great care, but here it might be appropriate). For larger values of \(n\), we distinguish three cases:

1. Four of the given cells form a rectangle. Then we colour all the other cells according to our rule (which is possible by the induction hypothesis) and colour two diagonally opposite cells of the rectangle red and the others blue, which yields a feasible colouring.

2. Three of the given cells are the corners of a rectangle (the fourth is not among the given cells). Remove these three cells, add the fourth corner of the rectangle instead, and colour the cells according to the induction hypothesis. If the added cell is red (blue), we colour the adjacent corners of the rectangle red (blue) and the opposite corner blue (red), which again yields a feasible colouring.

3. If none of the above cases applies, choose any row or column that contains more than one given cell (if there is no such row or column, we can colour the cells arbitrarily). The squares of this row (column) are coloured in such a way that the number of red cells differs from the number of blue cells by at most 1. All the other cells are unaffected, so that we can colour them in a feasible way according to the induction hypothesis again.