, 2018

We will show that if $|S| \geq n$, we can remove one element from $S$ and still have a comprehensive set. Doing this repeatedly will always allow us to find a comprehensive subset of size at most $n-1$.

Denote $S = \{s_1, s_2, \ldots, s_k\}$ for some $k \geq n$. Now start with the empty set and add in the elements $s_i$ in order. During this process, we will keep track of all possible remainders of sums of any subset.

If $T$ is the set of current remainders at any time, and we add an element $s_i$, the set of remainders will be $T$ and $\{t + s_i \mid t \in T\}$. In particular, the set of remainders only depends on the previous set of remainders and the element we add in.

At the beginning of our process, the set of possible remainders is $\{0\}$ for the empty set. Since we assumed that $S$ is comprehensive, the final set is $\{0, 1, \ldots, n-1\}$. The number of elements changes from $1$ to $n-1$.

However, since we added $k \geq n$ elements, at least one element did not change the size of our remainder set. This implies that adding this element did not contribute to making any new remainders and $S$ is still comprehensive without this element, proving our claim. $\square$