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)
(Formatted)
Line 1: Line 1:
 +
==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==
−
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>.
 
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 21: Line 20:
  
 
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, 14a, 6a, 9a\}</math>, for any positive integer <math>a</math>.
 +
 +
==See Also==
 +
{{IMO box|year=2011|before=First question|num-a=2}}
 +
 +
[[Category:Olympiad Number Theory Problems]]

Revision as of 16:55, 3 April 2012

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

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

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=46026"