Is there a set of 4004 positive integers such that the sum of each subset of 2003 elements is not divisible by 2003?
Answer
Yes.
Solution
Take 2002 distinct positive integers = 0 mod 2003, and 2002 distinct integers = 1 mod 2003. Then any subset of 2003 integers must include at least 1 and at most 2002 integers = 1 mod 2003 (and the rest = 0 mod 2003) and hence its sum mod 2003 is non-zero.
Thanks to Suat Namli.
© John Scholes
jscholes@kalva.demon.co.uk
6 July 2003