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$?
Problem
Source:
Tags:
25.05.2007 03:25
Here's my solution from MathLinks: Define $X: =\{ 1,2,...,p\},Y: =\{p+1,p+2,...,2p\}$. See $X$ and $Y$ as a representant system for $\mathbb{Z}/ p \mathbb{Z}$, since not more is necessary (so all identities concerning $X$ or $Y$ must be seen $\mod p$). For a subset $A \subset X$ and $z \in \mathbb{Z}/ p \mathbb{Z}$ define $A+z: =\{ a+z \in X| a \in A \}$ and similar for a subset $B \subset Y$. Call $A \subset X$ trivial iff $A=\emptyset$ or $A=X$, similar for $B \subset Y$ again. Now there are only $4$ subsets $P \subset (X \cup Y)$ such that both $P \cap X$ and $P \cap Y$ are trivial, so call these subsets trival from now on too. Then define for a nontrivial subset $P \subset (X \cup Y)$ a 'translation': if $P \cap X$ is nontrivial define $P+z : = ((P\cap X) +z) \cup (P \cap Y)$ and $P+z : = (P \cap X) \cup ((P\cap Y) +z)$ otherwise. Now it's easy to see that when $z$ goes through all possible residue classes, that also the sum of the elements of $P+z$ goes through all of them, so there is exactly one sum that is divisible by $p$. So the 'translation' divides the nontrivial subsets into equivalence classes of $p$ sets each, all sets of the same class having same number of elements. Since there are exactly $\binom{2p}{p}$ subsets of the desired order $p$ and $2$ of them are trivial, we get that there are $\frac{\binom{2p}{p}-2}{p}+2$ such subsets. (note that this technique trivially generalises to other types of subsets and all sets of type $\{1,2,...,kp\}$)
20.12.2021 07:41
Imo short list 1995 N6