IMO 1995 · Problem 6

Let \(p\) be an odd prime number. How many \(p\)-element subsets \(A\) of \(\{1,2,\ldots 2p\}\) are there, the sum of whose elements is divisible by \(p\)?

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{\frac{\binom{2p}{p}+2p-2}{p}}. \]

Solution

Partition the underlying set into \[ L=\{1,2,\ldots,p\},\qquad R=\{p+1,p+2,\ldots,2p\}. \] For a subset \(A\), write \(s(A)=\sum_{a\in A}a\).

The two \(p\)-element subsets \(L\) and \(R\) have sums \[ s(L)=\frac{p(p+1)}2,\qquad s(R)=\frac{p(3p+1)}2. \] Both are divisible by \(p\), since \(p\) is odd.

Now consider all other \(p\)-element subsets. Each contains \(k\) elements of \(L\), where \[ 1\le k\le p-1. \] Define a permutation \(T\) that cyclically shifts \(L\), \[ 1\mapsto2\mapsto\cdots\mapsto p\mapsto1, \] and fixes every element of \(R\). Apply \(T\) to subsets by applying it to each element.

Every element of \(L\) increases by \(1\) modulo \(p\), while every element of \(R\) remains fixed. Therefore \[ s(T(A))\equiv s(A)+k\pmod p. \] The number \(k\) is unchanged by \(T\), so, for \(j=0,1,\ldots,p-1\), \[ s(T^j(A))\equiv s(A)+jk\pmod p. \]

Because \(p\) is prime and \(1\le k\le p-1\), these \(p\) residues are all distinct: equality for indices \(i,j\) would imply \(p\mid(i-j)k\), hence \(p\mid i-j\), and thus \(i=j\). Consequently, \[ A,T(A),\ldots,T^{p-1}(A) \] are \(p\) distinct subsets, exactly one of which has sum divisible by \(p\).

These collections partition all the subsets other than \(L\) and \(R\). Indeed, \(T^p\) is the identity, so any two such collections that intersect coincide. There are thus \[ \frac{\binom{2p}{p}-2}{p} \] collections, each contributing exactly one qualifying subset.

Adding \(L\) and \(R\), the required number is \[ 2+\frac{\binom{2p}{p}-2}{p} =\boxed{\frac{\binom{2p}{p}+2p-2}{p}}. \]

The solution was checked against John Scholes' IMO solution archive (Kalva).