Find the smallest value of $n$ such that for any set of $n$ positive integers, there exists a non-empty subset of the set whose sum is divisible by $1001$
This is sort of a follow up on my last post which turned out to be a duplicate. My first intuition was that it's $1001$, but then when I tried to think about using similar methods as the solution to the previous problem, I found out that it couldn't be applied in this case as it isn't sufficient. Therefore, I think an alternate approach is required but I can't figure out any ways to approach this question systematically.
If this post turns out to be a duplicate of another one, please tell me and I'll refer to that one instead. Thank you!
Edit: Is it possible to generalize the result for values other than 1001? If so please try to include it in your answer. Thank you so much!
Best Answer
Show that given a set of positive n integers, there exists a non-empty subset whose sum is divisible by n shows that $1001$ does work. But you also need to show that it's the smallest $n$ that works. To do that, construct a set of $1000$ numbers where no subset sums to a multiple of $1001$. For example, take $1000$ numbers that are each congruent to $1 \pmod {1001}$: then the sum of any subset of size $k$ of them will be congruent to $k \pmod {1001}$, and as there are only $1000$ numbers, any non-empty subset must have $1 \leq k \leq 1000$.