Question

A set $\mathcal{S}$ of distinct positive integers has the following property: for every integer $x$ in $\mathcal{S},$ the arithmetic mean of the set of values obtained by deleting $x$ from $\mathcal{S}$ is an integer. Given that $1$ belongs to $\mathcal{S}$ and that $2002$ is the largest element of $\mathcal{S},$ what is the greatest number of elements that $\mathcal{S}$ can have?

Answer

Solution:

Let $\mathcal{S}$ have $n$ elements with sum $S.$ The condition says $\frac{S - x}{n - 1}$ is an integer for every $x \in \mathcal{S},$ which means every element is congruent to $S$ modulo $n - 1.$ In particular all elements are congruent to each other, and since $1 \in \mathcal{S},$ every element is $1$ more than a multiple of $n - 1.$

Then $2002 \equiv 1 \pmod{n - 1},$ so $n - 1$ divides $2001 = 3 \cdot 23 \cdot 29.$ Moreover the $n$ distinct elements run from $1$ up to $2002$ in steps that are multiples of $n - 1,$ so $2002 \ge 1 + (n - 1)^2,$ forcing $n - 1 \le 44.$ The largest divisor of $2001$ that is at most $44$ is $29,$ so $n \le 30.$

Thirty is attainable: take the $29$ numbers $1, 30, 59, \ldots, 813$ together with $2002.$ All are $\equiv 1 \pmod{29},$ and the sum of all $30$ is $\equiv 30 \equiv 1 \pmod{29},$ so every deleted mean is an integer. The answer is $30.$

2002 AIME I Problem 14

Solution:

Problem 14 in Other Years