Problem 6

Let

p

be an odd prime number. How many

p

-element subsets

A

\{1,2,\ldots,2p\}

are there, the sum of whose elements is divisible by

p

Step 3 of 3: Count one zero-sum set per orbit

Previous step Next step

In plain words

Since $p$ is prime and $r$ is nonzero modulo $p$ , the $p$ sums are all residues.

2+\frac{\binom{2p}{p}-2}{p}

Detailed analysis

The successive total sums differ by $r\not\equiv0\pmod p$ , so they are all residues modulo $p$ . Exactly one member of every orbit has total sum divisible by $p$ . The nonexceptional contribution is therefore $\frac{\binom{2p}{p}-2}{p}$ ; adding the two excluded subsets gives $2+\frac{\binom{2p}{p}-2}{p}$ .