MathLabs

Problem 2

Find all integers nn for which each cell of an n×nn\times n table can be filled with one of the letters II, MM, and OO in such a way that: in each row and each column, one third of the entries are II, one third are MM, and one third are OO; and in any diagonal, if the number of entries on the diagonal is a multiple of three, then one third of the entries on that diagonal are II, one third are MM, and one third are OO. (Note that an n×nn\times n table has 4n−24n-2 diagonals in total, in both directions.)
Step 3 of 5: Count II on the two diagonal families
Previous stepNext step
In plain words

The diagonal hypothesis gives exactly n2/9n^2/9 occurrences of II in each family. Their overlap is precisely the good II-cells.

∣D1∣=∣D2∣=19n2,∣D1∩D2∣=a|D_1|=|D_2|=\tfrac19n^2,\quad |D_1\cap D_2|=a
Detailed analysis

Let D1,D2D_1,D_2 be the sets of cells containing II on diagonals of the two directions whose lengths are multiples of 33. Every such diagonal is balanced, so ∣D1∣=∣D2∣=n2/9|D_1|=|D_2|=n^2/9. Their intersection consists exactly of the good II-cells, hence ∣D1∩D2∣=a|D_1\cap D_2|=a. Therefore ∣D1∪D2∣=2n2/9−a|D_1\cup D_2|=2n^2/9-a, and the number of II-cells in exactly one family is 2n2/9−2a2n^2/9-2a.