Difference between revisions of "2016 IMO Problems/Problem 2"

(Solution)
 
Line 11: Line 11:
 
==Solution==
 
==Solution==
 
{{solution}}
 
{{solution}}
 +
 +
Here is a solution using counting in two ways.
 +
 +
It's obvious that <math>3 \mid n</math>. We consider all the squares indexed <math>(3k+2,3l+2)</math> and call it [i]good[/i] square. Let <math>a</math> be number of [i]good[/i] squares that are filled with <math>I</math>. We can see that every good square lies on both type of diagonals. So if we call <math>D_1,D_2</math> be the set of all squares in first type, second type of diagonal that are filled with <math>I</math>, respectively. We will have <math>|D_1 \cap D_2|=a</math> and <math>|D_1|=|D_2|= \tfrac 19 n^2</math>. Hence, <cmath>|D_1 \cup D_2|=|D_1|+|D_2|+|D_1 \cap D_2|= \tfrac 29 n^2-a.</cmath>
 +
Hence, number of squares filled with <math>I</math> that either lie on first type of diagonal or second type but not in both is <math>\tfrac 29 n^2-2a</math>.
 +
 +
Now, these squares counted above doesn't fill the columns indexed <math>3k+2</math> and rows indexed <math>3k+2</math>. So we need to fill these squares with <math>I</math>. Let <math>C</math> be the set of squares in columns indexed <math>3k+2</math> that are filled with <math>I</math>, similar to set <math>R</math> of rows indexed <math>3k+2</math>. We have <cmath>|C \cup R|=|C|+|R|-|C \cap R|= \tfrac 29 n^2-a.</cmath>
 +
 +
From these, we find that the total number of squares filled with <math>I</math> is <math>\tfrac 49 n^2-3a</math>. Note that this is also equal to <math>\tfrac 13 n^2</math> so this means <math>3a= \tfrac 19 n^2</math> implies <math>9 \mid n</math>, which is the final answer.
 +
 +
This argument gives us a way to construct a <math>9 \times 9</math> table, which is first we fill all the [i]good[/i] squares in a way such that one third of them are <math>I</math>, one third are <math>O</math> and one third are <math>M</math>. After that, we fill all the diagonals and then fill the remain squares.
  
 
==See Also==
 
==See Also==
  
 
{{IMO box|year=2016|num-b=1|num-a=3}}
 
{{IMO box|year=2016|num-b=1|num-a=3}}

Latest revision as of 13:37, 4 December 2024

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.

See Also

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