1

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?

Asaf Karagila
  • 393,674
Hamid Reza Ebrahimi
  • 3,445
  • 13
  • 41

1 Answers1

2

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.

Stephen Meskin
  • 1,829
  • 8
  • 17