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 $$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\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 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ cannot consist of a power of $p$ only.

---

Alternative solution.

Suppose that for some $n$ and $k$, $$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\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 \left(\genfrac{}{}{0ex}{}{k-1}{n-m}\right)$$ 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 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ does not exceed that in the canonical representation of $m$. As the assumptions of the problem imply $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\ge \left(\genfrac{}{}{0ex}{}{n}{2}\right)>n\ge m$, this leads to a contradiction.