IMO 2016 Shortlisted Problems

We first show that such a table exists when $n$ is a multiple of $9$. Consider the following $9\times 9$ table. $$\left(\begin{array}{ccccccccc}I& I& I& M& M& M& O& O& O\\ M& M& M& O& O& O& I& I& I\\ O& O& O& I& I& I& M& M& M\\ I& I& I& M& M& M& O& O& O\\ M& M& M& O& O& O& I& I& I\\ O& O& O& I& I& I& M& M& M\\ I& I& I& M& M& M& O& O& O\\ M& M& M& O& O& O& I& I& I\\ O& O& O& I& I& I& M& M& M\end{array}\right)$$ It is a direct checking that the table (1) satisfies the requirements. For $n=9k$ where $k$ is a positive integer, we form an $n\times n$ table using $k\times k$ copies of (1). For each row and each column of the table of size $n$, since there are three $I$'s, three $M$'s and three $O$'s for any nine consecutive entries, the numbers of $I$, $M$ and $O$ are equal. In addition, every diagonal of the large table whose number of entries is divisible by $3$ intersects each copy of (1) at a diagonal with number of entries divisible by $3$ (possibly zero). Therefore, every such diagonal also contains the same number of $I$, $M$ and $O$.

Next, consider any $n\times n$ table for which the requirements can be met. As the number of entries of each row should be a multiple of $3$, we let $n=3k$ where $k$ is a positive integer. We divide the whole table into $k\times k$ copies of $3\times 3$ blocks. We call the entry at the centre of such a $3\times 3$ square a vital entry. We also call any row, column or diagonal that contains at least one vital entry a vital line. We compute the number of pairs ($l$, $c$) where $l$ is a vital line and $c$ is an entry belonging to $l$ that contains the letter $M$. We let this number be $N$.

On the one hand, since each vital line contains the same number of $I$, $M$ and $O$, it is obvious that each vital row and each vital column contain $k$ occurrences of $M$. For vital diagonals in either direction, we count there are exactly $$1+2+\cdots +(k-1)+k+(k-1)+\cdots +2+1=k^2$$ occurrences of $M$. Therefore, we have $N=4k^2$.

On the other hand, there are $3k^2$ occurrences of $M$ in the whole table. Note that each entry belongs to exactly $1$ or $4$ vital lines. Therefore, $N$ must be congruent to $3k^2\mathrm{mod}3$.

From the double counting, we get $4k^2\equiv 3k^2(\mathrm{mod}3)$, which forces $k$ to be a multiple of $3$. Therefore, $n$ has to be a multiple of $9$ and the proof is complete.