Page 1 of 1

IMO 2016 Problem 2

Posted: Sun Aug 07, 2016 1:00 pm
by Phlembac Adib Hasan
Find all integers $n$ for which each cell of $n \times n$ 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$.
Note. The rows and columns of an $n \times n$ table are each labelled $1$ to $n$ in a natural order. Thus each cell corresponds to a pair of positive integer $(i,j)$ with $1 \le i,j \le n$. For $n>1$, the table has $4n-2$ diagonals of two types. A diagonal of first type consists all cells $(i,j)$ for which $i+j$ is a constant, and the diagonal of this second type consists all cells $(i,j)$ for which $i-j$ is constant.

Re: IMO 2016 Problem 2

Posted: Sun Jan 01, 2017 2:11 pm
by ahmedittihad
\[
\begin{array}{|ccc|ccc|ccc|}
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}
\]
I could only show that $9$ divides $n$. No idea about the other part. How many points would that give me?

Re: IMO 2016 Problem 2

Posted: Mon Jan 02, 2017 1:54 pm
by Thanic Nur Samin
Here is a proof that $9|n$ is necessary (see ahmedittihad's post for sufficiency).

It's obvious that $n=3k$. Now, Replace $I$ with $1$, $M$ with $\omega$ and $O$ with $\omega^2$. Now, sum the numbers in the:

1. Rows that are of the form $3m+2$.

2. Columns that are the form $3m+2$.

3. All diagonals of both types that have number of cells divisible by $3$.

Note that while all of them are $0$, The sum of whole grid is $0$ and summing the three of them would result in the sum of the whole board plus twice the sum of the central squares when the whole grid is divided into $3\times 3$ parts. So, their sum is also 0. Assume that there are $a$ $I$'s, $b$ $M$'s and $c$ $O$'s in the central squares. So, we get:
$$a+b+c=k^2$$
$$a+b\omega+c\omega^2=0$$

Implying that $(a-b)^2+(b-c)^2+(c-a)^2=0$, From which we get $3|k$ and so $9|n$.