Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2011 IMO Problems/Problem 1"

(Created page with "Given any set A = {a1, a2, a3, a4} of four distinct positive integers, we denote the sum a1+a2+a3+a4 bysA. Let nA denote the number of pairs (i,j) with 1 ≤ i< j ≤ 4 for which...")
 
(→‎Solution 2 (Avoids the error of the first))
 
(16 intermediate revisions by 6 users not shown)
Line 1: Line 1:
−
Given any set A = {a1, a2, a3, a4} of four distinct positive integers, we denote the sum a1+a2+a3+a4 bysA. Let nA denote the number of pairs (i,j) with 1 ≤ i< j ≤ 4 for which ai+aj divides sA. Find all sets A of four distinct positive integers which achieve the largest possible value of nA.
+
==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>.
 +
 
 +
''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>.
 +
 
 +
We now find all sets <math>A</math> with <math>n_A = 4</math>. If <math>(a,b)</math> and <math>(c,d)</math> are both good couples, and <math>A=\{a, b, c, d\}</math>, we have <math>a+b=c+d=s_A/2</math>.
 +
So WLOG <math>A=\{a,b,a+x,b-x\}</math> with <math>x > 0</math> and <math>a < b, b-x, a+x</math>. It's easy to see <math>a=a_1</math> and since <math>(a_2, a_4),(a_3,a_4)</math> are bad, all couples containing <math>a</math> must be good. Obviously <math>(a,b)</math> and <math>(a+x,b-x)</math> are good (<math>s_A=2(a+b)</math>). So we have <math>2a+x | 2a+2b</math> and <math>a+b-x|2a+2b \Rightarrow a+b-x|2x</math>.
 +
 
 +
Using the second equation, we see that if <math>y=a+b</math>, <math>y-x|2x \Rightarrow yk_1-xk_1=2x \Rightarrow yk_1 = x(2+k_1) \Rightarrow y=x((2+k_1)/k_1)</math>, for some <math>k_1</math> a positive integer.
 +
 
 +
So now we use the first equation to get <math>2ak_2 + xk_2 = 2y = 2x(2+k_1)/k_1 \Rightarrow 2ak_2 = x(\frac{4+2k_1}{k_1}-k_2) \Rightarrow 2a=x(\frac{4+2k_1}{k_1k_2} - 1)</math>, for a natural <math>k_2</math>.
 +
 
 +
Finally, we obtain <math>k_1 | 4+2k-1 \Rightarrow k_1 | 4  \Rightarrow k_1=</math> 1, 2 or 4. We divide in cases:
 +
 
 +
CASE I: <math>k_1=1</math>.
 +
So <math>y=3x</math> and <math>2a=x((\frac{6}{k_2}) -1)</math>. But <math>a < b-x \Rightarrow 2a < y-x=2x \Rightarrow (6/k_2) - 1 < 2 \Rightarrow k_2 > 2 \Rightarrow k_2 =</math>3, 4,5 or 6. <math>k_2=6</math> implies <math>a=0</math>, impossible. <math>a=x</math> when <math>k_2=3</math>. We easily  see <math>b=3x=3x</math> and <math>A=\{x, 3x, 3x-x, 2x\}</math>, impossible since <math>3x-x=2x</math>. When <math>k_2=4</math>, <math>a=x/4=y/12</math>, and we get  <math>\{11a, a, 5a, 7a\}</math>.Uf <math>k_2=5</math>, <math>a=x/5=y/15</math> and we get <math>\{a, 14a, 6a, 9a\}</math>.
 +
 
 +
CASE II and III:<math>k_1=</math>2, 4. Left to the reader.
 +
 
 +
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==
 +
{{IMO box|year=2011|before=First question|num-a=2}}
 +
 
 +
[[Category:Olympiad Number Theory Problems]]

Latest revision as of 22:08, 26 June 2014

Problem

Given any set $A = \{a_1, a_2, a_3, a_4\}$ of four distinct positive integers, we denote the sum $a_1 +a_2 +a_3 +a_4$ by $s_A$. Let $n_A$ denote the number of pairs $(i, j)$ with $1 \leq i < j \leq 4$ for which $a_i +a_j$ divides $s_A$. Find all sets $A$ of four distinct positive integers which achieve the largest possible value of $n_A$.

Author: Fernando Campos, Mexico

Solution 1

Firstly, if we order $a_1 \ge a_2 \ge a_3 \ge a_4$, we see $2(a_3 + a_4) \ge (a_1+a_2)+(a_3+a_4) = s_A \geq 0$, so $(a_3, a_4)$ isn't a couple that satisfies the conditions of the problem. Also, $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$, so again $(a_2, a_4)$ isn't a good couple. We have in total 6 couples. So $n_A \leq 6-2=4$.

We now find all sets $A$ with $n_A = 4$. If $(a,b)$ and $(c,d)$ are both good couples, and $A=\{a, b, c, d\}$, we have $a+b=c+d=s_A/2$. So WLOG $A=\{a,b,a+x,b-x\}$ with $x > 0$ and $a < b, b-x, a+x$. It's easy to see $a=a_1$ and since $(a_2, a_4),(a_3,a_4)$ are bad, all couples containing $a$ must be good. Obviously $(a,b)$ and $(a+x,b-x)$ are good ($s_A=2(a+b)$). So we have $2a+x | 2a+2b$ and $a+b-x|2a+2b \Rightarrow a+b-x|2x$.

Using the second equation, we see that if $y=a+b$, $y-x|2x \Rightarrow yk_1-xk_1=2x \Rightarrow yk_1 = x(2+k_1) \Rightarrow y=x((2+k_1)/k_1)$, for some $k_1$ a positive integer.

So now we use the first equation to get $2ak_2 + xk_2 = 2y = 2x(2+k_1)/k_1 \Rightarrow 2ak_2 = x(\frac{4+2k_1}{k_1}-k_2) \Rightarrow 2a=x(\frac{4+2k_1}{k_1k_2} - 1)$, for a natural $k_2$.

Finally, we obtain $k_1 | 4+2k-1 \Rightarrow k_1 | 4 \Rightarrow k_1=$ 1, 2 or 4. We divide in cases:

CASE I: $k_1=1$. So $y=3x$ and $2a=x((\frac{6}{k_2}) -1)$. But $a < b-x \Rightarrow 2a < y-x=2x \Rightarrow (6/k_2) - 1 < 2 \Rightarrow k_2 > 2 \Rightarrow k_2 =$3, 4,5 or 6. $k_2=6$ implies $a=0$, impossible. $a=x$ when $k_2=3$. We easily see $b=3x=3x$ and $A=\{x, 3x, 3x-x, 2x\}$, impossible since $3x-x=2x$. When $k_2=4$, $a=x/4=y/12$, and we get $\{11a, a, 5a, 7a\}$.Uf $k_2=5$, $a=x/5=y/15$ and we get $\{a, 14a, 6a, 9a\}$.

CASE II and III:$k_1=$2, 4. Left to the reader.

ANSWER: $\{11a, a, 5a, 7a\}$,$\{a, 11a, 19a, 29a\}$, for any positive integer $a$.

(Note: The above solution looks generally correct, but the actual answer should be $\{11a, a, 5a, 7a\}$,$\{a, 11a, 19a, 29a\}$. You can check that $\{a, 14a, 6a, 9a\}$ 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 $A$ by $0 < a_1 < a_2 < a_3 < a_4$ since it is given that these four integers must be distinct and positive. Obviously, $s_a > 0$ from this. We know that pair $(a_3, a_4)$ cannot work because $2(a_3 + a_4) > a_1 + a_2 + a_3 + a_4 = s_A.$ Additionally, pair $(a_2, a_4)$ cannot work for the same reason: $2(a_2 + a_4) = a_4 + a_4 + a_2 + a_2 > s_A.$

Hence, since there were only ${4 \choose 2} = 6$ pairs $(i, j)$ in total, and two pairs are guaranteed not to work, we are to find sets $A$ satisfying $n_A = 6 - 2 = 4.$ Due to our making $a_4$ the largest term of set $A$, the only way to have a pair $(a_i, a_4)$ that exists such that $a_i + a_4 | s_A$ is to make $i$ equal to 1 and find an $a_1$ such that $\frac{s_A}{a_1 + a_4} = 2.$ When this happens, we know that $\frac{s_A}{a_2 + a_3} = 2$, as well. It clearly follows that we need pairs $(a_1, a_2)$ and $(a_1, a_3)$ that exist such that both $a_1 + a_2$ and $a_1 + a_3$ divide $s_A.$

To satisfy conditions $\frac{s_A}{a_1 + a_4} = 2$ and $\frac{s_A}{a_2 + a_3} = 2$, choose a set $A$ with four distinct positive integer elements $a - x, a, b, b + x$ with $0 < a - x < a < b < b + x.$ Obviously, $x < a < b$ for our set to consist solely of positive integers. The problem becomes to find $x, a,$ and $b$ such that $2a - x | 2(a + b)$ and $(a + b) - x | 2a + 2b.$

We realize that $x$ can be any positive even integer. This allows $2a - x$ and $2(a + b)$ to have a common factor of 2, simplifying our problem a bit. Hence, $a - \frac{x}{2}$ must divide $(a + b).$ Now, we can look at the other condition, $(a + b) - x | 2a + 2b$, to solve this problem. To find $a, b, x$ satisfying $(a + b) - x | 2a + 2b$, it suffices to define a positive integer $n$ that makes $n(a + b - x) = 2(a + b) \Rightarrow 0 = (n - 2)a + (n - 2)b - nx \Rightarrow (n - 2)(a + b) = nx.$ Note that $x$ must be less than $\frac{a + b}{2}.$ If $x \ge \frac{a + b}{2}$, $(n - 2)(a + b) = nx$ would have solutions $x, a,$ and $b$ that will make $a - x < 0$, since $a < \frac{a + b}{2}$ due to $a < b.$ This is a contradiction with the condition that each element in set $A$ has to be positive. Despite this, We move on to some cases.


  • $0 < n \le 2$ cannot work because this makes at least one of the solutions $a, b, x$ to $(n - 2)(a + b) = nx$ zero or negative, another contradiction.
  • For $n = 3$, we have that $a + b = 3x.$ We need to find possible values for $a$ such that $x < a < \frac{a + b}{2}$ that satisfy both $a + b = 3x$ and $a - \frac{x}{2} | (a + b) \Rightarrow a - \frac{x}{2} | 3x.$ Note that because $(a + b) = 3$, the sum of our set $A$ is $2(a + b) = 6x.$ Hence, it suffices to call our terms $a -x, a, 3x - a,$ and $4x - a.$ The only values for $a$ and $x$ that work are those such that $5 | a$ and $4 | x$ at the same time, and $11 | a$ and $10 | x$ at the same time. Hence, we get that $a - x = \frac{a}{5}$ or $\frac{a}{11}.$ Moreover, it follows that $x = \frac{4a}{5}$ or $\frac{10a}{11.}$ On a side note, because we are constrained to $x < a < \frac{a + b}{2}$, $\frac{a}{5} = \frac{x}{4}$ or $\frac{a}{11} = \frac{x}{10}$. Note that this completely satisfies $a - \frac{x}{2} | 3x$ because the $a$ and $x$ that we chose exists such that $4(a - \frac{x}{2}) = 3x$ for $5 | a$, $4 | x$, and $\frac{a}{5} = \frac{x}{4}$. At the same time, $5(a - \frac{x}{2}) = 3x$ for $11 | a$, $10 | x$, and $\frac{a}{11} = \frac{x}{10}$. In turn, we have the two sets $A = \{\frac{a}{5}, a, \frac{7a}{5}, \frac{11a}{5}\}$ and $\{\frac{a}{11}, a, \frac{19a}{11}, \frac{29a}{11}\}.$ Since $a$ must be a multiple of 5 or 11, we can scale these two sets by multiplying by 5 and 11, respectively, to get sets $A = \{p, 5p, 7p, 11p\}$ and $\{p, 11p, 19p, 29p\}$ with $p$ being any $\frac{a}{5}$ or $\frac{a}{11}$ that results in positive integers for the first and second set, respectively. Remember that $a$ cannot be zero because our set must contain positive integers.
  • $n \ge 4$ cannot work because we have established that $x$ cannot be greater than or equal to $\frac{a + b}{2}.$ Solving the inequality $\frac{n - 2}{n}(a + b) \ge \frac{a + b}{2}$, $a + b$ cancels, resulting in $\frac{n - 2}{n} \ge \frac{1}{2} \Rightarrow 2n - 4\ge n \Rightarrow n \ge 4.$ This shows that any $n$ greater than or equal to 4 will not work for $x = \frac{n - 2}{n}(a + b)$ .


Thus, the only possible sets $A$ we have for satisfying the maximum $n_A$, which is 4, are $A = \{p, 5p, 7p, 11p\}$ and $\{p, 11p, 19p, 29p\}$, with $p$ being any positive integer since it is obvious that any $a$ that is a positive multiple of 5 or 11 makes $\frac{a}{5}$ and $\frac{a}{11}$ 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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2011_IMO_Problems/Problem_1&oldid=62353"