Maths Olympiad Prep

Library / /12 of 106

Number theory Difficulty 7.7 National olympiad, round 2 Find the answer

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

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let p p be an odd prime number. We are tasked with finding the number of p p -element subsets A A of the set {1,2,,2p}\{1, 2, \dots, 2p\} such that the sum of the elements in A A is divisible by p p .

### Step 1: Representation of Subsets

The set {1,2,,2p}\{1, 2, \dots, 2p\} contains 2p 2p elements. We want to choose p p elements from these 2p 2p elements. The number of ways to choose p p elements from 2p 2p is given by (2pp)\binom{2p}{p}.

### Step 2: Applying Properties of Subsets and Congruences

When we consider a subset A A with p p elements, the sum of its elements, denoted as aAa \sum_{a \in A} a , needs to satisfy:

aAa0(modp). \sum_{a \in A} a \equiv 0 \pmod{p}.

By properties of combinatorial numbers, when subsets are considered modulo a prime, symmetry and cancellation often play roles. Specifically, we will use the properties of binomial coefficients and modulo arithmetic.

### Step 3: Symmetry and Combinatorial Argument

Given the symmetry and periodicity modulo p p , every element's contribution modulo p p can be considered as additive symmetric pairs (x,2p+1x)(x, 2p+1-x) whose sums modulo p p cover the full range as the whole set is considered.

### Step 4: Exploiting Known Theorems

Using Lucas' theorem or known properties about binomial coefficients modulo an odd prime p p , it can be derived that:

(2pp)2(modp). \binom{2p}{p} \equiv 2 \pmod{p}.

This relation outlines that, up to a multiple of p p , there are:

(2pp)=2p×k+2 \binom{2p}{p} = 2p \times k + 2

possible selections of sets, where the residue class modulo p p , i.e., remainder when divided by p p , is 2 2 .

### Conclusion

Since we are dividing the total number of such subsets by p p to get those subsets where the sum is specifically zero modulo p p , the formula for the number of such subsets is:

1p((2pp)2)+2. \frac{1}{p} \left( \binom{2p}{p} - 2 \right) + 2.

This simplifies to:

2+1p((2pp)2). \boxed{2 + \frac{1}{p} \left( \binom{2p}{p} - 2 \right)}.

Thus, the number of p p -element subsets A A such that the sum of the elements is divisible by p p is given by the expression inside the boxed formula.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.