Distinct sums from nine $9$ integers

Question

$9$ distinct integers are split into $3$ sets of $3$ integers each. $1$ integer is taken from each of the $3$ sets and the $3$ integers so obtained are added. Each such possible sum is equal to a distinct integer in $\{ 1,2, \dots, 27 \}$. What is the minimum possible value of the greatest of these $9$ integers ?

---

My attempt so far:-

Let the numbers be $a_1<a_2<a_3<a_4<a_5<a_6<a_7<a_8<a_9$

Now I started making cases of what values could $a_9$ potentially have

I started taking possible cases for $a_9$ from $0$, but I am not able to form a case when any possible sum from the three groups lie between $1$ to $27$, let alone them being distinct.

Reason for me to start from 0 was since we want to minimize $a_9$.

So my initial few cases were as follows :-

1. -8,-7,-6,-5,-4,-3,-2,-1,0 (This is not possible since the sums will always be negative)

2. -7,-6,-5,-4,-3,-2,-1,0,1 (Here also I was not able to form positive sum by splitting the numbers into 3 groups)

3. -6,-5,-4,-3,-2,-1,0,1,2 (same reasoning as (2))

4. -5,-4,-3,-2,-1,0,1,2,3 (from here on it is getting tricky for me to think if a legitimate group of 3 numbers can be made)

Please help me out with what should be the efficient way to solve this

Answer 1

The minimum possible value is

$11$.

There's a nice theoretical trick we can use to find this, and that works well for similar problems.

Let the three sets be $A=\{a_1,a_2,a_3\}$, $B=\{b_1,b_2,b_3\}$, $C=\{c_1,c_2,c_3\}$, where $a_1<a_2<a_3$ etc and $a_3<b_3<c_3$.

Consider the following product: $$p(x)=\left(x^{a_1}+x^{a_2}+x^{a_3}\right)\left(x^{b_1}+x^{b_2}+x^{b_3}\right)\left(x^{c_1}+x^{c_2}+x^{c_3}\right)$$

If we expand it out, we get $27$ terms, each of the form $x^{a_i+b_j+c_k}$ - but we know what these sums are! In other words, $$p(x) = x+x^2+\cdots + x^{27} = x\frac{x^{27}-1}{x-1}$$

where we've used the fact that $p(x)$ is the sum of a geometric series.

Now, using the fact that $A^3-1=(A-1)\left(1+A+A^2 \right)$, we have

$$\begin{align} x^{27}-1 &=\left(x^9-1\right)\left(1+x^9+x^{18}\right) \\ &=\left(x^3-1\right)\left(1+x^3+x^6\right)\left(1+x^9+x^{18}\right) \\ &=\left(x -1\right)\left(1+x+x^2\right)\left(1+x^3+x^6\right)\left(1+x^9+x^{18}\right) \end{align}$$

so that $$p(x)=\color{blue}{x}\left(1+x+x^2\right)\left(1+x^3+x^6\right)\left(1+x^9+x^{18}\right)$$

Apart from that blue $x$, this is already in the form we need. We can multiply the blue $x$ into any of the other brackets; eg $$p(x)=\left(x+x^2+x^3\right)\left(1+x^3+x^6\right)\left(1+x^9+x^{18}\right)$$

This corresponds to the three sets $\{1,2,3\}$, $\{0,3,6\}$, $\{0,9,18\}$ and you can check that these meet the criterion for having sums from $1$ to $27$. However, not all the numbers are distinct!

To fix this, we can essentially repeat what we did with the blue $x$; multiplying the brackets by powers of $x$ will still leave the right form (ie a product of three sums of three powers of $x$).

$$p(x)=\left(x^\alpha+x^{1+\alpha}+x^{2+\alpha}\right)\left(x^\beta+x^{3+\beta}+x^{6+\beta}\right)\left(x^\gamma+x^{9+\gamma}+x^{18+\gamma}\right)$$

where $\alpha+\beta+\gamma=1$.

This makes the problem much simpler; we want to minimise the maximum of $\{2+\alpha,6+\beta,18+\gamma\}$ subject to $\alpha+\beta+\gamma=1$ for integers $\alpha,\beta,\gamma$.

With a bit of work, it's not hard to find

$\alpha=8$, $\beta=0$, $\gamma=-7$

giving the form

$$p(x)=\left(x^7+x^8+x^9\right)\left(1+x^3+x^6\right)\left(x^{-7}+x^2+x^{11}\right)$$

This corresponds to the three sets

$\{7,8,9\}$, $\{0,3,6\}$, $\{-7,2,11\}$, which is optimal.

---

But wait, how do we know this is the only factorisation? Perhaps there's another way of writing $p(x)$ as a product that will give a different answer? In this case, no! We can look at the factorisation of $p(10)=111\ldots1$ ($27$ digits) and see that this is unique (there's a bit of case work but not much).

Answer 2

We have nine distinct integers in three groups of three integers, say $$a_1<a_2<a_3,\qquad b_1<b_2<b_3,\qquad c_1<c_2<c_3.$$ As each sum of the form $a_i+b_j+c_k$ yields a distinct integer from $1$ to $27$, and there are $27$ such sums, we see that $$a_1+b_1+c_1=1\qquad\text{ and }\qquad a_3+b_3+c_3=27.$$ Moreover, summing all $27$ sums we get $\sum_{m=1}^{27}m=378$, where $$\sum_{m=1}^{27}m=\sum_{i,j,k=1}^3a_i+b_j+c_k=\sum_{i,j,k=1}^3(a_i+b_i+c_i)=9\sum_{i=1}^3(a_i+b_i+c_i),$$ where of course $\sum_{n=1}^{27}n=378$ and so we see that $$\sum_{i=1}^3(a_i+b_i+c_i)=42,\qquad\text{ and }\qquad a_2+b_2+c_2=14.$$ Next we see that either $$a_1+b_1+c_2=2\qquad\text{ or }\qquad a_1+b_2+c_1=2\qquad\text{ or }\qquad a_2+b_1+c_1=2.\tag{1}$$ meaning that either $c_2=c_1+1$ or $b_2=b_1+1$ or $a_2=a_1+1$. Without loss of generality we have the first identity, and so $c_2=c_1+1$. Because the values of the sums of the form $a_i+b_j+c_k$ are pairwise distinct it also follows that $a_2\neq a_1+1$ and $b_2\neq b_1+1$. That means $$a_1+b_2+c_2\neq3\qquad\text{ and }\qquad a_2+b_1+c_2\neq3,\qquad\text{ so }\qquad a_1+b_1+c_3=3.$$ This implies $c_3=c_1+2$ and so $(c_1,c_2,c_3)=(c_1,c_1+1,c_1+2)$. This already shows that \begin{eqnarray*} a_1+b_1+c_1&=&1,\qquad a_2+b_2+c_1&=&13,\qquad a_3+b_3+c_1&=&25,\\ a_1+b_1+c_2&=&2,\qquad a_2+b_2+c_2&=&14,\qquad a_3+b_3+c_2&=&26,\\ a_1+b_1+c_3&=&3,\qquad a_2+b_2+c_3&=&15,\qquad a_3+b_3+c_3&=&27. \end{eqnarray*} In turn it follows that either $$a_2+b_1+c_1=4\qquad\text{ or }\qquad a_1+b_2+c_1=4,\tag{2}$$ meaning that either $a_2=a_1+3$ or $b_2=b_1+3$. Without loss of generality $b_2=b_1+3$, from which it follows that $a_2=a_1+9$ because we already saw that $$a_2+b_2+c_1=13.$$ This yields the further values \begin{eqnarray*} a_1+b_2+c_1&=&4,\\ a_1+b_2+c_2&=&5,\\ a_1+b_2+c_3&=&6,\\ \end{eqnarray*} Because $a_2=a_1+9$, for all $j$ and $k$ we have $$a_2+b_j+c_k\geq a_2+b_1+c_1=(a_1+9)+b_1+c_1=10.$$ The only sums that can now sum to $7$, $8$ and $9$ are the sums $a_1+b_3+c_i$, which shows that $b_3=b_2+3=b_1+6$. We see that $$27=a_3+b_3+c_3=27=a_3+(b_1+6)+(c_1+2)=(a_3-a_1)+(a_1+b_1+c_1)+8,$$ which shows that $a_3=a_1+18$, and so we have \begin{eqnarray*} (a_1,a_2,a_3)&=&(a_1,a_1+9,a_1+18),\\ (b_1,b_2,b_3)&=&(b_1,b_1+3,b_1+6),\\ (c_1,c_2,c_3)&=&(c_1,c_1+1,c_1+2). \end{eqnarray*} From here we can determine the minimum possible value of the greatest of these integers. The greatest integer is either $a_3$, $b_3$ or $c_3$, and because all nine integers are distinct and $$a_3+b_3+c_3=27=8+9+10,$$ we see that at least one of them is at least $10$. Moreover, if $\{a_3,b_3,c_3\}=\{8,9,10\}$ then $c_3=8$ because $c_1$, $c_2$ and $c_3$ are consecutive. Then $c_1=6$ and $c_2=7$. But either $b_3=9$ or $b_3=10$, and correspondingly $b_2=6$ or $b_2=7$, a contradiction.

The next smallest options have either $$\{a_3,b_3,c_3\}=\{6,10,11\}\qquad\text{ or }\qquad\{a_3,b_3,c_3\}=\{7,9,11\}.$$ The latter option is clearly impossible by the same argument as before. A quick check shows that $(a_3,b_3,c_3)=(11,6,10)$ does indeed yield a solution in nine distinct integers, corresponding to the following three groups: $$\{-7,2,11\},\qquad\{0,3,6\},\qquad\{8,9,10\}.$$

Answer 3

We can see that there are, in total, $27$ different combinations of numbers. Therefore, each combination should create a sum of every number from $1$ to $27$, and each combination should create a unique number.

Now, designate each of the three numbers in the three different groups as $x_1<x_2<x_3$,$y_1<y_2<y_3$, $z_1<z_2<z_3$. We can see that the combinations with sums of $1$ and $2$ must share two common numbers, WLOG $x_1$ and $y_1$. Therefore, $z_2-z_1=1$. Now, notice that the combinations with sums $26$ and $27$ also share two common numbers, for example $y_3$ and $z_3$. Therefore, $x_3-x_2=1$.

Now, if we take the combinations $x_2,y_2,z_1$ and $x_3,y_2,z_2$, we find that they are equal in sum, which cannot happen! Therefore, we must have that, $z_3,z_2,z_1$ are all consecutive numbers, from $z_3-z_2=z_2-z_1=1$.

Now, we know that the sum of $3$ is produced by $x_1,y_1,z_3$. Now, consider the sum for $4$. The number chosen in the $z$ group must be $z_1$, as otherwise if we replace $z_1$ with $z_3$, then we have two numbers in another group having a difference of one, which leads to a contradiction, and if we replace $z_1$ with $z_2$, then we produce a sum of $3$ that uses $z_1$, meaning $z_1=z_3$ which is impossible. Therefore, we have that $x_2-x_1=3$ or $y_2-y_1=3$, which we will WLOG the first case.

Similarly with the sum of 24, we must have $z_3$ in the sum, as otherwise this leads to different combinations summing to the same number. Therefore, we have another group with two numbers having a difference of 3. If we have that $y_3-y_2=3$, then upon taking $x_1,y_3,z_2$ and $x_2,y_2,z_2$, we having different combinations summing to the same number.

Therefore, we can WLOG group $y_3-y_2=y_2-y_1=3$. If we add the sums of each combination, then we yield $\frac{27\times 28}{2}$, and so we get $378$. However, the sums count each number $9$ times, so we have to divide by $9$ to get that $$\sum_{i=1}^9a_i=42$$ Therefore, we yield $$x_1+y_1+z_1=1,x_3+y_1+6+z_1+2=27,x_2+y_1+3+z_1+1=42-27-1=14$$

We then have that $x_3-x_2=x_2-x_1=9$. Therefore, we now have all the equations required, and any triple of integers such that $a_1+a_2+a_3=1$ must follow those equations. However, to minimize the largest number, we want to minimize $a_7+a_8+a_9$=27, and we can see that smallest $a_9$ can be is $10$, or otherwise $9+8+7<27$.

However, note that no two numbers can be the same, so $a_9-a_8$ and $a_8-a_7$ cannot coincide with any of the other distances (but they can coincide with each other). Therefore, $a_9=10$ is impossible.

With 11, we have the example, listed in $x_1,x_2,x_3,y_1,y_2,y_3,z_1,z_2,z_3$ order:$$-7,2,11\hspace{1cm}0,3,6\hspace{1cm}8,9,10$$ Anyways, the answer is $\boxed{11}$.