Berkeley Math Circle Monthly Contest 6

Solution:
Given $k$ and $x$, let $A$ be the set of all sets of the form
$$\left\{m_{1}+\frac{1}{k}, m_{2}+\frac{2}{k}, \ldots, m_{k}+\frac{k}{k}\right\}$$
where the $m_{i}$ are integers, $1 \leq m_{i} \leq x$. Clearly, $A$ consists of $x^{k}$ sets, each of which has $k$ distinct elements. Now we count the elements of $A$ in another way.

Arrange the elements of a member of $A$ in increasing order:
$$n_{1}+\frac{p_{1}}{k}<n_{2}+\frac{p_{2}}{k}<\cdots<n_{k}+\frac{p_{k}}{k}$$
For each permutation $p=\left(p_{1}, \ldots, p_{k}\right)$ of the numbers $(1, \ldots, k)$, let $A_{p} \subseteq A$ be the subset consisting of sets whose sorted presentation (1) displays the given sequence $p$ of numerators. We claim that the size of $A_{p}$ is a binomial coefficient $\left(\begin{array}{c}x+r_{p} \\ k\end{array}\right)$, where $r_{p}$ depends on $p$ (hence on $k$) but not on $x$.

For $n_{1}, \ldots, n_{k}\left(1 \leq n_{i} \leq x\right)$ to define an element of $A_{p}$, it is necessary and sufficient that the inequalities (1) hold. So we must have
$$1 \leq n_{1} \leq n_{2} \leq \cdots \leq n_{k} \leq x$$
Moreover, the strict inequality $n_{i}<n_{i+1}$ is required whenever $p_{i}>p_{i+1}$. To condense all these conditions, it is convenient to define nonnegative integers $e_{1}, e_{2}, \ldots, e_{k}$ by
$$\begin{aligned} e_{1} & =0 \\ e_{i+1} & = \begin{cases}e_{i}+1 & \text{ if } p_{i}<p_{i+1} \\ e_{i} & \text{ if } p_{i}>p_{i+1}\end{cases} \end{aligned}$$
Then the conditions may be written as
$$1 \leq n_{1}+e_{1}<n_{2}+e_{2}<\cdots<n_{k}+e_{k} \leq x+e_{k} .$$
We observe that $\left\{\left(n_{1}+e_{1}, \ldots, n_{k}+e_{k}\right)\right\}$ may be any $k$-element subset of $\left\{1,2, \ldots, x+e_{k}\right\}$, written in increasing order. So, writing $r_{p}=e_{k}$,
$$\left|A_{p}\right|=\left(\begin{array}{c} x+r_{p} \\ k \end{array}\right)$$
Observe that $0 \leq r_{p} \leq k-1$. Letting $a_{i}$ be the number of $p$ for which $r_{p}=i$, we obtain
$$x^{k}=|A|=\sum_{p}\left|A_{p}\right|=\sum_{i=0}^{k-1} a_{i}\left(\begin{array}{c} x+i \\ k \end{array}\right)$$
Here the $a_{i}$ are clearly nonnegative integers. To prove that they are positive, it suffices to exhibit, for each $i$, a $p$ with $r_{p}=i$; the permutation $(n, n-1, \ldots, i+1,1,2, \ldots, i)$ is readily seen to work.