Difference between revisions of "2011 IMO Problems/Problem 1"
(Formatted) |
(→Solution 2 (Avoids the error of the first)) |
||
(13 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
− | Given any set <math>A = \{a_1, a_2, a_3, a_4\}</math> of four distinct positive integers, we denote the sum <math>a_1+a_2+a_3+a_4</math> by <math>s_A</math>. Let <math>n_A</math> denote the number of pairs <math>(i,j)</math> with <math>1 \leq i < j \leq 4</math> for which <math>a_i+a_j</math> divides <math>s_A</math>. Find all sets <math>A</math> of four distinct positive integers which achieve the largest possible value of <math>n_A</math>. | + | Given any set <math>A = \{a_1, a_2, a_3, a_4\}</math> of four distinct positive integers, we denote the sum <math>a_1 +a_2 +a_3 +a_4</math> by <math>s_A</math>. Let <math>n_A</math> denote the number of pairs <math>(i, j)</math> with <math>1 \leq i < j \leq 4</math> for which <math>a_i +a_j</math> divides <math>s_A</math>. Find all sets <math>A</math> of four distinct positive integers which achieve the largest possible value of <math>n_A</math>. |
− | ==Solution== | + | ''Author: Fernando Campos, Mexico'' |
+ | |||
+ | ==Solution 1== | ||
Firstly, if we order <math>a_1 \ge a_2 \ge a_3 \ge a_4</math>, we see <math>2(a_3 + a_4) \ge (a_1+a_2)+(a_3+a_4) = s_A \geq 0</math>, so <math>(a_3, a_4)</math> isn't a couple that satisfies the conditions of the problem. Also, <math>2(a_4 + a_2) = (a_4 + a_4) + (a_2 + a_2) \ge (a_4+a_3)+(a_2+a_1) = s_A \ge 0</math>, so again <math>(a_2, a_4)</math> isn't a good couple. We have in total 6 couples. So <math>n_A \leq 6-2=4</math>. | Firstly, if we order <math>a_1 \ge a_2 \ge a_3 \ge a_4</math>, we see <math>2(a_3 + a_4) \ge (a_1+a_2)+(a_3+a_4) = s_A \geq 0</math>, so <math>(a_3, a_4)</math> isn't a couple that satisfies the conditions of the problem. Also, <math>2(a_4 + a_2) = (a_4 + a_4) + (a_2 + a_2) \ge (a_4+a_3)+(a_2+a_1) = s_A \ge 0</math>, so again <math>(a_2, a_4)</math> isn't a good couple. We have in total 6 couples. So <math>n_A \leq 6-2=4</math>. | ||
Line 19: | Line 21: | ||
CASE II and III:<math>k_1=</math>2, 4. Left to the reader. | CASE II and III:<math>k_1=</math>2, 4. Left to the reader. | ||
− | ANSWER: <math>\{11a, a, 5a, 7a\}</math>,<math>\{a, 14a, 6a, 9a\}</math>, for any positive integer <math>a</math>. | + | ANSWER: <math>\{11a, a, 5a, 7a\}</math>,<math> \{a, 11a, 19a, 29a\} </math>, for any positive integer <math>a</math>. |
+ | |||
+ | (Note: The above solution looks generally correct, but the actual answer should be <math>\{11a, a, 5a, 7a\}</math>,<math>\{a, 11a, 19a, 29a\}</math>. You can check that <math>\{a, 14a, 6a, 9a\}</math> doesn't actually work. -Someone who didn't write up the above solution but solved the problem in a similar way) | ||
+ | |||
+ | ==Solution 2 (Avoids the error of the first)== | ||
+ | Similarly to the first solution, let us order the terms in set <math>A</math> by <math>0 < a_1 < a_2 < a_3 < a_4</math> since it is given that these four integers must be distinct and positive. Obviously, <math>s_a > 0</math> from this. We know that pair <math>(a_3, a_4)</math> cannot work because <math>2(a_3 + a_4) > a_1 + a_2 + a_3 + a_4 = s_A.</math> Additionally, pair <math>(a_2, a_4)</math> cannot work for the same reason: <math>2(a_2 + a_4) = a_4 + a_4 + a_2 + a_2 > s_A.</math> | ||
+ | |||
+ | Hence, since there were only <math>{4 \choose 2} = 6</math> pairs <math>(i, j)</math> in total, and two pairs are guaranteed not to work, we are to find sets <math>A</math> satisfying <math>n_A = 6 - 2 = 4.</math> Due to our making <math>a_4</math> the largest term of set <math>A</math>, the only way to have a pair <math>(a_i, a_4)</math> that exists such that <math>a_i + a_4 | s_A</math> is to make <math>i</math> equal to 1 and find an <math>a_1</math> such that <math>\frac{s_A}{a_1 + a_4} = 2.</math> When this happens, we know that <math>\frac{s_A}{a_2 + a_3} = 2</math>, as well. It clearly follows that we need pairs <math>(a_1, a_2)</math> and <math>(a_1, a_3)</math> that exist such that both <math>a_1 + a_2</math> and <math>a_1 + a_3</math> divide <math>s_A.</math> | ||
+ | |||
+ | To satisfy conditions <math>\frac{s_A}{a_1 + a_4} = 2</math> and <math>\frac{s_A}{a_2 + a_3} = 2</math>, choose a set <math>A</math> with four distinct positive integer elements <math>a - x, a, b, b + x</math> with <math>0 < a - x < a < b < b + x.</math> Obviously, <math>x < a < b</math> for our set to consist solely of positive integers. The problem becomes to find <math>x, a,</math> and <math>b</math> such that <math>2a - x | 2(a + b)</math> and <math>(a + b) - x | 2a + 2b.</math> | ||
+ | |||
+ | We realize that <math>x</math> can be any positive even integer. This allows <math>2a - x</math> and <math>2(a + b)</math> to have a common factor of 2, simplifying our problem a bit. Hence, <math>a - \frac{x}{2}</math> must divide <math>(a + b).</math> Now, we can look at the other condition, <math>(a + b) - x | 2a + 2b</math>, to solve this problem. To find <math>a, b, x</math> satisfying <math>(a + b) - x | 2a + 2b</math>, it suffices to define a positive integer <math>n</math> that makes <math>n(a + b - x) = 2(a + b) \Rightarrow 0 = (n - 2)a + (n - 2)b - nx \Rightarrow (n - 2)(a + b) = nx.</math> Note that <math>x</math> must be less than <math>\frac{a + b}{2}.</math> If <math>x \ge \frac{a + b}{2}</math>, <math>(n - 2)(a + b) = nx</math> would have solutions <math>x, a,</math> and <math>b</math> that will make <math>a - x < 0</math>, since <math>a < \frac{a + b}{2}</math> due to <math>a < b.</math> This is a contradiction with the condition that each element in set <math>A</math> has to be positive. Despite this, We move on to some cases. | ||
+ | |||
+ | |||
+ | *<math>0 < n \le 2</math> cannot work because this makes at least one of the solutions <math>a, b, x</math> to <math>(n - 2)(a + b) = nx</math> zero or negative, another contradiction. | ||
+ | *For <math>n = 3</math>, we have that <math>a + b = 3x.</math> We need to find possible values for <math>a</math> such that <math>x < a < \frac{a + b}{2}</math> that satisfy both <math>a + b = 3x</math> and <math>a - \frac{x}{2} | (a + b) \Rightarrow a - \frac{x}{2} | 3x.</math> Note that because <math>(a + b) = 3</math>, the sum of our set <math>A</math> is <math>2(a + b) = 6x.</math> Hence, it suffices to call our terms <math>a -x, a, 3x - a,</math> and <math>4x - a.</math> The only values for <math>a</math> and <math>x</math> that work are those such that <math>5 | a</math> and <math>4 | x</math> at the same time, and <math>11 | a</math> and <math>10 | x</math> at the same time. Hence, we get that <math>a - x = \frac{a}{5}</math> or <math>\frac{a}{11}.</math> Moreover, it follows that <math>x = \frac{4a}{5}</math> or <math>\frac{10a}{11.}</math> On a side note, because we are constrained to <math>x < a < \frac{a + b}{2}</math>, <math>\frac{a}{5} = \frac{x}{4}</math> or <math>\frac{a}{11} = \frac{x}{10}</math>. Note that this completely satisfies <math>a - \frac{x}{2} | 3x</math> because the <math>a</math> and <math>x</math> that we chose exists such that <math>4(a - \frac{x}{2}) = 3x</math> for <math>5 | a</math>, <math>4 | x</math>, and <math>\frac{a}{5} = \frac{x}{4}</math>. At the same time, <math>5(a - \frac{x}{2}) = 3x</math> for <math>11 | a</math>, <math>10 | x</math>, and <math>\frac{a}{11} = \frac{x}{10}</math>. In turn, we have the two sets <math>A = \{\frac{a}{5}, a, \frac{7a}{5}, \frac{11a}{5}\}</math> and <math>\{\frac{a}{11}, a, \frac{19a}{11}, \frac{29a}{11}\}.</math> Since <math>a</math> must be a multiple of 5 or 11, we can scale these two sets by multiplying by 5 and 11, respectively, to get sets <math>A = \{p, 5p, 7p, 11p\}</math> and <math>\{p, 11p, 19p, 29p\}</math> with <math>p</math> being any <math>\frac{a}{5}</math> or <math>\frac{a}{11}</math> that results in positive integers for the first and second set, respectively. Remember that <math>a</math> cannot be zero because our set must contain positive integers. | ||
+ | *<math>n \ge 4</math> cannot work because we have established that <math>x</math> cannot be greater than or equal to <math>\frac{a + b}{2}.</math> Solving the inequality <math>\frac{n - 2}{n}(a + b) \ge \frac{a + b}{2}</math>, <math>a + b</math> cancels, resulting in <math>\frac{n - 2}{n} \ge \frac{1}{2} \Rightarrow 2n - 4\ge n \Rightarrow n \ge 4.</math> This shows that any <math>n</math> greater than or equal to 4 will not work for <math>x = \frac{n - 2}{n}(a + b)</math> . | ||
+ | |||
+ | |||
+ | Thus, the only possible sets <math>A</math> we have for satisfying the maximum <math>n_A</math>, which is 4, are <math>A = \{p, 5p, 7p, 11p\}</math> and <math>\{p, 11p, 19p, 29p\}</math>, with <math>p</math> being any positive integer since it is obvious that any <math>a</math> that is a positive multiple of 5 or 11 makes <math>\frac{a}{5}</math> and <math>\frac{a}{11}</math> positive integers, respectively. | ||
==See Also== | ==See Also== |
Latest revision as of 23:08, 26 June 2014
Problem
Given any set of four distinct positive integers, we denote the sum
by
. Let
denote the number of pairs
with
for which
divides
. Find all sets
of four distinct positive integers which achieve the largest possible value of
.
Author: Fernando Campos, Mexico
Solution 1
Firstly, if we order , we see
, so
isn't a couple that satisfies the conditions of the problem. Also,
, so again
isn't a good couple. We have in total 6 couples. So
.
We now find all sets with
. If
and
are both good couples, and
, we have
.
So WLOG
with
and
. It's easy to see
and since
are bad, all couples containing
must be good. Obviously
and
are good (
). So we have
and
.
Using the second equation, we see that if ,
, for some
a positive integer.
So now we use the first equation to get , for a natural
.
Finally, we obtain 1, 2 or 4. We divide in cases:
CASE I: .
So
and
. But
3, 4,5 or 6.
implies
, impossible.
when
. We easily see
and
, impossible since
. When
,
, and we get
.Uf
,
and we get
.
CASE II and III:2, 4. Left to the reader.
ANSWER: ,
, for any positive integer
.
(Note: The above solution looks generally correct, but the actual answer should be ,
. You can check that
doesn't actually work. -Someone who didn't write up the above solution but solved the problem in a similar way)
Solution 2 (Avoids the error of the first)
Similarly to the first solution, let us order the terms in set by
since it is given that these four integers must be distinct and positive. Obviously,
from this. We know that pair
cannot work because
Additionally, pair
cannot work for the same reason:
Hence, since there were only pairs
in total, and two pairs are guaranteed not to work, we are to find sets
satisfying
Due to our making
the largest term of set
, the only way to have a pair
that exists such that
is to make
equal to 1 and find an
such that
When this happens, we know that
, as well. It clearly follows that we need pairs
and
that exist such that both
and
divide
To satisfy conditions and
, choose a set
with four distinct positive integer elements
with
Obviously,
for our set to consist solely of positive integers. The problem becomes to find
and
such that
and
We realize that can be any positive even integer. This allows
and
to have a common factor of 2, simplifying our problem a bit. Hence,
must divide
Now, we can look at the other condition,
, to solve this problem. To find
satisfying
, it suffices to define a positive integer
that makes
Note that
must be less than
If
,
would have solutions
and
that will make
, since
due to
This is a contradiction with the condition that each element in set
has to be positive. Despite this, We move on to some cases.
cannot work because this makes at least one of the solutions
to
zero or negative, another contradiction.
- For
, we have that
We need to find possible values for
such that
that satisfy both
and
Note that because
, the sum of our set
is
Hence, it suffices to call our terms
and
The only values for
and
that work are those such that
and
at the same time, and
and
at the same time. Hence, we get that
or
Moreover, it follows that
or
On a side note, because we are constrained to
,
or
. Note that this completely satisfies
because the
and
that we chose exists such that
for
,
, and
. At the same time,
for
,
, and
. In turn, we have the two sets
and
Since
must be a multiple of 5 or 11, we can scale these two sets by multiplying by 5 and 11, respectively, to get sets
and
with
being any
or
that results in positive integers for the first and second set, respectively. Remember that
cannot be zero because our set must contain positive integers.
cannot work because we have established that
cannot be greater than or equal to
Solving the inequality
,
cancels, resulting in
This shows that any
greater than or equal to 4 will not work for
.
Thus, the only possible sets we have for satisfying the maximum
, which is 4, are
and
, with
being any positive integer since it is obvious that any
that is a positive multiple of 5 or 11 makes
and
positive integers, respectively.
See Also
2011 IMO (Problems) • Resources | ||
Preceded by First question |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
All IMO Problems and Solutions |