combinatorics - $n_{p,k} = frac{1}{p}binom{p}{k}$ for counting $k$-element subsets of $left{1,2,ldots,pright}$ with sum divisible by $p$

Let $p$ be prime and $k$ be an integer where $0.

Let $n_{p,k}$ denote the number of subsets $S$ of $\{1, 2, ..., p\}$ such that $\left|S\right| = k$ and such that the sum of all the elements in $S$ is divisible by $p$.

Show that $n_{p,k} = \dfrac{1}{p}\dbinom{p}{k}$.

Attempted work :

Let $l$ be positive integer such that $kl \equiv 1\; (\bmod p)$

and $\{a_1, a_2, ..., a_k\} \in \mathcal F_a(p,k)$

Let $f_{a,b} : \mathcal F_a(p,k) \to \mathcal F_b(p,k)$ defined by

$f(\{a_1, a_2, ..., a_k\}) = \{b_1, b_2, ..., b_k\}$ , where

$a_1 + l(a-b) \equiv b_1\; (\bmod p)\;\;, \; 0\leq b_1

$a_2 + l(a-b) \equiv b_2\; (\bmod p)\;\;, \; 0\leq b_2

.

.

$a_k + l(a-b) \equiv b_k\; (\bmod p)\;\;, \; 0\leq b_k

1) To show that $f$ is injective

Let $f(\{a_1, a_2, ..., a_k\}) = f(\{a'_1, a'_2, ..., a'_k\})$

so $\{b_1, b_2, ..., b_k\} = f(\{a'_1, a'_2, ..., a'_k\})$

we obtain $a'_i + l(a-b) \equiv b_i\; (\bmod p)$

and $a'_i \equiv a_i\; (\bmod p)$

so $a'_i = a_i , \;\forall i = 1, 2, ..., p$, thus $f$ is injective.

2) To prove that $f$ is surjective

Let $\{b_1, b_2, ..., b_k\} \in \mathcal F_b(p,k)$

Choose

$a_1 \equiv b_1- l(a-b) \; (\bmod p)$

$a_2 \equiv b_2- l(a-b) \; (\bmod p)$

.

.

$a_k \equiv b_k- l(a-b) \; (\bmod p)$ , where $gcd(l,p) = 1$

so, $f(\{a_1,\dots,a_k\}) = \{b_1, \dots, b_k\}$, thus $f$ is surjective.

Therefore $f$ is bijective, $|\mathcal F_a(p,k)|= |\mathcal F_b(p,k)|\;\forall a, b$ so $|\mathcal F_0(p,k)|= \frac{1}{p}\binom{p}{k}$.

Answer

Let $X_k$ be the set of $k$-element subsets of $\{1,2,\ldots,p\}$. Let the cyclic group $G=\mathbf{Z}/p\mathbf{Z}$ act on $X_k$ by translation: that is, for $a\in G$, we define

$$\sigma_a(\{x_1,\dots, x_k\}) = \{x_1+a,\ldots,x_k+a\}$$
where addition is mod $p$. This makes sense since translation preserves distinctness.

So far this makes sense for any $p$. But when $p$ is prime, this action is free: that is, if $a\ne0$, there is no $k$-tuple mapped to itself by $\sigma_a$. A cute way to see this is to look at the (mod $p$) sum of the elements of a subset. If we apply $\sigma_a$ to a subset whose sum is $s$, the sum of the resulting elements is $s+ak$ (mod $p$). If the subset is fixed by $\sigma_a$, then $s+ak=s$ (mod $p$), so $ak=0$ (mod $p$). But $k$ is not divisible by $p$, hence (since $p$ is prime) $a=0$ (mod $p$), and we see the action is free.

So each orbit of the action has size $p$ (hence $\binom pk$ is divisible by $p$) and furthermore each possible sum appears exactly once in each orbit, for a total of $\frac1p\binom pk$ times each.

(Added in response to OP comment:)

At a high school level, and expressed without group theory, we are arguing that when $p$ is prime, the following group of $p$ subsets

$$\begin{array}{lcl} \{x_1,&\dots,&x_k\}\\ \{x_1+1,&\ldots,&x_k+1\} \mod p\\ \vdots&\vdots&\vdots\\ \{x_1+p-1,&\ldots,&x_k+p-1\} \mod p \end{array}$$
all have different sums mod $p$, so each possible sum appears exactly once. (This also means the subsets in the group are actually different.) As $X_k$ is the disjoint union of groups of this kind, that means the possible sums occur equally often as you look across $X_k$.

If you're in high school, there are a few details to fill in, so you should do that. But the other thing to do would be to learn some basic group theory, which is accessible to any high school student (some experience with proofs helps, but group theory is as good as geometry for studying mathematical argument anyway). Once you check that what you have is a group acting freely on a set, a lot of those details come for free, and the structure of the argument becomes much more transparent.