# Maximum size of a subset S of $\{1,2,…,9\}$ such that sum of each of two members are distinct

What is the maximum size of a subset S of $\{1,2,...,9\}$ such that sum of each of two members of it are distinct?

I considered the following partition: $\{1,9\},\{2,8\},\{3,7\},\{4,6\},\{5\},$ and since these subsets have equal sum I deduced that $S$ has at most 5 members,am I right?

• are you supposed to sum two distinct elements of the subset? If so, the subset $\{5\}$ has sum $5$, not $10$. If you can sum the same element twice, then the problem is very different – infinitylord Dec 15 '17 at 19:04
• Are you only looking at sums of two distinct members of the subset? – Stephen Meskin Dec 15 '17 at 19:05
• Yes, sum of two distinct elements in the subset $S$ is to be unique – Hamid Reza Ebrahimi Dec 15 '17 at 19:06
• $5$ is the max. – Alexander Gruber Dec 15 '17 at 19:12
• Please post your complete reasoning as an answer – Hamid Reza Ebrahimi Dec 15 '17 at 19:12

I do not follow your deduction but 5 is right because there is a subset of size 5 such as: $\{2, 5, 7, 8, 9\}$ and, on the other hand, 6 will not work.

Proof:

1. There are 15 pairs of numbers from a set of size 6.
2. The smallest and largest sum of a pair from $\{1, 2,, 3, 4, 5, 6, 7, 8, 9\}$ are 3 and 17.
3. There are 15 different integers in the range from to 3 to 17 inclusive.
4. So if a set of size 6 works, call it T, T's sums must consist of all 15 integers from 3 to 17.
5. In order to get the sums $3, 4,\text { and } 6$, T must contain $1, 2, 3,\text { and } 4$ or $1, 2, 3,\text { and } 5$. In the first case $1+4=2+3$ so T must contain $1, 2, 3,\text { and } 5$.
6. Similarly in order to get a sum of $9$ we must have $8 \in T$ so $T=\{1, 2, 3, 5, 8\}$.
7. The only numbers left that could be added to T are $4, 6, 7, \text { and } 9$ but each of them would give T non-unique sums. $1+4=2+3;\; 1+6=2+5;\;1+7=3+5;\;1+9=2+8$. So T cannot have 6 elements.

EDIT: Simpler version, same approach.
New step 5. In order to get sums $3 \text { and } 17$, T must contain $1, 2, 8, 9$. But then $1+9=2+8$ so T cannot have 6 elements.
Delete steps 6 and 7.

• Between 3 and 17 we have at most 15 different sums,ok? – Hamid Reza Ebrahimi Dec 15 '17 at 19:17
• @HamidRezaEbrahimi Thanks for the correction. – Stephen Meskin Dec 15 '17 at 20:28
• Can you extend your method to the set: {1,2,...,n}? – Hamid Reza Ebrahimi Dec 16 '17 at 8:48
• I've answered your question. if you are interested in generalizing it, ask another question and let's see you do some work on it. – Stephen Meskin Dec 16 '17 at 16:50