Summer Problem Solving Marathon Solution #32

Given any S meeting the conditions, let s be the number of elements in S, and let N be the sum of all the elements in S.

Given any n∈S, the mean of the elements in S other than n is an integer. There are s-1 other elements in S, and their sum is N - n. So s-1 is a factor of N-n. Thus N and n are congruent mod s-1 (that is, they have the same remainder when divided by s-1).

Since 1∈S, N and 1 are congruent mod s-1, and in fact all elements of S are congruent to 1 mod s-1. Since 2002∈S, we know that 2002 is congruent to 1 mod s-1, so 2001 is a multiple of s-1. Since 2001 = 3 x 23 x 29, the possible values for s are 4, 24, 30, 70, 88, 668, and 2002.

If we list the numbers that are congruent to 1 mod s-1, we get 1, s, 2s-1, 3s-2, ... . The s^th such number is 1 + (s-1)(s-1) = s² - 2s + 2. So the largest element of S must be of size at least s² - 2s + 2. Since the largest element is 2002, this rules out 70, 88, 668, and 2002 as values of s.

Thus the largest possible value of s is 30. It remains to see that this value of s can be made to work. We will need a set of 30 elements, each of which is congruent to 1 mod 29. There are many sets meeting this constraint, including {1, 30, 59, 88, ..., 813, 2002}.