Exercise 4.5.7* (The probability that the sum of $k$ integers in $[\![1,n]\!]$ is divisible by $n$ is $1/n$)

Question

Let $n$ and $k$ be positive integers with $n >k$ and $(n,k) = 1$. Prove that if $k$ distinct integers are selected at random from $1,2,\ldots,n$, the probability that their sum is divisible by $n$ is $1/n$.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

I found on the net (math.stackexchange.com) the following crucial hint:

''Think of the numbers as integers modulo $n$. Consider the map
$$A = \{a_1,a_2,\ldots,a_k\} \mapsto \{a_1+1, a_2 + 1,\ldots, a_k +1\}.$$
This adds $k$ modulo $n$ to the sum of the elements of $A$.''

\hspace{5cm} answered Sep 5, 2017 Angina Seng.
\begin{proof} 
We suppose that $1 \leq k < n$ and that $k \wedge n = 1$.

Let $\mathscr{P}_k([\![1, n]\!])$ denote the set of subsets of $[\![1, n]\!]$ with $k$ elements, and $N = \left |\mathscr{P}_k([\![1, n]\!])ight|$ its cardinality (then $N = \binom{n}{k}$).

Consider 
$$\mathscr{B}_{k,n} = \left\{B \in \mathscr{P}_k([\![1, n]\!]) \mid \sum_{a \in B} a \equiv 0 \pmod night\}$$
the subset of $ B \in \mathscr{P}_k([\![1, n]\!])$ such that the sum of elements of $B$ is divisible by $n$. Then the wanted probability $p$ is $p = \left| \mathscr{B}_{k,n}ight|/ N$.

If
$$\mathscr{A}_{k,n} = \left\{A \in \mathscr{P}_k(\Z/n\Z) \mid \sum_{\alpha \in A} \alpha = 0 ight\},$$
Then $\left| \mathscr{A}_{k,n}ight| = \left| \mathscr{B}_{k,n}ight|$, because $\{1,2,\ldots,n\}$ is a complete residue system modulo $n$, so the map 
$$
\left\{
\begin{array}{ccl}
\mathscr{B}_{k,n} & 	o& \mathscr{A}_{k,n}\
 A = \{a_1,a_2,\ldots a_k\} &\mapsto &\{\alpha_1,\alpha_2,\ldots, \alpha_k\} = \{\overline{a_1},\overline{a_2},\ldots,\overline{a_k}\}
 \end{array}
 ight.
 $$
 is a bijection. It remains to compute the cardinality of $\mathscr{A}_{k,n}$. 
 
 Consider the map
$$
t
\left\{
\begin{array}{ccl}
\mathscr{P}_k([\![1, n]\!])& 	o& \mathscr{P}_k([\![1, n]\!])\
 A = \{\alpha_1,\alpha_2,\ldots, \alpha_k\} &\mapsto &\{\alpha_1 + 1,\alpha_2 + 1,\ldots, \alpha_k + 1\}  = \bigcup\limits_{\alpha \in A} \{\alpha +1\}.
 \end{array}
 ight.
 $$
 (Here $1 = \overline{1} \in \Z/n\Z$.)
 Then $t$ is bijective, with $t^{-1}(B) = \bigcup\limits_{\beta \in B} \{\beta -1\}$, so $t^i$ is defined for all integers $i \in \Z$, and 
 $$t^i(\{\alpha_1,\alpha_2,\ldots, \alpha_k\}) = \{\alpha_1 + \overline{i},\alpha_2+ \overline{i},\ldots, \alpha_k+ \overline{i}\}.$$
 
 We define the relation $\mathscr{R}$ between any two elements $A = \{\alpha_1,\alpha_2,\ldots, \alpha_k\},\ B = \{\beta_1,\beta_2,\ldots,\beta_k\}$ of $\mathscr{P}_k([\![1, n]\!])$ by
\begin{align*}
 A \sim B &\iff \exists i \in \Z,\ B = t^i (A)\
&\iff \exists \gamma \in \Z/n\Z, \ \forall j \in[\![1,k]\!], \beta_j = \alpha_j + \gamma.
\end{align*}
Then $\sim$ is an equivalence relation: $A = t^0(A) \sim A$; if $A \sim B$, then $B = t^i(A)$ for some $i \in \Z$, then $A = t^{-i}(B)$, so $B \sim A$; if $A \sim B$ and $B \sim C$, then $B = t^i(A), C =t^j(B)$ for some integers $i,j$, then $C = t^{i+j}(A)$, so $A \sim C$.

What is the class of $A = \{\alpha_1,\alpha_2,\ldots, \alpha_k\}$ for the relation $\sim$  (where $\alpha_1,\alpha_2,\ldots,\alpha_k$ are distinct)? Since $t^n(A) = A$, and $t^{n+j}(A) = t^{j}(A)$ for all $j$, the class of $A$ is
$$\dot{A} =\{A, t(A),t^2(A),\ldots,t^{n-1}(A)\}.$$
Moreover, if $t^i(A) = t^j(A)$, where $0 \leq i \leq j <n$, then $A = t^{j-i}(A) $. Therefore 
$$\sum\limits_{\alpha \in A} \alpha = \left(\sum\limits_{\alpha \in A} \alphaight)+ k(\overline{j}-\overline{i}),$$
thus $k(j-i) \equiv 0 \pmod n$, where $k \wedge n = 1$, so $j - i \equiv 0 \pmod n$ (and $0 \leq i \leq j < n$), thus $i = j$.

This shows that $|\dot{A}| = n$, so all the classes have same cardinality $n$, and the number of classes is $\frac{N}{n} = \frac{1}{n} \binom{n}{k}$ (in particular, this shows that if $k \wedge n = 1$, then $n \mid \binom{n}{k}$, which is not quite obvious).

The important fact is that every class contains a unique element $\{\gamma_1,\gamma_2,\ldots,\gamma_k\}$ in $\mathscr{A}_{k,n}$ (such that $\gamma_1 + \gamma_2 + \cdot + \gamma_k = 0$). Indeed,  consider the class $\dot{A}$ of $A =\{\alpha_1,\alpha_2,\ldots,\alpha_k\} \in \mathscr{P}_k([\![1, n]\!])$, and let $B = \{\gamma_1,\gamma_2,\ldots,\gamma_k\} = \{\alpha_1 + \overline{j},\alpha_2 + \overline{j},\ldots, \alpha_k + \overline{j}\}$ in the class $\dot{A}$. Then 
\begin{align*}
\gamma_1 + \gamma_2 + \cdots + \gamma_k = \alpha_1 + \alpha_2 + \cdots + \alpha_k + \overline{k}\overline{j}.
\end{align*}
Since $k \wedge n = 1$, there is a unique $\overline{j} \in \Z/n\Z$ such that $\alpha_1 + \alpha_2 + \cdots + \alpha_k + \overline{k}\overline{j} = 0$, so every class contains a unique element of $\mathscr{A}_{k,n}$. This shows that there are as many classes than elements of $\mathscr{A}_{k,n}$. Therefore
$$\left| \mathscr{A}_{k,n}ight| = \frac{|\mathscr{P}_k([\![1, n]\!])|}{n} = \frac{1}{n} \binom{n}{k},$$
so
$$p = \frac{\left| \mathscr{A}_{k,n}ight|}{ \binom{n}{k}} = \frac{1}{n}.$$
if $k \wedge n = 1$ and if $k$ distinct integers are selected at random from $1,2,\ldots,n$, the probability that their sum is divisible by $n$ is $1/n$.
\end{proof}

Note: In the language of group actions, the group $\Z/n \Z$ acts on $\mathscr{P}_k([\![1, n]\!])$ by
$$\gamma \cdot A = \bigcup\limits_{\alpha \in A} \{\alpha +\gamma\}.$$
By the preceding arguments, if $k \wedge n = 1$, all orbits have $n$ elements, and every orbit contains a unique element of $\mathscr{A}_{k,n}$, so
$$\left| \mathscr{A}_{k,n}ight| = \frac{|\mathscr{P}_k([\![1, n]\!])|}{n}.$$

Exercise 4.5.7* (The probability that the sum of $k$ integers in $[\![1,n]\!]$ is divisible by $n$ is $1/n$)

Answers

Comments

Exercise 4.5.7* (The probability that the sum of $k$ integers in $[\![1,n]\!]$ is divisible by $n$ is $1/n$)

Answers

Comments

Add answer