examday

/TMUA

An array has $5$ labelled rows and $4$ labelled columns. Each of its $20$ cells is coloured red or blue.

Whenever two distinct rows and two distinct columns are chosen, the four cells at their intersections must not all be the same colour.

A proof that there are exactly $720$ such colourings has been split into five blocks. Two colourings are different if at least one labelled cell has a different colour.

• I. Both necessity and sufficiency have now been established. Assign five different patterns to the five labelled rows in $6\times5\times4\times3\times2=720$ ways.
• II. An all-blue row forces every other row to have at least three red cells, so two of those rows share two red columns. A row with one red cell forces each of the other four rows to have at least two red cells in its three blue columns. Among the three pairs of those columns, two of the four rows must share a red pair. Both cases give a forbidden rectangle. Interchanging colours also rules out all-red rows and rows with three red cells. Thus every row has two cells of each colour.
• III. This last necessary condition is also sufficient: two different balanced row patterns cannot share both red positions or both blue positions, so choosing different patterns creates no monochromatic rectangle.
• IV. Each row must therefore be one of the six patterns with exactly two red positions among four labelled columns.
• V. Of these six patterns, no one can appear in two rows, because their two red positions would give a forbidden rectangle. Hence a valid colouring must use five distinct patterns.

Which ordering gives a complete proof, with every reference to an earlier conclusion justified when it is used?