2016 IMO Problems/Problem 2

Problem

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.

Solution

This problem needs a solution. If you have a solution for it, please help us out by adding it.

Here is a solution using counting in two ways.

It's obvious that $3 \mid n$ . We consider all the squares indexed $(3k+2,3l+2)$ and call it [i]good[/i] square. Let $a$ be number of [i]good[/i] squares that are filled with $I$ . We can see that every good square lies on both type of diagonals. So if we call $D_1,D_2$ be the set of all squares in first type, second type of diagonal that are filled with $I$ , respectively. We will have $|D_1 \cap D_2|=a$ and $|D_1|=|D_2|= \tfrac 19 n^2$ . Hence, $|D_1 \cup D_2|=|D_1|+|D_2|+|D_1 \cap D_2|= \tfrac 29 n^2-a.$ Hence, number of squares filled with $I$ that either lie on first type of diagonal or second type but not in both is $\tfrac 29 n^2-2a$ .

Now, these squares counted above doesn't fill the columns indexed $3k+2$ and rows indexed $3k+2$ . So we need to fill these squares with $I$ . Let $C$ be the set of squares in columns indexed $3k+2$ that are filled with $I$ , similar to set $R$ of rows indexed $3k+2$ . We have $|C \cup R|=|C|+|R|-|C \cap R|= \tfrac 29 n^2-a.$

From these, we find that the total number of squares filled with $I$ is $\tfrac 49 n^2-3a$ . Note that this is also equal to $\tfrac 13 n^2$ so this means $3a= \tfrac 19 n^2$ implies $9 \mid n$ , which is the final answer.

This argument gives us a way to construct a $9 \times 9$ table, which is first we fill all the [i]good[/i] squares in a way such that one third of them are $I$ , one third are $O$ and one third are $M$ . After that, we fill all the diagonals and then fill the remain squares.

2016 IMO (Problems) • Resources
Preceded by Problem 1	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 3
All IMO Problems and Solutions

Page

Toolbox

Search

2016 IMO Problems/Problem 2

Problem

Solution

See Also