IMO 2016 Problem 2

Discussion on International Mathematical Olympiad (IMO)
User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:
IMO 2016 Problem 2

Unread post by Phlembac Adib Hasan » Sun Aug 07, 2016 1:00 pm

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.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

User avatar
ahmedittihad
Posts:181
Joined:Mon Mar 28, 2016 6:21 pm

Re: IMO 2016 Problem 2

Unread post by ahmedittihad » Sun Jan 01, 2017 2:11 pm

\[
\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?
Frankly, my dear, I don't give a damn.

User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am

Re: IMO 2016 Problem 2

Unread post by Thanic Nur Samin » Mon Jan 02, 2017 1:54 pm

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$.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

Post Reply