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$.
IMO 2011 Problem 1
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin
Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.
Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.
Re: IMO 2011 Problem 1
There are total $6$ possible pairs such that $1\le i< j\le4$. The expressions are symmetric. Let's assume without loss of generality, $a_1<a_2<a_3<a_4$ because they are distinct. Since $a_2+a_4|s_A=a_1+a_2+a_3+a_4\to a_2+a_4|a_1+a_3<a_2+a_4$, and the same holds for $a_3+a_4$. Therefore, $n_{A}=4$.
$a_1+a_4|a_2+a_3\to a_1+a_4\le a_2+a_3$, if $a_2+a_3<s<2(a_2+a_3)$, $s$ is not a multiple of $a_2+a_3$. So $a_1+a_4=a_2+a_3=k,s=2k$. This shows that the set is $\{a,b,d-a,d-b\}$ for some $a,b$.
We have $d-b+a|d+b-a\to d-b+a|2d$ and $a+b|2d-a-b\to a+b|2d$. From the first, if $d+a-b|d-a+b$ we easily conclude from $\frac{a_2+a_4}{a_1+a_3}=l,l=2\to d=3(b-a)$ or $d=a+b$ gives the solution $a+b=2(a-b)\to b=3a\to a=1,b=3$. Then $a+b=4|2d\to d=2k$ is a solution.
Else $d=3(b-a)\to a+b|6(b-a)\to a+b|12a\to 1<a+b|12\to a+b=3,6,12$. We have three cases $a=1,b=2,3|d$ giving $\{1,2,3k-2,3k-1\}$.
Or, $a=1,b=5$ as $\gcd(a,b)=1$. Then $6|2d\to d=3k$ giving $\{1,5,3k-5,3k-1\}$.
Else $a=1,b=11,6|d$ gives $\{1,11,6k-11,6k-1\}$.
They are all solutions.ion.
Else $d=3(b-a)\to a+b|6(b-a)\to a+b|12a\to 1<a+b|12\to a+b=3,6,12$. We have three cases $a=1,b=2,3|d$ giving $\{1,2,3k-2,3k-1\}$.
Or, $a=1,b=5$ as $\gcd(a,b)=1$. Then $6|2d\to d=3k$ giving $\{1,5,3k-5,3k-1\}$.
Else $a=1,b=11,6|d$ gives $\{1,11,6k-11,6k-1\}$.
Now use the fact $a_1+a_3|a_2+a_4$ and find the complete solutions.
Note: This year IMO problems 1 and 5 both use the same idea.
$a_1+a_4|a_2+a_3\to a_1+a_4\le a_2+a_3$, if $a_2+a_3<s<2(a_2+a_3)$, $s$ is not a multiple of $a_2+a_3$. So $a_1+a_4=a_2+a_3=k,s=2k$. This shows that the set is $\{a,b,d-a,d-b\}$ for some $a,b$.
We have $d-b+a|d+b-a\to d-b+a|2d$ and $a+b|2d-a-b\to a+b|2d$. From the first, if $d+a-b|d-a+b$ we easily conclude from $\frac{a_2+a_4}{a_1+a_3}=l,l=2\to d=3(b-a)$ or $d=a+b$ gives the solution $a+b=2(a-b)\to b=3a\to a=1,b=3$. Then $a+b=4|2d\to d=2k$ is a solution.
Else $d=3(b-a)\to a+b|6(b-a)\to a+b|12a\to 1<a+b|12\to a+b=3,6,12$. We have three cases $a=1,b=2,3|d$ giving $\{1,2,3k-2,3k-1\}$.
Or, $a=1,b=5$ as $\gcd(a,b)=1$. Then $6|2d\to d=3k$ giving $\{1,5,3k-5,3k-1\}$.
Else $a=1,b=11,6|d$ gives $\{1,11,6k-11,6k-1\}$.
They are all solutions.ion.
Else $d=3(b-a)\to a+b|6(b-a)\to a+b|12a\to 1<a+b|12\to a+b=3,6,12$. We have three cases $a=1,b=2,3|d$ giving $\{1,2,3k-2,3k-1\}$.
Or, $a=1,b=5$ as $\gcd(a,b)=1$. Then $6|2d\to d=3k$ giving $\{1,5,3k-5,3k-1\}$.
Else $a=1,b=11,6|d$ gives $\{1,11,6k-11,6k-1\}$.
Now use the fact $a_1+a_3|a_2+a_4$ and find the complete solutions.
Note: This year IMO problems 1 and 5 both use the same idea.
One one thing is neutral in the universe, that is $0$.
- Tahmid Hasan
- Posts:665
- Joined:Thu Dec 09, 2010 5:34 pm
- Location:Khulna,Bangladesh.
Re: IMO 2011 Problem 1
since $a_1,a_2,a_3,a_4$ are distinct positive integers without loss of generality we may assume
$a_1<a_2<a_3<a_4$
now the six possible cases are
a.$a_1+a_2 \mid s_a$ or, $a_1+a_2 \mid a_3+a_4$
b.$a_1+a_3 \mid s_a$ or,$a_1 +a_3 \mid a_2+a_4$
c.$a_1+a_4 \mid s_a$ or,$a_1+a_4 \mid a_2+a_3$
d.$a_2+a_3 \mid s_a$ or, $a_2+a_3 \mid a_1+a_4$
e.$a_2+a_4 \mid s_a$ or, $a_2+a_4 \mid a_1+a_3$
f.$a_3+a_4 \mid s_a$ or, $a_3+a_4 \mid a_1+a_2$
but $a_2>a_1,a_4>a_3$ so,$a_2+a_4>a_1a_3$
and $a_3>a_1,a_4>a_2$ so,$a_3+a_4>a_1+a_2$
so e. and f. are not possible,now we consider the case
$n_a=4$
the cases we have now are
1. $a_1+a_2 \mid a_3+a_4$
2.$a_1 +a_3 \mid a_2+a_4$
3.$a_1+a_4 \mid a_2+a_3$
4. $a_2+a_3 \mid a_1+a_4$
from 3. and 4. we get $a_2+a_3=a_1+a_4$ or $a_2+a_3=-(a_1+a_4)$
but both sides are natural,so the second condition is not possible.
so we have
$a_2+a_3=a_1+a_4$
or,$a_2-a_1=a_4-a_3$
or,$a_3-a_1=a_4-a_2$
from this we can deduce ${a_1,a_2,a_3,a_4}={a_1,a_1+k_1,a_1+k_2,a_1+k_1+k_2}$......(x)
where $k_1,k_2$ are natural numbers.
inputting these values in 1. and 2. we get
1.a.$2a_1+k_1 \mid 2k_2$ or,$(2a_1+k_1)p_1=2k_2$........(s)[p_1 is a natural number]
2.a.$2a_1+k_2 \mid 2k_1$ or,$(2a_1+k_2)p_2= 2k_1$.......(t)[p_2 is a natural number]
now we input the value of $k_2$ from (s) to (t)
and get $2a_1p_2(2+p_1)=k_1(4-p_1p_2)$........(u)
since the left side of (u) is positive then the right side is also positive
so $0<p_1p_2<1$
now the possible cases are
c1.$p_1=1,p_2=2$
c2.$p_1=2,p_2=1$
c3.$p_1=1,p_2=1$
c4.$p_1=1,p_2=3$
c5.$p_1=3,p_2=1$
first we input these values in (u) and get the value of $k_1$ wrt $a_1$
now we input the values in (t) and get the value of $k_2$ wrt $a_1$
now we input the value of $k_1,k_2$ in (x) and the five results from which c1,c3,c4 are not possible after doing verification.
then the two desired results are
c2.${a_1,a_1,a_1,a_1}={a_1,5a_1,7a_1,11a_1}$
c5.${a_1,a_1,a_1,a_1}={a_1,11a_1,19a_1,29a_1}$
$a_1<a_2<a_3<a_4$
now the six possible cases are
a.$a_1+a_2 \mid s_a$ or, $a_1+a_2 \mid a_3+a_4$
b.$a_1+a_3 \mid s_a$ or,$a_1 +a_3 \mid a_2+a_4$
c.$a_1+a_4 \mid s_a$ or,$a_1+a_4 \mid a_2+a_3$
d.$a_2+a_3 \mid s_a$ or, $a_2+a_3 \mid a_1+a_4$
e.$a_2+a_4 \mid s_a$ or, $a_2+a_4 \mid a_1+a_3$
f.$a_3+a_4 \mid s_a$ or, $a_3+a_4 \mid a_1+a_2$
but $a_2>a_1,a_4>a_3$ so,$a_2+a_4>a_1a_3$
and $a_3>a_1,a_4>a_2$ so,$a_3+a_4>a_1+a_2$
so e. and f. are not possible,now we consider the case
$n_a=4$
the cases we have now are
1. $a_1+a_2 \mid a_3+a_4$
2.$a_1 +a_3 \mid a_2+a_4$
3.$a_1+a_4 \mid a_2+a_3$
4. $a_2+a_3 \mid a_1+a_4$
from 3. and 4. we get $a_2+a_3=a_1+a_4$ or $a_2+a_3=-(a_1+a_4)$
but both sides are natural,so the second condition is not possible.
so we have
$a_2+a_3=a_1+a_4$
or,$a_2-a_1=a_4-a_3$
or,$a_3-a_1=a_4-a_2$
from this we can deduce ${a_1,a_2,a_3,a_4}={a_1,a_1+k_1,a_1+k_2,a_1+k_1+k_2}$......(x)
where $k_1,k_2$ are natural numbers.
inputting these values in 1. and 2. we get
1.a.$2a_1+k_1 \mid 2k_2$ or,$(2a_1+k_1)p_1=2k_2$........(s)[p_1 is a natural number]
2.a.$2a_1+k_2 \mid 2k_1$ or,$(2a_1+k_2)p_2= 2k_1$.......(t)[p_2 is a natural number]
now we input the value of $k_2$ from (s) to (t)
and get $2a_1p_2(2+p_1)=k_1(4-p_1p_2)$........(u)
since the left side of (u) is positive then the right side is also positive
so $0<p_1p_2<1$
now the possible cases are
c1.$p_1=1,p_2=2$
c2.$p_1=2,p_2=1$
c3.$p_1=1,p_2=1$
c4.$p_1=1,p_2=3$
c5.$p_1=3,p_2=1$
first we input these values in (u) and get the value of $k_1$ wrt $a_1$
now we input the values in (t) and get the value of $k_2$ wrt $a_1$
now we input the value of $k_1,k_2$ in (x) and the five results from which c1,c3,c4 are not possible after doing verification.
then the two desired results are
c2.${a_1,a_1,a_1,a_1}={a_1,5a_1,7a_1,11a_1}$
c5.${a_1,a_1,a_1,a_1}={a_1,11a_1,19a_1,29a_1}$
বড় ভালবাসি তোমায়,মা
Re: IMO 2011 Problem 1
Let's assume without loss of generality, $a_1<a_2<a_3<a_4$ because the numbers are distinct.
Now, it's visible that $a_3+a_4$ , $a_2+a_4 > \frac {1}{2} S_A$ and therefore do not devide $S_A$.
So $n_A \leq 4$.
If ${a_1+a_4}$ is not equal to ${a_2+a_3}$, $a_1+a_4$ or $a_2+a_3$ will be greater than $\frac {1}{2}S_A$ and won't divide it.
So, to get $n_A$'s max value $(4)$, $a_1+a_4$ has to be equal to $a_2+a_3$.
So, ${a_1+a_4} = {a_2+a_3}$ ................... $(1)$
Again, ${a_2+a_4} = k(a_1+a_3)$............... $(2)$
and ${a_3+a_4} = m(a_1+a_2)$............... $(3)$
where $m,k \in N$ and $m,k > 1$.
From $(2)$, we get -
$a_2+a_2+a_3-a_1=k.a_1+k.a_3 $
$\Rightarrow (k+1)a_1+(k-1)a_3=2a_2$ ................ $(4)$
As $2a_3>2a_2$, so $(k-1)=1$.
Therefore, $a_3=2a_2-3a_1$............ $(5)$
and $a_4=3a_2-4a_1$............ $(6)$ [From $(1)$]
Again, From $(3)$ we get -
${5a_2-7a_1} = m(a_1+a_2) $
$\Rightarrow (m+7)a_1 = (5-m)a_2$.................... $(7)$
As, $1 \leq (5-m) \leq 3$,
$m$ has $3$ possible values. $(2,3,4)$
Putting $m=2$ in $(5)$, we deduce $a_2=a_3$ which is not possible. So $m$ is not equal to $2$.
Then, putting $m=3$ in $(5),(6)$ and $(7)$ we get -
$A$=$\left \{ a_1,5a_1,7a_1,11a_1 \right \}$.
And putting $m=3$ in $(5),(6)$ and $(7)$ we get -
$A$=$\left \{ a_1,11a_1,19a_1,29a_1 \right \}$.
These two sets represent all such sets $A$ which satisfy the given requirements.
Now, it's visible that $a_3+a_4$ , $a_2+a_4 > \frac {1}{2} S_A$ and therefore do not devide $S_A$.
So $n_A \leq 4$.
If ${a_1+a_4}$ is not equal to ${a_2+a_3}$, $a_1+a_4$ or $a_2+a_3$ will be greater than $\frac {1}{2}S_A$ and won't divide it.
So, to get $n_A$'s max value $(4)$, $a_1+a_4$ has to be equal to $a_2+a_3$.
So, ${a_1+a_4} = {a_2+a_3}$ ................... $(1)$
Again, ${a_2+a_4} = k(a_1+a_3)$............... $(2)$
and ${a_3+a_4} = m(a_1+a_2)$............... $(3)$
where $m,k \in N$ and $m,k > 1$.
From $(2)$, we get -
$a_2+a_2+a_3-a_1=k.a_1+k.a_3 $
$\Rightarrow (k+1)a_1+(k-1)a_3=2a_2$ ................ $(4)$
As $2a_3>2a_2$, so $(k-1)=1$.
Therefore, $a_3=2a_2-3a_1$............ $(5)$
and $a_4=3a_2-4a_1$............ $(6)$ [From $(1)$]
Again, From $(3)$ we get -
${5a_2-7a_1} = m(a_1+a_2) $
$\Rightarrow (m+7)a_1 = (5-m)a_2$.................... $(7)$
As, $1 \leq (5-m) \leq 3$,
$m$ has $3$ possible values. $(2,3,4)$
Putting $m=2$ in $(5)$, we deduce $a_2=a_3$ which is not possible. So $m$ is not equal to $2$.
Then, putting $m=3$ in $(5),(6)$ and $(7)$ we get -
$A$=$\left \{ a_1,5a_1,7a_1,11a_1 \right \}$.
And putting $m=3$ in $(5),(6)$ and $(7)$ we get -
$A$=$\left \{ a_1,11a_1,19a_1,29a_1 \right \}$.
These two sets represent all such sets $A$ which satisfy the given requirements.
Please Install $L^AT_EX$ fonts in your PC for better looking equations,
Learn how to write equations, and don't forget to read Forum Guide and Rules.
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." - Sherlock Holmes
Learn how to write equations, and don't forget to read Forum Guide and Rules.
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." - Sherlock Holmes