Possible outcomes of sums

Question

Let $\mathrm{S}$ be a set of distinct 20 integers. A set $\mathrm{T}_{\mathrm{A}}$ is defined as $\mathrm{T}_{\mathrm{A}}:=\left\{\mathrm{s}_1+\mathrm{s}_2+\mathrm{s}_3 \mid \mathrm{s}_1, \mathrm{~s}_2, \mathrm{~s}_3 \in \mathrm{S}\right\}$. What is the smallest possible cardinality of $\mathrm{T}_{\mathrm{A}}$?

My progress so far: We're looking for the smallest possible cardinality of $T_A$, which is the set of sums of three distinct numbers from $S$, and $S$ is a set of 20 distinct integers.

To minimize the cardinality of $T_A$, we would aim to have as many sums repeating as possible. In other words, we want the sums to overlap as much as possible.

Consider the set of 20 integers to be $S = {1, 2, 3, ..., 20}$ for simplicity.

If we choose the smallest three numbers, the sum would be $1 + 2 + 3 = 6$. If we choose the largest three numbers, the sum would be $18 + 19 + 20 = 57$. Thus, the range of possible sums lies between 6 and 57.

However, not all values within this range can be achieved due to the restriction of using distinct integers for each sum. For instance, the value 7 cannot be achieved because there's no way to add three distinct positive integers from $S$ to get 7. Similarly, there will be several values within the range that cannot be achieved due to this restriction.

The problem is equivalent to finding the number of distinct elements in a multiset where we sum triplets from the multiset ${1, 2, ..., 20}$.

Answer 1

The smallest possible cardinality is $52$, which is achieved by $S=\{\,1,2,\dotsc,20\,\}$ (or by any $20$-term arithmetic progression.

Let the elements of $S$ be $a_1<a_2<\dotsb<a_{20}$. Then all the sums $a_1+a_2+a_r$, $3\le r\le20$, are distinct – that's $18$ sums.

All the sums $a_1+a_s+a_{20}$, $3\le s\le19$, are distinct from each other and from the first $18$ sums. That's another $17$ sums.

All the sums $a_t+a_{19}+a_{20}$, $2\le t\le18$, are distinct from each other, and from the previous sums. That's another $17$ sums.

Total: $18+17+17=52$.

The argument works for a set of $k$ distinct numbers, and gives a minimum of $3k-8$ sums.

Answer 2

I'll find it for an arbitrary set $S$ with $n$ distinct integer.

Let $S=\left\{s_1, s_2, s_3, \cdots, s_n\right\}$ with $s_i<s_{i+1}$ for $i=1,2, \cdots, n-1$. $T_A$ contains at least $n$ distinct integers $3 s_1<3 s_2<\cdots<3 s_n$ since $3 s_i=s_i+s_i+s_i$ for all $i=1,2, \cdots, n$. Furthermore, $T_A$ contains at least $2(n-1)$ elements more since for every $i=1,2, \cdots, n-1$, there are two distinct elements $s_i+s_i+s_{i+1}$ and $s_i+s_{i+1}+s_{i+1}$ in $T_A$ between $3 s_i$ and $3 s_{i+1}$. Thus $T_A$ contains at least $3 n-2$ elements.

Let $S=\{0,1, \cdots, n-1\}$. Then clearly $T_A=\{0,1, \cdots, 3 n-3\}$ and $\left|T_A\right|=$ $3 n-2$. Thus minimal cardinality of $T_A$ is $3 n-2$. For the $n=20$ case, it is 58.

This is the solution I came up with, but I don't know whether I did something wrong or the above solution has some fallacy in solving. Can anyone verify these particular cases?