Not so equal subsets

Note that S = {20, 31, 37, 40, 42, 43, 44} works. To see this, we first note that if there exists two subsets of S whose sums of elements are equal, then we can remove the overlapping elements from each subset and still obtain two subsets of S with the same sum. So S does not fulfil the criteria in the question if and only if there exists two disjoint subsets of S with the same sum. Let the size of two disjoint subsets of S be a and b, where $a \geq b$ . Consider all possible (a,b). Note that since the sum of all elements in S is odd but the total sum of the two equal subsets is even, then a + b cannot be 7. The individual cases are analysed below:

(1,1): Clearly, there is no such pair of subsets.

(2,1): The minimum sum of two-element subsets is 51, which exceed 44. So there is no such pair of subsets.

(2,2): Clearly, the two subsets will have to be {c,d} and {e,f} where c < e < f < d. A simple exhaustive search shows that no such pair of subsets exists.

(3,1): The minimum sum of three-element subsets is 88, which exceed 44. So there is no such pair of subsets.

(3,2): The minimum sum of three-element subsets is 88, which exceed 44+43=87. So there is no such pair of subsets.

(3,3): The sum of the elements in S is 257. So the element that is left out of these two disjoint sets must be odd. A simple exhaustive search (where we leave out each of the 3 odd terms in turn) shows that no such pair of subsets exists.

(4,1): The minimum sum of four-element subsets is 128, which exceed 44. So there is no such pair of subsets.

(4,2): The minimum sum of four-element subsets is 128, which exceed 44+43=87. So there is no such pair of subsets.

(5,1): The minimum sum of five-element subsets is 170, which exceed 44. So there is no such pair of subsets.

Thus, this set with n = 7 has the property that all its subsets have distinct sums.

We now try to show that $n \leq 7$ . The maximum possible sum of any subset is 1 + 2 + ... + 45 = 45(23) = 1035. So there are altogether at most 1035 possible distinct subset sums. For any set with at least 11 terms, the number of non-empty subsets is at least $2^{11} - 1 = 2047 > 1035$ , so by the pigeonhole principle, there must exist at least a pair of subsets with the same sum. Thus $n \leq 10$ . When n = 10, the maximum subset sum is 36 + 37 + ... + 45 = 405. But there are $2^{10} - 1 = 1023$ non-empty subsets, so there must exist at least a pair of subsets with the same sum. When n = 9, the maximum subset sum is 37 + 38 + ... + 45 = 369. But there are $2^9 - 1 = 511$ non-empty subsets, so there must exist at least a pair of subsets with the same sum. When n = 8, the number of subsets with 1, 2, 3, 4 or 5 terms is ${8 \choose 1} + {8 \choose 2} + {8 \choose 3} + {8 \choose 4} + {8 \choose 5} = 218$ . But the maximum subset sum for these subsets is 41 + 42 + 43 + 44 + 45 = 215. So there must exist at least a pair of subsets (among the 218) with the same sum.

Therefore, we have $n \leq 7$ . Since we have already shown that there exists a set with n = 7 with distinct subset sums, then the largest possible value of n is 7.

{The largest possible value of $n$ is $7$ . Our proof consists of two parts: (i) $n\geq 8$ is impossible; (ii) $n=7$ is possible.

(i) Consider the following $2^n$ numbers: $x=\epsilon_1x_1+\epsilon_2x_2+\cdots+\epsilon_n x_n,$ where $\epsilon_i=-1$ or $1$ . Suppose $s$ is the sum of $x^2$ over all possible $x$ 's. Then, on one hand,

$s = 2^n(x_1^2+\cdots+x_n^2) + \alpha,$

where $\alpha$ is the sum of "cross terms": $\sum_{i\neq j} ( (+x_i)(+x_j)+(+x_i)(-x_j)+(-x_i)(+x_j)+(-x_i)(-x_j))$ which is equal to $0$ . Therefore $s = 2^n(x_1^2+\cdots+x_n^2)$ . On the other hand, it is evident that all numbers in the form of $x$ have the same parity and not equal to $0$ , so $s$ is at least $1^2 + (-1)^2 + 3^2 + (-3)^2 + \cdots +(2^n-1)^2 + (-2^n+1)^2$ $= 2(1^2 + 3^2 +\cdots +(2^n-1)^2)= 2(1+2+\cdots+(2^n-1))^2$ $= \frac{2}{3}(2^{n-1})(2^n-1)(2^n+1)$ $=\frac{2^{n}}{3}(4^n-1).$

(Note that we used the formula $1^2 + 3^2 + 5^2 + ... + (2N - 1)^2 = \frac{N(2N - 1)(2N + 1)}{3}$ , which can be proved by induction easily.)

So $n\cdot x_n^2 \geq x_1^2+\cdots+x_n^2 \geq (4^n-1)/3$ . Thus $x_n \geq \sqrt{\frac{4^n-1}{3n}}.$

However, if $n\geq 8$ , $x_8 \geq \sqrt{(4^8-1)/24}>52$ , which contradicts with $x_8\leq 45$ .

(ii) For $n=7$ , consider the set $B=\{20,31,37,40,42,43,44\}$ . Suppose it does not satisfy the property stated in the problem. Then there are two different subsets whose sums are equal:

$\alpha_1 +\cdots+ \alpha_p = \beta_1 +\cdots+ \beta_q,$

where $\alpha_i, \beta_j\in B$ . Also, one can eliminate the same terms from both sides (if any), and thus it can be assumed that $p+q\leq 7$ . Observe that $\sum B = 20+31+\cdots+44 = 257$ , which is an odd number, so it is not possible to have all $7$ numbers in the equation, i.e. $p+q\leq 6$ . Furthermore, at least one odd number is not in the $p+q$ numbers selected, and $31$ is the smallest odd number in the set $B$ , therefore the value of both sides of the equation is no greater than $(257-31)/2=113$ . However, $20+31+37+40=128>113$ , so we have $p, q\leq 3$ .

Given that the smallest 3-element sum, $20+31+37=88$ , is greater than the largest 2-element sum, $43+44=87$ , and the smallest 2-element sum, $20+31=51$ , is greater than the largest element $44$ , we can conclude that $p\neq q$ is not possible. So we assume $p=q$ . Subtracting each element from $44$ , we see that the equation

$y_1+\cdots+y_p = z_1+\cdots+z_p$

holds for $p=2$ or $3$ , and $y_i, z_j$ are distinct elements in the set $\{0,1,2,4,7,13,24\}$ . We then argue as follows:

1. Note that $4+7+13=24$ . If $24$ appears in this equation, say the left hand side, then the right hand side is at least $24$ and hence must contain $4,7,13$ . But then $p=3$ , and the left hand side will be at least $24+0+1=25$ , a contradiction. So $24$ does not appear in the equation.

2. Similarly, if $13$ appears in one side of the equation, the other side should contain $2,4,7$ since $2+4+7=13$ , so $p=3$ and the left hand side is more than $13$ , again a contradiction.

3. Same case for $7$ because $7=1+2+4$ .

4. Therefore $7,13,24$ do not appear in both sides of the equation. Now $4>1+2+0$ , $2>1+0$ , $1>0$ suggest that actually $4,2,1$ are also not in the equation. We deduce that there are no more than one element which appear in the equation, an absurdity. (Q.E.D.)

Direct experimentation shows that such a set does exist for $n=7$ , for example: $\{45,44,43,41,38,32,20\}$ . (In finding this solution, I found it helpful first to keep in mind that if two subsets have the same sum, then WLOG they are disjoint; and second to think in terms of the set $T=\{y_1,...y_7\}$ , where $y_j=45-x_j$ . The given solution corresponds to $T=\{0,1,2,4,7,13,25\}$ . It is easy to show that no two subsets of $T$ have both the same sum and the same number of elements. This leaves the case where a subset of $T$ has sum $\ge45$ , but that case is also easily dealt with.)

To complete the proof, we need to show that the sums cannot all be distinct if $n=8$ . (Clearly if it isn't possible for $n=8$ , then it isn't possible for $n>8$ either.)

For $n=8$ , the number of subsets (including the empty set) is $2^8=256$ , and the largest possible sum is $38+...+45=332$ .

However, most of the sums will be substantially less that $332$ . In fact, the number of subsets with five or fewer elements is $2^8 -{8 \choose 8} -{8 \choose 7} -{8 \choose 6} =256-1-8-28=219$ , and the sum of each of those subsets is a nonnegative integer less than or equal to $41+42+43+44+45=215$ , so the sums cannot all be distinct.

We will show that the answer is $n=7$ . To do this, we must show that these two statements are true:

1. There does not exist a set $\{x_1,x_2,\ldots,x_8\}$ satisfying the conditions of the problem; and
2. There exists a set $\{x_1,x_2,\ldots,x_7\}$ satisfying the conditions of the problem.

~~~~

Part 1 : Assume for the sake of contradiction that there exists a set $\{x_1,x_2,\ldots,x_8\}$ satisfying the conditions of the problem.

Let us consider the set of numbers $S=\{e_1x_1+e_2x_2+\cdots+e_8x_8\mid e_1,\ldots e_8\in\{+1,-1\}\},$ or, in other words, the numbers which can be written in the form $\pm x_1\pm x_2\pm\cdots\pm x_8$ with a suitable choice of signs.

First, note that every element of $S$ has the same parity, i.e. either every element is even or every element is odd, because all elements are congruent to $x_1+x_2+\cdots+x_8\pmod2$ .

Secondly, note that no two elements of $S$ are equal. For example, if $x_1-x_2+x_3-x_4-x_5-x_6+x_7-x_8\\ =-x_1+x_2-x_3-x_4+x_5+x_6+x_7-x_8$ then by moving all terms to one side of the equation we get $2(x_1-x_2+x_3-x_5-x_6)=0,$ or in other words $x_1+x_3=x_2+x_5+x_6$ , contradicting the fact that no two subsets of $\{x_1,\ldots,x_8\}$ have the same sum of elements.

Hence $S$ contains $2^8$ distinct numbers of the same parity.

We will now evaluate the sum $\sigma=\sum_{a\in S} a^2$ in two different ways.

---

Step 1 : Clearly $(e_1x_1+e_2x_2+\cdots+e_8x_8)^2$ , when expanded, only contains terms of the form $x_i^2$ and $x_ix_j$ . So to determine $\sigma$ , we only have to determine the coefficients of $x_i^2$ and $x_ix_j$ in that sum.

1. Note that the coefficient of $x_i^2$ in $(e_1x_1+e_2x_2+\cdots+e_8x_8)^2$ is $e_i^2=1$ . Thus the coefficient of $x_i^2$ in $\sigma$ is just the number of terms in the sum, which is $2^8$ .
2. Split the $2^8$ terms of the sum in $\sigma$ into groups of four like this: $(x_i+x_j+A)^2+(x_i-x_j+A)^2\\+(-x_i+x_j+A)^2+(-x_i-x_j+A)^2$ It is easy to check that the coefficient of $x_ix_j$ in every such group is 0. Hence the coefficient of $x_ix_j$ in $\sigma$ is also 0.

Therefore $\boxed{\sigma=2^8(x_1^2+x_2^2+\cdots+x_8^2)<2^8\cdot8\cdot45^2}$ .

---

Step 2 : Now that we have an upper bound for $\sigma$ , let us find a lower bound. In fact, we shall find the minimum value of $s=\sum_{i=1}^{2^8} y_i^2$ , where $y_1>y_2>\cdots>y_{2^8}$ and all the $y_i$ are integers with the same parity. (The minimum value of $s$ exists because $s$ is always a nonnegative integer.)

If all the $y_i$ are even and there does not exist $k$ such that $y_k=0$ then replacing $y_1$ by 0 will decrease $s$ . Similarly, if all the $y_i$ are odd and there does not exist $k$ such that $y_k=1$ then replacing $y_1$ by 1 will decrease $s$ . Hence we may assume that there exists $k$ such that $y_k\in\{0,1\}$ .

If there exists $i\in\{2,3,\ldots,k\}$ such that $y_{i-1}>y_i+2$ then replacing $y_{i-1}$ by $y_{i-1}-2$ will decrease $s$ , since $y_{i-1}\geq2$ . Similarly, if there exists $i\in\{k,\ldots,2^8-1\}$ such that $y_i>y_{i+1}+2$ then replacing $y_{i+1}$ by $y_{i+1}+2$ will decrease $s$ , since $y_{i+1}\leq-2$ . Hence we may assume that $y_i-y_{i+1}=2$ for all $i=1,2,\ldots,2^8-1$ .

Also, if $y_1>-y_{2^8}+2$ then replacing $y_1$ by $y_{2^8}-2$ decreases $s$ . Similarly if $y_1<-y_{2^8}-2$ then replacing $y_{2^8}$ by $y_1+2$ decreases $s$ . Hence we may assume $|y_1-y_{2^8}|\leq1$ .

Combining all of the above, we see that the minimum value of $s$ is achieved when $\{y_1,\ldots,y_{2^8}\}$ is one of the following:

• $\{256,254,\ldots,-252,-254\}$
• $\{254,252,\ldots,-254,-256\}$
• $\{255,253,\ldots,-253,-255\}$

In the first two cases, $\begin{aligned} s&=2\cdot2^2\cdot(1^2+2^2+\cdots+127^2)+256^2\\ &=8\cdot\frac{127\cdot128\cdot255}{6}+256^2\\ &=\frac{254\cdot255\cdot256}{3}+256^2\\ &=\frac{257\cdot255\cdot256}{3}+256^2-255\cdot256\\ &=\frac{255\cdot256\cdot257}{3}+256 \end{aligned}$

In the last case, $\begin{aligned} s&=2(1^2+3^2+\cdots+255^2)\\ &=2((1^2+2^2+3^2+\cdots+255^2)-2^2(1^2+2^2+\cdots+127^2))\\ &=2(\frac{255\cdot256\cdot511}{6}-4\frac{127\cdot128\cdot255}{6})\\ &=\frac{255\cdot256\cdot257}{3} \end{aligned}$

Hence the minimum value of $s$ is $\frac{255\cdot256\cdot257}{3}$ , and thus $\boxed{\sigma\geq\frac{255\cdot256\cdot257}{3}}$ .

---

Putting everything together we have $2^8\cdot8\cdot45^2>\sigma\geq\frac{255\cdot256\cdot257}{3}$ , which implies $8\cdot45^2=16200>21845=\frac{255\cdot257}{3}$ , contradiction.

Note: using the above method we can prove the following: for any set of positive integers $\{x_1,\ldots,x_n\}$ such that no two distinct subsets have equal sum of elements, we have $x_1^2+x_2^2+\cdots+x_n^2\geq1^2+2^2+4^2+\cdots+(2^{n-1})^2.$

~~~~

Part 2 : We now show that there exists a set $\{x_1,x_2,\ldots,x_7\}$ satisfying the conditions of the problem. To do this, let us look at the set $X=\{20,31,37,40,42,43,44\}$ . From this point on let $\varsigma(S)$ denote the sum of elements of a set $S$ .

Assume there exist two distinct subsets of $X$ , call them $A$ and $B$ , such that $\varsigma(A)=\varsigma(B)$ . By removing elements that are in both $A$ and $B$ , we can assume that $A$ and $B$ are disjoint, which implies $|A|+|B|\leq7$ . We may also assume that $|A|\leq|B|$ , which implies $|A|\leq3$ .

---

Case 1 : $|A|=3$ .

If $|B|=4$ then $A$ and $B$ together contain each element of $X$ exactly once. But $257=\varsigma(X)=\varsigma(A)+\varsigma(B)=2\varsigma(A)$ , contradiction.

If $|B|\leq2$ then $\varsigma(B)\leq43+44=87$ , but $\varsigma(A)\geq20+31+37=88$ , contradiction.

If $|B|=3$ then there is exactly one element of $X$ which is not in either $A$ or $B$ . Note that this element must be equal to $\varsigma(X)-\varsigma(A)-\varsigma(B)=257-2\varsigma(A)$ , so it is either 31, 37 or 43. It is easy to check in each of these three cases that no solutions to $A,B$ can be found.

---

Case 2 : $|A|=2$ .

If $|B|\geq3$ then again we have $\varsigma(A)\leq87<88\leq\varsigma(B)$ , contradiction.

If $|B|=1$ then $\varsigma(A)\geq20+31>44\geq\varsigma(B)$ , contradiction.

Hence $|B|=2$ . Write $A=\{a_1,a_2\}$ , $B=\{b_1,b_2\}$ . Then $a_1+a_2=b_1+b_2$ , or $a_1-b_1=b_2-a_2$ . But it is easily checked that no two pairwise differences of elements of $X$ are equal, so $a_1=b_1$ , $a_2=b_2$ and thus $A=B$ , contradiction.

---

Case 3 : $|A|=1$ .

If $|B|\geq2$ then again we have $\varsigma(A)\leq44<51\leq\varsigma(B)$ , contradiction.

If $|B|=1$ then clearly $A=B$ , contradiction.

---

Hence $X$ does not contain two distinct subsets with the same sum of elements.

Therefore the maximum value of $n$ in the question is $n=7$ .

The solution for the above question can be given by Erdo's conjecture and later can be verified by Conway-Guy's sequence of sets which has distinct subset sums.

Before calculating the solution lets define a set which has distinct subset sums-

A set $S$ of positive integers has distinct subset sums if the set $\{\sum_{x \epsilon X} x : X \subset S\}$ has $2^{|S|}$ distinct elements i.e all the subsets of S including null set. Let $f(n)$ be a function denoting the maximum value or the highest positive integer in $S$ for, $|s|=n$ .
Now Erdo’s conjecture. He states that $f(n)\geq c2^n$ , where $n$ is the number of integers in set $S$ and c is a constant and presently the value of $c=.22002$ .

Coming to the question. Taking the given set $1 to 45$ . The maximum value is $45$ . Thus assuming that $45$ the maximum value of Set $S$ with $n$ elements,

.i.e $f(n)=45\geq 0.22002(2^n)$ $\Rightarrow \log_2 [45/0.22002] \geq n$ Thus, $n\leq 7.676$ . Since $n \epsilon N, n \leq 7$ . And they have asked the largest possible value of $n$ .

$\therefore \boxed {n=7}$

Now coming to the verification part using Conway-Guy's sequence. Its is a sequence of sets which has distinct subset sums. And the sequence goes in such a way that the number elements in preceding and succeeding sets of the sequence differ by $1$ . And in general the Sequence is given by

$S_{i}= \{ \displaystyle \sum_{j=k}^i d(j): k=1,2,3,…,i \}$

$\{ d(j) \} : 1, 1, 2, 3 ,6, 11, 20, 40, 77, 148, 285,….,$

So, the Conway-guy’s sequence goes like this, $S_{1}=\{ 1\}$ , $S_{2}=\{ 2,1\}$ , $S_{3}=\{ 4,3,2\}$ , $S_{4}=\{ 7,6,5,3\}$ , $S_{5}=\{ 13,12,11,9,6\}$ , $S_{6}=\{ 24,23,22,20,17,11\}$ , $S_{7}=\{ 44,43,42,40,37,31,20\}$ , $S_{8}=\{ 84,83,82,80,77,71,60,40\} \ldots$

Here we can see that the $7^{th}$ set of the sequence has $f(7)=44$ but we had assumed it as 45. And in the $8^{th}$ set $f(8=84)$ which is not included in the set $1 to 45$ given in the question. Hence, the largest set having distinct sums of subset and having element between $1 to 45$ is $S_{7}$ with 7 elements. Hence, verified.

$\boxed {n=7}$

The answer is $7.$

First, we note that the following numbers satisfy the condition of the problem: $45,44,43,41,38,32,21$ To check this, it is easier to look at $45-x_i:$ $0,1,2,4,7,13,24$ First, one can check that if two subsets (which can be considered disjoint) have equal sums, they must have the same number of elements. Then one can check that the subset with the biggest $45-x_i$ will have strictly smaller sum than any other subset with the same number of elements.

Now suppose that $n\geq 8$ . We may as well assume that $n=8$ and order the numbers: $x_1<...<x_8.$ Consider the sums of $x_i$ that contain at least three terms. Their number is $2^8-(1+8+\frac{8\cdot 7}{2})=219$ . The difference between the biggest and the smallest such sum is no bigger than $x_4+x_5+x_6+x_7+x_8,$ which is no bigger than $41+42+43+44+45=215.$ Because $216<219,$ by the Dirichlet Box Principle two of these sums must be the same.

If $n= 9$ then there are $2^9=512$ subsets and thus $512$ subset sums. The possible sums range from $1$ to $37+38+\cdots +45=369.$ By the Pigeonhole principle, two of the subset sums must be the same, which is a contradiction. We can clearly extend this result to all $n\geq 9$ , so we conclude that $n\leq 8.$

For $n=8$ we utilize the following program to produce the set of $8$ positive integers that satisfies the given conditions.

====

void guess(int k, int xk)

{

x[k] = xk;

FOR(i = -MAX .. MAX)

free[k][i] = free[k+1][i-xk] && free[k+1][i] && free[k+1][i+xk];

free[k][pk] = free[k][-pk] = false;

FOR(i = pk-1 .. 1) if(free[k][i]) guess(k-1,i);

}

====

The program produces the sets, {39,59,70,77,78,79,81,84} {20,40,71,77,80,82,83,84} {40,60,71,77,80,82,83,84}

Since no element of the set can exceed $45$ we conclude that $n\neq 8.$

Finally, we provide a construction for $n=7:$ {20,31,37,40,42,43,44}. Therefore, $7$ is our answer.

if n=7 there is a solution (25,33,38,41,43,44,45) if n=8 we will prove that it cannot be Let there is a set ${x_{1},x_{2},....,x_{8}}$ we can see there are $2^8-1$ distict sum let ${x_{1}+x_{2}+....+x_{8}} = a$ so $a \leq 285$

proof: let ${x_{1} \geq x_{2} \geq....\geq x_{8}}$ because we will find the maximum value of a, so we maximize $x_{1}=45$ and $x_{2}=44$ , then $x_{3}=43$ (there is still no same sum) if $x_{4}=42$ there is a same sum ( $x_{1}+x_{4} = x_{2}+x_{3}$ ) so $x_{4} = 41$ with the same way for $x_{5},x_{6},x_{7},x_{8}$ we can find the set (45,44,43,41,38,33,25,16) is maybe the solution for n=8 which have greatest value of a

we can see that from $2^8-1$ distict sum there are 127 pairs where the sum is a example: ( $x_{1} and x_{2}+x_{3}+...+x_{8}$ so we can differ $2^8-1$ distict sum into 2 groups ( the group of 127 smallest sum where $\leq \frac {a}{2}$ , and 128 greatest sum(including a))

because $a \leq 285$ so $\frac {a}{2} \leq 142$

note again that there are 8 sum smaller than 45 ( ${x_{1},x_{2},....,x_{8}}$ ) minimally so there are $142-45=97$ number for $127-8=119$ sums which is impossible using pigeon hole principle so there is no solution for n=8

SO, the greatest value of n=7

Let a pair of number be denoted by {a,b}, with a $\geq$ b . Note that if any two distinct pair of numbers have the same difference, then we can take $a_1$ + $b_2$ as set 1, and $a_2$ + $b_1$ as set 2, and they will have the same sum. </p>

Also, if two sets share a common element d , we can remove d from both sets and whether the sets have a distinct sum is not affected. </p>

Thus, by eliminating all possible answers after starting from having 1 in our set, we get the set is {1,2,4,8,13,21,31,45} . Hence, n is 7 </p>

When faced with a sum of subset that do not equal to each other, the first thing that came into my mind is the power of 2s. So I tried answering $6$ for the set $\{1,2,4,8,16,32\}$ . Since it is wrong, the answer usually is not far from it, and so I answered $7$ and got it correct.