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"
(Answer to problem)
Line 1: Line 1:
 
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:
 +
 +
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, 14a, 6a, 9a\}</math>, for any positive integer <math>a</math>.

Revision as of 22:46, 22 August 2011

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$.


Solution:

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, 14a, 6a, 9a\}$, for any positive integer $a$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2011_IMO_Problems/Problem_1&oldid=41872"