3

I saw this problem on a maths challenge book. 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\le i\le j\le4$ for which $a_i +a_j$ divides $S\{A\}$. Find all sets of four distinct positive integers which achieve the largest value of $n_A$.

I was thinking that ${4\choose 2}$ is $6$. So there should be six possible ways to pair all the elements of set $A$ that will divide $S\{A\}$ provided that $a_i + a_i$ is not allowed. $n_A$ will have the value of $6$ if what I said is possible. Well this is only my first thought, other ideas will be appreciated .

zoli
  • 20,452
Abu Bardewa
  • 411
  • If $a_1<a_2<a_3<a_4$ then $a_3+a_4>\frac{1}{2}S{A}$ so that $(a_3+a_4)\nmid S{A}$. Similarly $(a_2+a_4)\nmid S{A}$. So $n_A\le 4$. – Marconius Sep 27 '15 at 22:30
  • @Marconius the answer if trimmed . I cannot see anyway , it's less than or equal to instead of less than. – Abu Bardewa Sep 27 '15 at 22:33
  • It's less than or equal to. That is to say $n_A$ cannot be 6 and can be at most 4. There may be further reductions. – Marconius Sep 27 '15 at 22:44

1 Answers1

1

WLOG assume that $a_1<a_2<a_3<a_4$. Then $$a_3+a_4>a_1+a_2 \implies a_3+a_4>\frac{1}{2}S \implies (a_3+a_4)\nmid S$$ and $$a_2+a_4>a_1+a_3 \implies a_2+a_4>\frac{1}{2}S \implies (a_2+a_4)\nmid S$$ So two of the six possible combinations definitely don't divide the sum. So $n_A$ is at most four.

We have maximal $n_A=4$, because there is a solution for $n_A=4$, namely

$$(a_1,a_2,a_3,a_4)=k(1,5,7,11),\quad k\in\mathbb{Z}^+$$

This was constructed by trial and error after noting that if $n_A=4$ then:

  • either $a_1+a_4$ or $a_2+a_3$ exceeds $\frac{1}{2}S$ (hence cannot divide) unless $a_1+a_4=a_2+a_3=\frac{1}{2}S$
  • $a_1+a_2<a_1+a_3<a_1+a_4$ so $S$ is a higher multiple of $(a_1+a_2)$ than it is of $(a_1+a_3)$, and is a higher multiple of $(a_1+a_3)$ than it is of $a_1+a_4$

So first try with multiples of $2$, $3$ and $4$, resulting in the set of simultaneous equations

$$\begin{array}{rcccc} S=&2a_1&&&+2a_4 \\ S=&&2a_2&+2a_3 \\ S=&3a_1&&+3a_3 \\ S=&4a_1&+4a_2 \\ \end{array}$$

This solves to $a_1=\frac{S}{24},a_2=\frac{5S}{24},a_3=\frac{7S}{24},a_4=\frac{11S}{24}$.

Since the $a_i$ must be integral, take $S=24k,a_1=k,a_2=5k,a_3=7k,a_4=11k$.

I will leave it up to the reader to see whether multiples other than $3$ and $4$ can also produce viable solutions, noting that solutions are not viable if one of the numbers (especially $a_1$) is a negative multiple of $S$.

Marconius
  • 5,635
  • Nice answer. But can I ask what is WLOG at the top if I may please . – Abu Bardewa Sep 28 '15 at 18:30
  • @AbuBardewa - it means Without Loss Of Generality. This is particularly true here because we are only interested in sets and not in ordered 4-tuples $(a_1,a_2,a_3,a_4)$. – Marconius Sep 28 '15 at 18:47