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 for which each cell of
table can be filled with one of the letters
and
in such a way that:
|
Note. The rows and columns of an table are each labelled
to
in a natural order. Thus each cell corresponds to a pair of positive integer
with
. For
, the table has
diagonals of two types. A diagonal of first type consists all cells
for which
is a constant, and the diagonal of this second type consists all cells
for which
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 . We consider all the squares indexed
and call it [i]good[/i] square. Let
be number of [i]good[/i] squares that are filled with
. We can see that every good square lies on both type of diagonals. So if we call
be the set of all squares in first type, second type of diagonal that are filled with
, respectively. We will have
and
. Hence,
Hence, number of squares filled with
that either lie on first type of diagonal or second type but not in both is
.
Now, these squares counted above doesn't fill the columns indexed and rows indexed
. So we need to fill these squares with
. Let
be the set of squares in columns indexed
that are filled with
, similar to set
of rows indexed
. We have
From these, we find that the total number of squares filled with is
. Note that this is also equal to
so this means
implies
, which is the final answer.
This argument gives us a way to construct a table, which is first we fill all the [i]good[/i] squares in a way such that one third of them are
, one third are
and one third are
. 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 |