IMO Team Selection Contest

Assume w.l.o.g. that $n \ge 2k$ (if $n < 2k$, then interchange the roles of $k$ and $n-k$). Let $p$ be an arbitrary prime number. Consider the numbers that remain into the numerator of the expression
$$\binom{n}{k} = \frac{n \cdot (n-1) \cdots (n-k+1)}{k \cdot (k-1) \cdots 1}$$
after reducing all factors by the highest power of $p$ by which they are divisible. Suppose that some two of the $k$ factors resulting after this step are equal. Then the corresponding initial factors are of the form $s \cdot p^i$ and $s \cdot p^j$, where $i > j$. But then $n \ge s \cdot p^i \ge p \cdot s \cdot p^j > p \cdot (n-k) \ge 2 \cdot (n-k)$, which contradicts the assumption $n \ge 2k$. Hence the $k$ new factors are pairwise different. As $1 < k < n-1$, the numerator initially contains at least two consecutive numbers, at least one of which is not divisible by $p$. This number does not change in the process described above. By the assumption $n \ge 2k$, this number is greater than $k$. Consequently, the product remaining in the numerator after elimination of powers of $p$ is greater than the denominator $k \cdot (k-1) \cdots 1$. This means that the powers of $p$ in the original numerator cannot be completely cancelled out with the denominator. So the canonical representation of $\binom{n}{k}$ cannot consist of a power of $p$ only.

Suppose that for some $n$ and $k$,
$$\binom{n}{k} = \frac{n \cdot (n-1) \cdots (n-k+1)}{k \cdot (k-1) \cdots 1} = p^t,$$
where $p$ is a prime number and $t$ is some positive integer. Let $m$ be a number in $\{n, n-1, \dots, n-k+1\}$, in the canonical representation of which the exponent of $p$ is the largest. Then the exponent of $p$ in the canonical representation of $n, n-1, ..., m+1$ coincides with that in the canonical representation of $n-m, n-m-1, ..., 1$, respectively. Similarly, the exponent of $p$ in the canonical representation of $m-1, ..., n-k+1$ coincides with that in the canonical representation of $1, ..., m-1-n+k$, respectively. Consequently, the exponent of $p$ in the canonical representation of the product $n(n-1)...(m+1)(m-1)...(n-k+1)$ equals to that in the canonical representation of the product $(n-m)!(m-1-n+k)!$. Since
$$\frac{k!}{(n-m)!(m-1-n+k)!} = k \cdot \frac{(k-1)!}{(n-m)!(k-1-n+m)!} = k \cdot \binom{k-1}{n-m}$$
is clearly an integer, the exponent of $p$ in the canonical representation of $(n-m)!(m-1-n+k)!$ does not exceed that in the canonical representation of $k!$. Hence, the exponent of $p$ in the canonical representation of $\binom{n}{k}$ does not exceed that in the canonical representation of $m$. As the assumptions of the problem imply $\binom{n}{k} \ge \binom{n}{2} > n \ge m$, this leads to a contradiction.