IMO 2011 Problem 1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5452 posts

#1 h Jul 18, 2011, 12:05 PM • 19 Y

Y by acegikmoqsuwy2000, Davi-8191, adityaguharoy, pog, centslordm, megarnie, ryusei, Adventure10, Mango247, ItsBesi, and 9 other users

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

Proposed by Fernando Campos, Mexico

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Utkirstudios

56 posts

Utkirstudios

#2 h Jul 18, 2011, 12:26 PM • 7 Y

Y by pog, centslordm, Adventure10, Mango247, radian_51, and 2 other users

I think it is easy to prove that $n_A$ <5. Hence:
$n_A = 4$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

-[]-

97 posts

-[]-

#3 h Jul 18, 2011, 12:30 PM • 11 Y

Y by Cha21, pog, centslordm, Adventure10, Mango247, radian_51, and 5 other users

Let $a_1<a_2<a_3<a_4$ . We have $a_2+a_4>a_1+a_3$ and $a_3+a_4>a_1+a_2$ .
Therefore, $a_2+a_4$ and $a_3+a_4$ are greater then $\frac{s_A}{2}$ and do not divide $s_A$ .
So the number $n_A$ cannot be greater than 4.

To achieve the maximum value, consider $a_1+a_4$ and $a_2+a_3$ . If they are not equal, one of them has to be greater than $\frac{s_A}{2}$ and does not divide $s_A$ . Therefore, $a_1+a_4 = a_2+a_3$ .

Let $k=a_2-a_1$ , $m=a_1$ , $n=a_4$ . The four numbers are in the forms $m,m+k,n-k,n$ .

We have $2m+k | 2(m+n)$ and $m+n-k | 2(m+n)$ .
Since $a_2<a_3$ , we get $m+k<n-k$ . So, $2k<n-m<m+n$ .
Therefore, $4(m+n-k)>2(m+n)>2(m+n-k)$ . But since $m+n-k | 2(m+n)$ , the only case is $2(m+n)=3(m+n-k)$ or $k=\frac{m+n}{3}$ .

Now the four numbers are in the forms $m, \frac{4m+n}{3},\frac{2n-m}{3},n$ .
Since $a_1+a_2=\frac{7m+n}{3}$ divides $2(m+n)$ , we get $7m+n | 6m+6n$ or $7m+n|36n$ .

This post has been edited 9 times. Last edited by -[]-, Jul 18, 2011, 12:53 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

misof

10 posts

misof

#4 h Jul 18, 2011, 12:40 PM • 17 Y

Y by Amir Hossein, ArtisticLimon, XbenX, Imayormaynotknowcalculus, pog, centslordm, Sush0, Adventure10, Mango247, thatsgonzalez, and 7 other users

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lchserious

80 posts

lchserious

#5 h Jul 18, 2011, 12:44 PM • 7 Y

Y by pog, centslordm, Adventure10, Mango247, radian_51, and 2 other users

The answers are $(1,5,7,11),(1,11,19,29),(2,10,14,22)$ and their multiples.
In fact, by applying several inequalities, we know that the answer has the form $(a,b,d-b,d-a)$ where $\frac{d}{2}>b>a,(a,b)=1$ .
To achieve the maximum value 4, we further need $d-(b-a)|2d$ and $a+b|2d$ ,
but since $d-(b-a)>\frac{d}{2}$ , we must have $3(a-b)=d$ .
All we need to do is to solve $a+b|3(b-a)$ , which is pretty easy.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

arqady

30235 posts

arqady

#6 h Jul 18, 2011, 1:14 PM • 8 Y

Y by pog, centslordm, Adventure10, Mango247, radian_51, and 3 other users

Yes, $\{(a,11a,19a,29a)|a\in\mathbb N\}$ or $\{(a,5a,7a,11a)|a\in\mathbb N\}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dr_Civot

354 posts

dr_Civot

#7 h Jul 18, 2011, 1:44 PM • 8 Y

Y by pog, centslordm, Adventure10, radian_51, and 4 other users

WLOG $a_1<a_2<a_3<a_4$ .
Let $a_1=a$ , $a_2=a+x$ , $a_3=a+x+y$ , $a_4=a+x+y+z$ ( $x,y,z>0$ ).
We see that $a_4+a_3>a_1+a_2$ and $a_4+a_2>a_1+a_3$ so $s_A$ is not divisible by $a_4+a_3$ , and $a_4+a_2$ . So because we can choose $i,j$ on $6$ ways, and $2$ ways are impossible, $n_A\leq 4$ . It is easy to see that $n=4$ because numbers $1,7,5,11$ satisfies condition. Now we have:
$2a+x|2a+2x+2y+z\Rightarrow 2a+x|2(x+y)$
$2a+x+y|2a+3x+y+z\Rightarrow 2a+x+y|x+z$
$2a+x+y+z|2a+2x+y$ .... $[1]$
$2a+2x+y|2a+x+y+z$ .... $[2]$
$[1],[2]\Rightarrow 2a+x+y+z=2a+2x+y\Rightarrow x=z$ (because a|b and b|a)
Now we just need to find numbers $a,x,y$ such that:
$2a+x|2(x+y)$ and $2a+x+y|2x\Rightarrow k(2a+x+y)=2x \Rightarrow k=1$ because for $k>1$ $k(2a+x+y)>2x$ , so we have $2a+y=x$ . Now $2a+x=4a+y|2(x+y)=4a+y+3y$ so $4a+y|3y\Rightarrow m(4a+y)=3y$ so $m=1$ or $m=2$ . If $m=1$ then solutions are $(a_1,a_2,a_3,a_4)=(a,7a,5a,11a)$ and if $m=2$ solutions are $(a_1,a_2,a_3,a_4)=(a,11a,19a,29a)$ and all permutations.

note: I use that if $a_i+a_j|s_A\Rightarrow a_i+a_j|s_A-a_i-a_j$ , and if $a|b$ then $a\leq b$ .

This post has been edited 1 time. Last edited by dr_Civot, Jul 18, 2011, 1:48 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

arshakus

769 posts

arshakus

#8 h Jul 18, 2011, 1:46 PM • 5 Y

Y by pog, centslordm, Adventure10, and 2 other users

it is very nice problem)))
i solved it in about hour)))
but the second and third are awful))

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

uglysolutions

304 posts

uglysolutions

#9 h Jul 18, 2011, 1:50 PM • 11 Y

Y by huyaguero, amar_04, pog, centslordm, ZHEKSHEN, Adventure10, Mango247, and 4 other users

Suppose WLOG $a_1 < a_2 < a_3 < a_4$ . It is not possible that $a_3 + a_4 \mid s_A$ , because it is equivalent to $a_3 + a_4 \mid a_1 + a_2$ , a contradiction since $a_1,a_2,a_3,a_4$ are positive and $a_3+a_4 > a_1+a_2$ .
In a similar fashion we can rule out the case $a_2+a_4 \mid s_A$ .
Therefore we get $n_A \leq 4$ . If $n_A = 4$ , the following conditions must be fulfilled:
$a_1+a_2 \mid a_3+a_4$ ;
$a_1+a_3 \mid a_2+a_4$ ;
$a_1+a_4 \mid a_2+a_3$ ;
$a_2+a_3 \mid a_1+a_4$ .

The last two conditions give $a_1+a_4 = a_2+a_3$ , since the $a_i$ 's are positive. Hence $s_A = 2(a_2+a_3)$ , and now we just have to find all positive integers $a_1 < a_2 < a_3$ such that $a_1+a_2 \mid 2(a_2+a_3)$ and $a_1+a_3 \mid 2(a_2+a_3)$ .

Let $2(a_2+a_3) = k(a_1+a_2)$ , hence $a_3 = \frac{ka_1+(k-2)a_2}{2}$ . Notice $k \geq 3$ since $2(a_1+a_2) < 2(a_2+a_3)$ . The second condition is equivalent to $a_1+a_3 \mid 2(a_2-a_1)$ , that is, $\frac{(k+2)a_1+(k-2)a_2}{2} \mid 2(a_2-a_1) \iff (k+2)a_1+(k-2)a_2 \mid 4a_2 - 4a_1 \Rightarrow k \leq 5$ , otherwise LHS would be greater than RHS.

So now we have three cases:
If $k=5$ , then $7a_1+3a_2 \mid 4a_2 - 4a_1$ , but we must have equality since $2(7a_1+3a_2) > 4a_2 > 4a_2 - 4a_1$ . Therefore $a_2 = 11a_1$ , and the general solution is this case is $\boxed{(a,11a,19a,29a)}$ .
If $k=4$ , with the same reasoning we have $6a_1+2a_2 = 4a_2 - 4a_1 \Rightarrow a_2 = 5a_1$ , and the general solution in this case is $\boxed{(a,5a,7a,11a)}$ .
We claim there are no solutions with $k=3$ . Indeed, from $5a_1 + a_2 \mid 4a_2 - 4a_1$ we get $5a_1 + a_2 \leq 4a_2 - 4a_1 \iff a_2 \geq 3a_1$ , and now since $a_3 = \frac{3a_1+a_2}{2}$ , we have $a_3 \leq a_2$ , a contradiction.

The solution is complete.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

kevinatcausa

374 posts

kevinatcausa

#10 h Jul 18, 2011, 1:52 PM • 13 Y

Y by SFScoreLow, pog, centslordm, Adventure10, ike.chen, Mango247, and 7 other users

My way of looking at it (which is probably equivalent to some of the above):

As in -[]-'s solution, at least two of the sums must be strictly larger than $s_A/2$ , so $n_A \leq 4$ . For equality to hold, we must have $a_1+a_4=a_2+a_3=s_A/2.$ Writing $s_A=2n$ , this means our set has the form
$\{a,b,n-b,n-a\}.$
for some $a<b<n/2$ . We must have $a+b=2n/k$ and $a+n-b=2n/l$ . for some positive integers $k$ and $l$ , each of which must be at least $3$ by our assumption $a<b<n/2$ . Our assumption $b<n/2$ also implies $k<l$ . Adding, we have
$n+2a=n(\frac{2}{k}+\frac{2}{l}) >n.$
So $1/k+1/l>1/2$ . The only solutions to this are $k=3, l=4$ and $k=3, l=5$ . These lead to the two solutions given above.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Joao Pedro Santos

152 posts

Joao Pedro Santos

#11 h Jul 18, 2011, 2:55 PM • 6 Y

Y by pog, centslordm, Adventure10, and 3 other users

lchserious wrote:

The answers are $(1,5,7,11),(1,11,19,29),(2,10,14,22)$ and their multiples.
In fact, by applying several inequalities, we know that the answer has the form $(a,b,d-b,d-a)$ where $\frac{d}{2}>b>a,(a,b)=1$ .
To achieve the maximum value 4, we further need $d-(b-a)|2d$ and $a+b|2d$ ,
but since $d-(b-a)>\frac{d}{2}$ , we must have $3(a-b)=d$ .
All we need to do is to solve $a+b|3(b-a)$ , which is pretty easy.

In fact, $(2,10,14,22)=2(1,5,7,11)$ , so you didn't need to mention it.

Very easy problem, despite being problem 1...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Goutham

3130 posts

Goutham

#12 h Jul 18, 2011, 7:12 PM • 12 Y

Y by pog, centslordm, Adventure10, Mango247, MS_asdfgzxcvb, and 7 other users

All the possible divisibilities are $a_1+a_2|a_3+a_4, a_1+a_3|a_2+a_4, a_1+a_4|a_2+a_3$ , $a_2+a_3|a_1+a_4, a_2+a_4|a_1+a_3$ , and $a_3+a_4|a_1+a_2$ . Now, assume without loss of generality $a_1<a_2<a_3<a_4$ . Then the cases $a_2+a_4|a_1+a_3$ and $a_3+a_4|a_1+a_2$ are easily got rid of. And let us try to make $n_A=4$ . We have $a_1+a_4|a_2+a_3, a_2+a_3|a_1+a_4\Longrightarrow a_1+a_4=a_2+a_3$ . Now, we still have $a_1+a_3|a_2+a_4$ . Let $s=\frac{a_2+a_4}{a_1+a_3}$ . Then rearranging gives $(s-1)a_3+(s+1)a_1=2a_2$ and so, $(s-1)a_3<2a_2<2a_3\Longrightarrow (s-1)a_3=a_3$ and hence, $s=2\Longrightarrow 2(a_1+a_3)=(a_2+a_4)$ . Indeed, if $a_1=a, a_2=a+\alpha, a_3=a+\alpha+\beta, a_4=a+\alpha+\beta+\gamma$ . Then by the conditions $a_2+a_3=a_1+a_4, 2(a_1+a_3)=(a_2+a_4)$ , we have $\gamma=\alpha=2a+\beta$ . So, $A=\{a, 3a+\beta, 3a+2\beta, 5a+3\beta\}$ . Now, consider the condition $a_1+a_2|a_3+a_4$ . This gives $4a+\beta|8a+5\beta\Longrightarrow 4a+\beta|3\beta$ . Let $t=\frac{3\beta}{4a+\beta}$ . Rearranging gives $(3-t)\beta=4a>0\Longrightarrow t=1, 2$ . If $t=1$ , then $\beta=2a\Longrightarrow \boxed{A=\{a, 5a, 7a, 11a\}}$ and if $t=2$ , $\beta=8a\Longrightarrow \boxed{A=\{a, 11a, 19a, 29a\}}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Raja Oktovin

277 posts

Raja Oktovin

#13 h Jul 19, 2011, 12:00 AM • 5 Y

Y by pog, centslordm, Adventure10, Mango247, and 1 other user

I worried that they'll cut the point for the not-stating the permutations $(a,5a,7a,11a)$ $(5a,7a,11a,a)$ and so on. I hope not.

Easy and nice problem!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rustam

348 posts

rustam

#14 h Jul 19, 2011, 3:35 AM • 8 Y

Y by pog, centslordm, Adventure10, Mango247, and 4 other users

Raja Oktovin wrote:

I worried that they'll cut the point for the not-stating the permutations $(a,5a,7a,11a)$ $(5a,7a,11a,a)$ and so on. I hope not.

Easy and nice problem!

Don't worry, the problem asks for the set and permutation of the elements of the set is the same set.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathmdmb

1547 posts

mathmdmb

#15 h Jul 19, 2011, 4:00 AM • 6 Y

Y by pog, centslordm, HoRI_DA_GRe8, Adventure10, Mango247, and 1 other user

Icherious, your last divisibility is wrong. We have $a+b|6(a-b)$ . Also how did you conclude $d=3(b-a)$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shendrew7

795 posts

shendrew7

#90 h Mar 27, 2024, 4:02 AM

Y by

The maximal value of $n_A$ is 4, as 5 and 6 are unattainable as
$\frac{a_1+a_2+a_3+a_4}{2} < a_2+a_4, a_3+a_4 < a_1+a_2+a_3+a_4,$
where we assume WLOG $a_1<a_2<a_3<a_4$ . To attain 4, we notice we must have
$a_1+a_4 \mid a_2+a_3, \quad a_2+a_3 \mid a_1+a_4 \implies a_1+a_4 = a_2+a_3.$
Hence our set can be rewritten as $\{a,b,x-b,x-a\}$ , where $x<2b$ , and we also require
$x+a-b \mid 2x-2(x+a-b) = 2(b-a) \implies x+a-b = 2(b-a) \implies x = 3b-3a.$ $a+b \mid 2x = 6(b-a) \implies a+b \mid 12a \implies 12a = (a+b), \ldots, 5(a+b).$
Testing all 5 cases, we find the only solutions $\boxed{(a,5a,7a,11a),~(a,11a,19a,29a) \quad a \in \mathbb{N}}$ . $\blacksquare$

This post has been edited 1 time. Last edited by shendrew7, Mar 27, 2024, 4:03 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

VideoCake

9 posts

VideoCake

#91 h Mar 27, 2024, 6:33 PM

Y by

The answer is $n_A = 4$ , achieved by the sets $A = \{t, 11t, 19t, 29t\}$ and $A = \{t, 5t, 7t, 11t\}$ for any positive integer $t$ . One can check that they work. Without loss of generality, $a_1 < a_2 < a_3 < a_4$ .

Claim 1. We have $n_A \leq 4$ .
Proof. If we have two positive integers $a$ and $b$ that divide their sum, then they are equal to each other. Similarly, if $n_A > 4$ , then at least two of $(a_1 + a_2, a_3 + a_4)$ , $(a_1 + a_3, a_2 + a_4)$ and $(a_1 + a_4, a_2 + a_3)$ have equal sums. However, $a_1 + a_2 < a_3 + a_4$ and $a_1 + a_3 < a_2 + a_4$ , so we have a contradiction. $\square$
In particular, if $n_A = 4$ , then $a_1 + a_4 = a_2 + a_3$ .

Claim 2. We achieve $n_A = 4$ with only the sets $A = \{t, 11t, 19t, 29t\}$ and $A = \{t, 5t, 7t, 11t\}$ for any positive integer $t$ .
Proof We let $a_1 = x$ , $a_2 = x + y$ , $a_3 = x + y + z$ and $a_4 = x + y + z + y$ to homogenize the condition $a_1 + a_4 = a_2 + a_3$ . In order to achieve $n_A = 4$ , we need:
$2x + y = a_1 + a_2 \mid s_A = 4x + 4y + 2z$ $2x + y + z = a_1 + a_3 \mid s_A = 4x + 4y + 2z$ This is equivalent to $2x + y \mid 2y + 2z$ and $2x + y + z \mid 2y$ . Notice how the second condition implies $2x + y + z = 2y$ , because $2x + y + z > y$ , which is the second largest possible divisor of $2y$ . We get $2x + z = y$ . Substituting that into the first condition, we obtain $4x + z \mid 4x + 4z \implies 4x + z \mid 3z.$ using the same argument as before, we have $4x + z > z$ , so either $4x + z = \frac{3}{2}z$ or $4x + z = 3z$ . In other words, $8x = z$ or $2x = z$ . This implies $10x = y$ or $4x = y$ . We now reverse the substitution at the beginning of the proof to get
$(a_1, a_2, a_3, a_4) \in \{(t, 11t, 19t, 29t), (t, 5t, 7t, 11t)\}$ completing the solution. $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Shreyasharma

682 posts

Shreyasharma

#92 h Mar 28, 2024, 2:52 AM

Y by

Without loss of generality let $a_1 < a_2 < a_3 < a_4$ . Note then that clearly,
$\begin{align*} a_3 + a_4 < s_A < 2(a_3 + a_4) \end{align*}$ and hence $a_3 + a_4 \nmid s_A$ . Similarly as,
$\begin{align*} a_1 + a_3 &\leq a_2 + a_4 \iff (a_3 - a_4) \leq (a_2 - a_1) \end{align*}$ we cannot have $a_2 + a_4 \mid s_A$ . This proves the bound of $n_A = 4$ .

Now it remains to find all sets $A$ of four distinct positive integers that achieve $n_A = 4$ . Begin by noting we must have,

$a_2 + a_3 \equiv 0 \pmod{a_1 + a_4}$
$a_1 + a_4 \equiv 0 \pmod{a_2 + a_3}$
$a_3 + a_4 \equiv 0 \pmod{a_1 + a_2}$
$a_2 + a_4 \equiv 0 \pmod{a_1 + a_3}$

It immediately follows from the first two bullets that $a_1 + a_4 = a_2 + a_3$ . From the remaining bullets we substitute $a_4 = a_2 + a_3 - a_1$ to find,
$\begin{align*} a_3 + a_4 \equiv a_2 + 2a_3 - a_1 &\equiv 0 \pmod{a_1 + a_2} \iff a_1 + a_2 \mid a_2 + 2a_3 - a_1\\ a_2 + a_4 \equiv 2a_2 + a_3 - a_1 &\equiv 0 \pmod{a_1 + a_3} \iff a_1 + a_3 \mid 2a_2 + a_2 - a_1 \end{align*}$ The relations then become,
$\begin{align*} a_1 + a_2 \mid a_2 + 2a_3 - a_1 \iff a_1 + a_2 \mid 2( a_3 - a_1)\\ a_1 + a_3 \mid 2a_2 + a_3 - a_1 \iff a_1 + a_3 \mid 2(a_2 - a_1) \end{align*}$ Thus let,
$\begin{align*} m(a_1 + a_2) = 2(a_3 - a_1)\\ n(a_1 + a_3) = 2(a_2 - a_1) \end{align*}$ This rearranges to,
$\begin{align*} (m + 2)a_1 = 2a_3 - ma_2\\ (n + 2)a_1 = 2a_2 - na_3 \end{align*}$ Note that the last equation forces $n = 1$ as for $n > 2$ we find $2a_2 - 2a_3 < 0$ . Thus we have,
$\begin{align*} (m + 2)a_1 &= 2a_3 - ma_2\\ 3a_1 &= 2a_2 - a_3 \end{align*}$ Now we have,
$\begin{align*} (m + 2)a_1 &= 2(a_3 - 2a_2) - (m - 4)a_2\\ (m + 8)a_1 &= (4 - m)a_2\\ \frac{a_1}{a_2} &= \frac{4 - m}{m + 8} \end{align*}$ Note that clearly $m < 4$ . Thus we find that,
$\begin{align*} \frac{a_1}{a_2} \in \left\{ \frac{1}{3}, \frac{1}{5}, \frac{1}{11} \right\} \end{align*}$ We're now at the home-stretch. We take cases on $\frac{a_1}{a_2}$ .

Case 1: If $a_2 = 3a_1$ , then $a_3 = 3a_1$ contradiction as then $a_2 = a_3$ .

Case 2: If $a_2 = 5a_1$ , then $a_3 = 7a_1$ and $a_4 = 1 1a_1$ . This can be checked to always work.

Case 3: If $a_2 = 1 1a_1$ , then $a_3 = 19a_1$ and hence $a_4 = 29a_1$ , and this always works as well.

Our solution set is then for $a \in \mathbb{Z}^+$ :
$\begin{align*} \boxed{\left\{ (a_1, 5a_1, 7a_1, 11a_1), (a_1, 11a_1, 19a_1, 29a_1) \right\}} \end{align*}$

This post has been edited 1 time. Last edited by Shreyasharma, Mar 28, 2024, 2:53 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

RedFireTruck

4221 posts

RedFireTruck

#93 h May 5, 2024, 3:55 PM

Y by

WLOG let $a_1<a_2<a_3<a_4$ . Since $a_1+a_2<a_3+a_4$ and $a_1+a_3<a_2+a_4$ , $n_A\le4$ , with equality only possible when $a_1+a_4=a_2+a_3$ .

Let the numbers be $\{a, b, n-b, n-a\}$ for $0<a<b<\frac{n}2$ .

We want $(n-(b-a))|(2n)$ . $n-(b-a)\ge \frac{2n}{2}$ and $n-(b-a)\le \frac{2n}{4}$ are clearly absurd, so $n-(b-a)=\frac{2n}3$ or $b-a=\frac{n}{3}$ .

We also want $(a+b)|(2n)$ . As $b-a=\frac{n}{3}$ , $\frac{2n}{3}>a+b>\frac{2n}{6}$ so $a+b=\frac{2n}4=\frac{n}{2}$ or $a+b=\frac{2n}{5}$ .

The first case gives $\{k, 5k, 7k, 11k\}$ and the second case gives $\{k, 11k, 19k, 29k\}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ezpotd

1263 posts

ezpotd

#94 h Aug 31, 2024, 7:10 PM

Y by

The answers are $a_1:a_2:a_3:a_4 = 1:5:7:11$ and $a_1:a_2:a_3:a_4 = 1:11:19:29$ , both of which clearly work.

Sort $a$ . Consider the pairs $a_1 + a_2, a_3+ a_4$ and $a_1 + a_3, a_2 + a_4$ . One of the elements in each pair is clearly larger than the other, so at most one can divide into the total sum. Then if we want $n_a = 4$ , we need $a_1 + a_4 = a_2 + a_3$ . Thus let $a_1 = x, a_2 = y, a_3 = z$ , we then require $x + y \mid 2(y + z), x + z \mid 2(y + z)$ . Let $x + y = d, x + z = e, y + z = f$ , then we require $d \mid 2f, e \mid 2f$ , and $d,e,f$ satisfy the triangle inequality to make $x,y,z$ positive. By size then, we clearly need $e > \frac f2$ , so $e = \frac{2f}{3}$ . Since $d,e$ are distinct, we can either have $d = \frac{2f}{4}, d = \frac{2f}{5}$ . In the first case, we get $d:e:f = 6:8:12, x:y:z = 1:5:7$ , so $a_1:a_2:a_3 = 1:5:7$ , since $a_1 + a_4 = a_2 + a_3$ gives $a_1:a_2:a_3:a_4 = 1:5:7:11$ . In the second case, we get $d:e:f = 12:18:20, x:y:z = 1:11:19$ , so $a_1:a_2:a_3:1:11:19$ , since $a_1 + a_4 = a_2 + a_3$ , gives $a_1:a_2:a_3:a_4 = 1:11:19:29$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pie854

243 posts

pie854

#95 h Oct 12, 2024, 9:39 PM

Y by

WLOG assume that $a_1>a_2>a_3>a_4$ . We have $n_A\leq 4$ since $a_1+a_2\nmid a_3+a_4$ and $a_1+a_3\nmid a_2+a_4$ . Notice that $n_A=4$ is achievable: $5+1\mid 11+7$ , $7+1\mid 11+5$ , $7+5\mid 11+1$ , $11+1\mid 7+5$ .

Now, we need to find all $A$ such that $n_A=4$ . In that case we must have $a_1+a_4=a_3+a_2, \ a_3+a_4\mid a_1+a_2, \ a_2+a_4\mid a_1+a_3 \qquad (1)$ Take $a_4=a$ , $a_3=a+b$ , $a_2=a+b+c$ , $a_1=a+b+c+d$ . Then $a_1+a_4=a_3+a_2\implies b=d.$ Now, $(1)$ implies that (replacing $d$ ): $\begin{align*} & 2a+b \mid 2a+3b+2c \Rightarrow 2a+b\mid 2b+2c \qquad (2) \\ & 2a+b+c \mid 2a+3b+c \Rightarrow 2a+b+c\mid 2b \qquad (3)\end{align*}$ $(3)$ implies that $2a+b+c=2b$ , since $2(2a+b+c)>2b$ . So $c=b-2a$ and so $(2)$ implies that $2a+b\mid 4b-4a$ . If $2a+b=4b-4a$ then $b=2a$ but then $c=0$ , a contradiction. Thus either $2(2a+b)=4b-4a$ or $3(2a+b)=4b-4a$ . In the first case $b=4a$ , $c=2a$ and in the second $b=10a$ , $c=8a$ . Returning back we get $(a_1,a_2,a_3,a_4)\in \{(29a, 19a, 11a, a), (11a, 7a, 5a, a)\}.$ Thus the answer is $\{29k,19k,11k,k\}$ for any $k\in \mathbb N$ and $\{11k,7k,5k,k\}$ for any $k\in \mathbb N$ . These clearly work.

This post has been edited 2 times. Last edited by pie854, Oct 12, 2024, 9:41 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

620 posts

cursed_tangent1434

#96 h Dec 21, 2024, 2:54 PM

Y by

Another old solution, which I am posting for storage. We claim that the maximum of $n_A$ is $4$ . It is easy to see that this $n_A\leq 4$ since always $a_2+a_4>a_1+a_3$ and $a_3+a_4>a_1+a_2$ which contradicts two of the six possible divisibilities. Now, we find all sets for which $n_A=4$ is achievable.

Note that we must have, $a_1+a_4\leq a_2+a_3$ and $a_2+a_3 \leq a_1+a_4$ which implies that $a_4=a_2+a_3-a_1$ . Further,
$a_1+a_3 \mid a_2+a_4 \implies a_1+a_3 \mid 2a_2+a_3-a_1 \implies a_1+a_3 \mid 2a_2-2a_1$ Now, $2a_2-2a_1 < 2a_3-2a_1<2a_3+2a_1=2(a_1+a_3)$
Thus, $2a_2-2a_1=0 \implies a_1=a_2$ which is impossible or $2a_2-2a_2=a_1+a_3$ which gives us that $a_3=2a_2-3a_1$ .
Now note that this means $a_1+a_2\mid a_3+a_4 \implies a_1+a_2 \mid 12a_2$ . Thus, $a_1=\frac{(12-k)a_2}{k}$ . Thus, clearly $k<12$ . Further, $a_4=3a_2-4a_1 \implies 3a_2\geq \frac{(48-4k)a_2}{k}\implies k\geq 8$ . Now, we check.

It is easy to check that $k=8$ and $k=9$ yield no solutions. $k=10$ yields the solution set $\{r,5r,7r,11r\}$ for all positive integers $r$ and $k=11$ gives us $\{r,11r,19r,29r\}$ for all positive integers $r$ . Thus, these are the only solutions and we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

de-Kirschbaum

198 posts

de-Kirschbaum

#97 h Feb 2, 2025, 11:27 PM

Y by

First let us relable the variables as $a,b,c,d$ . WLOG let $a<b<c<d$ . Note that for any pair, say $a+c$ to divide $a+b+c+d$ it is sufficient that they divide $a+b+c+d-a-c=b+d$ . Note now that $a+b<c+d$ so at best this breakup contributes one division via $a+b | c+d$ , similarly we have $a+c<b+d$ so at best one with $a+c|b+d$ , then we can have $a+d=b+c$ contributing two divisions $a+d|b+c,b+c|a+d$ . Thus $n_A\leq 4$ .

Now we will derive all tuples satisfying $n_A =4$ . Note that $a+d=b+c \implies d-c=b-a=x$ . Rewriting we get $a,a+x,c,c+x$ and we want to satisfy $2a+x|2c+x, a+c|a+c+2x$ . The second divisibility gives ups $a+c|2x$ . Note that if $a+c<2x$ , then $a+c \leq x \implies x \geq a+a+(c-a)>2a+x$ which is impossible so $a+c=2x$ . From the former divisibility, since $2a+x<2c+x$ we have $2a+x|2c+x-2a-x=2(c-a)=2(2x-2a)=4(x-a)$ . Thus $2a+x|4(x-a) \implies 2|x$ , let $x=2k$ we have $a+k|2(2k-a)$ . Now, if $a+k =4k-2a$ we will have $3a=3k \implies a=k \implies k+c=4k \implies c=3k$ . However, then $b=3k=c$ is a contradiction.

Thus we have $a+k<4k-2a \implies a+k|3k-3a$ . If equality holds in this case we have $2a=k$ , letting $k=2t$ would give us the set of solutions $(t,5t,7t,11t)$ . If equality doesn't hold in this case then $a+k|2k-4a$ . If equality holds here then $5a=k$ , letting $k=5t$ gives us the set of solutions $(t, 11t, 19t, 29t)$ . If equality doesn't hold then $a+k|k-5a$ which is absurd because this would require $6a\leq 0$ while $a>0$ .

Thus the set of numbers that work are $(t,5t,7t,11t),(t,11t,19t, 29t)$ and all their permutations for every positive integer $t$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

megahertz13

3183 posts

megahertz13

#98 h Feb 10, 2025, 2:37 AM

Y by

Don't know why, but this feels like an easy A1 despite this being a long solution

The sets $\{a_1,a_2,a_3,a_4\}$ that satisfy the property that $p_A$ is maximal are $\{x,5x,7x,11x\}$ and $\{y,11y,19y,29y\}$ for any positive integers $x$ and $y$ , and permutations of these. Notice that these two families of sets both yield $p_A=4$ . This is maximal as $(i,j)=(2,4)$ and $(i,j)=(3,4)$ are clearly both invalid (where we assume that $a_1<a_2<a_3<a_4$ ). This only leaves $\dbinom{4}{2}-2=4$ pairs $(i,j)$ remaining, so this is maximal and attainable. We prove that these are the only solutions with maximal $p_A$ . Suppose otherwise, and by WLOG that $a_1<a_2<a_3<a_4.$ Notice that $a_1+a_2+a_3+a_4\equiv 0\pmod {a_1+a_4}\implies a_2+a_3\equiv 0\pmod {a_1+a_4}.$ Similarly, we have $a_1+a_4\equiv 0\pmod {a_2+a_3}.$ It is clear that $a_1+a_4=a_2+a_3\implies a_4=a_2+a_3-a_1.$ Note that $2<\frac{a_1+a_2+a_3+a_4}{a_1+a_3}=2\cdot\frac{a_2+a_3}{a_1+a_3}<2\cdot \frac{2a_3}{a_1+a_3}<\frac{4a_3}{a_3}=4,$ so $\frac{a_1+a_2+a_3+a_4}{a_1+a_3}=3$ $\implies 2a_1+2a_3=a_2+(a_2+a_3-a_1)$ $\implies 2a_1+2a_3=2a_2+a_3-a_1$ $\implies 3a_1+a_3=2a_2$ $\implies a_3=2a_2-3a_1.$ Now, we know that $a_1+a_2+a_3+a_4$ $=a_1+a_2+2a_2-3a_1+a_2+(2a_2-3a_1)-a_1$ $=6a_2-6a_1.$ Additionally, we have $2<\frac{6a_2-6a_1}{a_1+a_2}<6.$ We split this into casework: First, we have $\frac{6a_2-6a_1}{a_1+a_2}=3\implies 6a_2-6a_1=3a_1+3a_2\implies a_2=3a_1.$ However, this would give $a_3=6a_1-3a_1=3a_1,$ but we need $a_2<a_3$ . There are no solutions here. Second, we have $\frac{6a_2-6a_1}{a_1+a_2}=4\implies 6a_2-6a_1=4a_1+4a_2\implies a_2=5a_1.$ This gives the $\{x,5x,7x,11x\}$ solution discussed earlier (with the $a_1$ being $x$ ). Finally, we have $\frac{6a_2-6a_1}{a_1+a_2}=5\implies 6a_2-6a_1=5a_1+5a_2\implies a_2=11a_1.$ This gives the $\{y,11y,19y,29y\}$ solution discussed earlier (with the $a_2$ being $y$ ). This concludes the problem.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mr.Sharkman

498 posts

Mr.Sharkman

#99 h Feb 10, 2025, 2:46 AM

Y by

Why is this 10 MOHS :skull:

The largest possible value of $n_{A}$ is $4.$ First, we will show that no higher $n_{A}$ is possible. Assume for the sake of contradiction that $n_{A} \ge 5.$ Then, there would be at least two sets of permutations $\{i, j, k, \ell\}$ of $\{1, 2, 3, 4\}$ where $a_{i}+a_{j}, a_{k}+a_{\ell} \mid s_{A}.$ Notice that $a_{k}+a_{\ell}, a_{i}+a_{j} \neq s_{A},$ so
$a_{k}+a_{\ell}, a_{i}+a_{j} \le \frac{s_{A}}{2}.$ But, $a_{i}+a_{j}+a_{k}+a_{\ell} = \frac{s_{A}}{2},$ so $a_{i}+a_{j} = a_{k}+a_{\ell} = \frac{s_{A}}{2}.$ So, we have that
$a_{1}+a_{i} = \frac{s_{A}}{2},$ and
$a_{1}+a_{j} = \frac{s_{A}}{2},$ where $i \neq a_{j}.$ But, then this contradicts the fact that the numbers in $A$ are distinct. Thus, $n_{A} \le 4.$

Next, we find when $n_{A} = 4.$ We have that
$a_{1}+a_{i} = a_{j}+a_{k} = \frac{s_{A}}{2},$ where $i \neq j \neq k,$ and $i,j,k \in \{2,3,4\}.$ Since the order of the numbers does not matter, we can assume WLOG that $a_{1}+a_{2} = \frac{s_{A}}{2}.$ Now, we have two other subsets of $A$ with cardinality $2$ that have their sum a divisor of $s_{A}.$ We know that they must share an element, since otherwise we will get two of the "permutations" from the proof that $n_{A} \le 4$ earlier. Assume WLOG that this is common element is $a_{1}.$ Then,
$a_{1}+a_{3} = \frac{s_{A}}{a},$ and
$a_{1}+a_{4} = \frac{s_{A}}{b}.$ So,
$a_{4}-a_{3} = \frac{s_{A}}{b}-\frac{s_{A}}{a},$ and hence
$a_{4} = s_{A}\left(\frac{1}{4}+\frac{1}{2b}-\frac{1}{2a} \right)$ and
$a_{4} = s_{A}\left(\frac{1}{4}-\frac{1}{2b}+\frac{1}{2a} \right).$ Now,
$a_{1} = s_{A}\left(-\frac{1}{4}+\frac{1}{2b}+\frac{1}{2a} \right),$ and
$a_{2} = s_{A}\left(\frac{3}{4}-\frac{1}{2b}-\frac{1}{2a}\right).$ So, we need to have
$\frac{3}{2} > \frac{1}{a}+\frac{1}{b} > \frac{1}{2},$ and
$\frac{1}{a}+\frac{1}{2} > \frac{1}{b} > \frac{1}{a} - \frac{1}{2}.$ Notice that $a,b \ge 3,$ since $a,b \ge 2,$ and $a,b \neq 2.$ So, the last inequality chain is redundant. In fact, the only meaningful inequality is
$\frac{1}{a}+\frac{1}{b} > \frac{1}{2}.$ Assume WLOG that $a \ge b$ (this will only swap $a_{3}$ and $a_{4},$ which have been symmetric until now). Then, $a < 4,$ so $a = 3.$ So, $b = 3, 4, 5.$

If $(a,b) = \left(3, 3 \right),$ then $a_{3}, a_{4} = \frac{s_{A}}{4},$ and so $a_{1} = \frac{s_{A}}{12},$ and thus $a_{2}=\frac{5s_{A}}{12}.$ So,
$A = \{n, 3n, 3n, 5n\},$ where $n$ is a positive integer.

If $(a,b) = \left(3, 4\right),$ we get that $A = \{n, 11n, 5n, 7n\}.$

If $(a,b) = \left(3,5\right),$ we find that $A = \{n, 29n, 19n, 11n\}.$ So, we have completed the proof.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Maximilian113

575 posts

Maximilian113

#100 h Feb 10, 2025, 3:00 AM

Y by

wow, three posts at around the same time?!?! :O

Clearly if we have at least $5$ pairs there will be two "conjugate" pairs of pairs that each divide $s,$ implying that some two numbers are equal, contradiction.

Thus $n_A =4.$ WLOG assume that $a_1 \leq a_2 \leq a_3 \leq a_4.$ Then $a_i+a_j$ divides $s$ if and only if $a_i+a_j \leq \frac{s}{2}.$ Thus $a_1+a_4, a_2+a_3, a_1+a_2, a_1+a_3$ are the pairs that divide $s.$ From the first two it follows that $a_1+a_4=a_2+a_3,$ thus $s=2(a_2+a_3).$ The latter two pairs thus imply $\frac{2(a_3-a_1)}{a_1+a_2}, \frac{2(a_2-a_1)}{a_1+a_3} \in \mathbb Z^+.$ But, observe that their product is $\frac{4(a_3-a_1)(a_2-a_1)}{(a_1+a_2)(a_1+a_3)} < 4.$ Therefore this product can only take the values $1, 2, 3.$

We now proceed with casework.

$\text{Case 1: Product is 1.}$ Then the two parts of the product are each equal to $1.$ Hence $2(a_3-a_1)=a_1+a_2, 2a_2-2a_1=a_1+a_3 \implies 2a_3=3a_1+a_2, 2a_2=3a_1+a_3.$ But this yields $a_2=a_3,$ contradiction.

$\text{Case 2: Product is 2.}$ Then the parts of the product are $1, 2.$ The only way this can happen is if $a_3-a_1=a_1+a_2, 2a_2-2a_1=a_1+a_3.$ These yield $a_3=2a_1+a_2, 2a_2=3a_1+a_3.$ Thus $a_2=5a_1, a_3=7a_1, \implies a_4=11a_1.$ Hence we have the solution $(k, 5k, 7k, 11k)$ for positive integers $k.$

$\text{Case 3: Product is 3.}$ Then the parts of the product are $1, 3.$ Thus $2a_3=5a_1+3a_2, 2a_2=3a_1+a_3.$ This gives $a_2=11a_1, a_3=19a_1, a_4=29a_1.$ Thus we have the solution $(k, 11k, 19k, 29k)$ for positive integers $k.$

To summarize, the solutions are $(k, 5k, 7k, 11k), (k, 11k, 19k, 29k)$ for positive integers $k.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

megahertz13

3183 posts

megahertz13

#101 h Feb 10, 2025, 8:11 PM

Y by

Mr.Sharkman wrote:

Why is this 10 MOHS :skull:

The largest possible value of $n_{A}$ is $4.$ First, we will show that no higher $n_{A}$ is possible. Assume for the sake of contradiction that $n_{A} \ge 5.$ Then, there would be at least two sets of permutations $\{i, j, k, \ell\}$ of $\{1, 2, 3, 4\}$ where $a_{i}+a_{j}, a_{k}+a_{\ell} \mid s_{A}.$ Notice that $a_{k}+a_{\ell}, a_{i}+a_{j} \neq s_{A},$ so
$a_{k}+a_{\ell}, a_{i}+a_{j} \le \frac{s_{A}}{2}.$ But, $a_{i}+a_{j}+a_{k}+a_{\ell} = \frac{s_{A}}{2},$ so $a_{i}+a_{j} = a_{k}+a_{\ell} = \frac{s_{A}}{2}.$ So, we have that
$a_{1}+a_{i} = \frac{s_{A}}{2},$ and
$a_{1}+a_{j} = \frac{s_{A}}{2},$ where $i \neq a_{j}.$ But, then this contradicts the fact that the numbers in $A$ are distinct. Thus, $n_{A} \le 4.$

Next, we find when $n_{A} = 4.$ We have that
$a_{1}+a_{i} = a_{j}+a_{k} = \frac{s_{A}}{2},$ where $i \neq j \neq k,$ and $i,j,k \in \{2,3,4\}.$ Since the order of the numbers does not matter, we can assume WLOG that $a_{1}+a_{2} = \frac{s_{A}}{2}.$ Now, we have two other subsets of $A$ with cardinality $2$ that have their sum a divisor of $s_{A}.$ We know that they must share an element, since otherwise we will get two of the "permutations" from the proof that $n_{A} \le 4$ earlier. Assume WLOG that this is common element is $a_{1}.$ Then,
$a_{1}+a_{3} = \frac{s_{A}}{a},$ and
$a_{1}+a_{4} = \frac{s_{A}}{b}.$ So,
$a_{4}-a_{3} = \frac{s_{A}}{b}-\frac{s_{A}}{a},$ and hence
$a_{4} = s_{A}\left(\frac{1}{4}+\frac{1}{2b}-\frac{1}{2a} \right)$ and
$a_{4} = s_{A}\left(\frac{1}{4}-\frac{1}{2b}+\frac{1}{2a} \right).$ Now,
$a_{1} = s_{A}\left(-\frac{1}{4}+\frac{1}{2b}+\frac{1}{2a} \right),$ and
$a_{2} = s_{A}\left(\frac{3}{4}-\frac{1}{2b}-\frac{1}{2a}\right).$ So, we need to have
$\frac{3}{2} > \frac{1}{a}+\frac{1}{b} > \frac{1}{2},$ and
$\frac{1}{a}+\frac{1}{2} > \frac{1}{b} > \frac{1}{a} - \frac{1}{2}.$ Notice that $a,b \ge 3,$ since $a,b \ge 2,$ and $a,b \neq 2.$ So, the last inequality chain is redundant. In fact, the only meaningful inequality is
$\frac{1}{a}+\frac{1}{b} > \frac{1}{2}.$ Assume WLOG that $a \ge b$ (this will only swap $a_{3}$ and $a_{4},$ which have been symmetric until now). Then, $a < 4,$ so $a = 3.$ So, $b = 3, 4, 5.$

If $(a,b) = \left(3, 3 \right),$ then $a_{3}, a_{4} = \frac{s_{A}}{4},$ and so $a_{1} = \frac{s_{A}}{12},$ and thus $a_{2}=\frac{5s_{A}}{12}.$ So,
$A = \{n, 3n, 3n, 5n\},$ where $n$ is a positive integer.

If $(a,b) = \left(3, 4\right),$ we get that $A = \{n, 11n, 5n, 7n\}.$

If $(a,b) = \left(3,5\right),$ we find that $A = \{n, 29n, 19n, 11n\}.$ So, we have completed the proof.

yes this was 0 mohs

where are isl mohs ratings

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mr.Sharkman

498 posts

Mr.Sharkman

#102 h Feb 10, 2025, 9:23 PM

Y by

Bro this is IMO 2011/1 :skull: But I think that this should have been N1, and not A1

This post has been edited 1 time. Last edited by Mr.Sharkman, Feb 10, 2025, 9:24 PM

Z K Y