Team selection tests for JBMO 2018

We will show that if $|S|\ge 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,\dots ,s_k\}$ for some $k\ge 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,\dots ,n-1\}$. The number of elements changes from $1$ to $n-1$.

However, since we added $k\ge 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$