Decomposition of Bicolored Square Arrays into Bichromatic Diagonals

摘要

Let M be an nxn array (n>2), where each of its cells is colored in one of two colors. We give a necessary and sufficient condition for the existence of a partition of M into n diagonals, each containing at least one cell of each color. As a consequence, it follows that if each color appears in at least 2n-1 cells, then such a partition exists. The proof uses results on completion of partial Latin squares.