1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – infinitylord Dec 15 '17 at 19:04
  • $\begingroup$ Are you only looking at sums of two distinct members of the subset? $\endgroup$ – Stephen Meskin Dec 15 '17 at 19:05
  • $\begingroup$ Yes, sum of two distinct elements in the subset $S$ is to be unique $\endgroup$ – Hamid Reza Ebrahimi Dec 15 '17 at 19:06
  • $\begingroup$ $5$ is the max. $\endgroup$ – Alexander Gruber Dec 15 '17 at 19:12
  • 1
    $\begingroup$ Please post your complete reasoning as an answer $\endgroup$ – Hamid Reza Ebrahimi Dec 15 '17 at 19:12
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Between 3 and 17 we have at most 15 different sums,ok? $\endgroup$ – Hamid Reza Ebrahimi Dec 15 '17 at 19:17
  • 1
    $\begingroup$ @HamidRezaEbrahimi Thanks for the correction. $\endgroup$ – Stephen Meskin Dec 15 '17 at 20:28
  • $\begingroup$ Can you extend your method to the set: {1,2,...,n}? $\endgroup$ – Hamid Reza Ebrahimi Dec 16 '17 at 8:48
  • $\begingroup$ 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. $\endgroup$ – Stephen Meskin Dec 16 '17 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.