IMO 2016 Problem 2

This year's IMO problems are out! The second one is combinatorics:

Find all integers n for which each cell of nxn table can be filled with one of the letters I, M, and O in such a way that: in each row and each column, one third of the entries are I, one third are M and one third are O; and in any diagonal, if the number of entries on the diagonal is a multiple of three, then one third of the entries are I, one third are M and one third are O.

Solution:

Initial attempts for n=3 and n=6 failed, making me wonder if no n satisfies the requirement. However by counting in two ways I got more clue.

To simplify thinking process let's see if it's even possible to just put letter O such that all columns, rows, and diagonals with length multiple of 3 have 1/3 of O. We can assign a binary varaible c(i,j) to cell (i,j) to indicate whether we put an O there.

Partition the table by 3x3 blocks. Let the sum of c over the 4 corner cells, center cell, and the rest 4 cells of all blocks be x, y, and z respectively.

Counting all columns and rows with index 3i+1 and 3i+3 we get 2x+z=4/9*n^2

Counting all columns and rows with index 3i+2 we get 2y+z=2/9*n^2

Counting all qualifying diagonals we get x+2y=2/9*n^2

(x,y,z)=n^2/27*(4, 1, 4), so the only possible n must be divisible by 9.

It is not too hard to find an easy construction for n=9, and see that it generalizes to all n divisible by 9:

IIIMMMOOO
MMMOOOIII
OOOIIIMMM
IIIMMMOOO
MMMOOOIII
OOOIIIMMM
IIIMMMOOO
MMMOOOIII
OOOIIIMMM