# Distinct sums from nine $9$ integers

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

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)

• Is there any reason you're only looking at consecutive numbers? Two hints: since the largest three numbers sum to $27$, $a_9$ is at least $10$ (can you see why?) Secondly, you're told the numbers are in three sets, which limits the combinations you can get; maybe there's a better notation? Commented Jul 14, 2023 at 11:10
• (to be clear, there's an easy way to show $a_9$ has to be at least $10$, but that doesn't mean a solution exists with $a_9=10$ - that'll take more work) Commented Jul 14, 2023 at 11:13
• Do you know for certain that a solution exists? I'm not convinced that this can hold for any set of nine distinct integers. Commented Jul 14, 2023 at 12:24
• @legionwhale Infinitely many solutions exists, but none with $a_9=10$. Commented Jul 14, 2023 at 12:37
• There's quite a sneaky shortcut here that doesn't involve casework or simultaneous equations. I've posted one way as an answer but I'd be interested to know if there were any other short methods. Commented Jul 14, 2023 at 13:19

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 etc and $$a_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).

• +1 Very nice solution! As for the uniqueness of this factorization; it suffices to show that the factor $q(x):=1+x^9+x^{18}$ is irreducible, and this follows from the fact that $q(x+1)$ is Eisenstein at $3$. Commented Jul 14, 2023 at 14:49
• Omg, that was an amazing solution!! Thanks alot ! , now that I know this approach, can you help me out by explaining what were the trigger points in the question that made you follow this approach, was it that we wanted all possible sums from all possible elements combined with other sets ? This insight would surely help me in the problem solving for future :) Thanks alot again Commented Jul 14, 2023 at 20:37

We have nine distinct integers in three groups of three integers, say $$a_1 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\}.$$

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,$$y_1, $$z_1. 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}$$.

• That conclusion isn't right - one set could have three negative numbers, or two sets could each have two negative numbers in them. Commented Jul 14, 2023 at 11:07
• I have fixed it now, the answer seems to be correct now. Commented Jul 14, 2023 at 11:17
• Ermm...I might also question the line $\frac{27 \times 28}{2} = 108$ !!! Commented Jul 14, 2023 at 11:21
• Should work now (x2) Commented Jul 14, 2023 at 12:44