Given an integer $k \geq 2$, determine the largest number of divisors the binomial coefficient $\binom{n}{k}$ may have in the range $n-k+1, \ldots, n$ , as $n$ runs through the integers greater than or equal to $k$.
Problem
Source: Romania TST 2015 Day 4 Problem 2
Tags: binomial coefficients, Romanian TST, number theory
05.06.2015 17:10
$k-1$.A trivial example is $n=k!$. To prove that $k$ is impossible,pick a prime $p/k$,and pick $x \in (n-k+1,...,n)$ for which $v_p(x)$ is maximal.Obviously $v_p(x) \ge v_p(i)$ for $i=1,...,k$.Now a trivial counting and bounding of $v_p(\binom{n}{k})$ via Legendre's formula and the $[a+b]-[a]-[b] \in (0,1)$ shows that $v_p(\binom{n}{k})<v_p(x)$,hence $x$ cannot divide $\binom{n}{k}$,Q.E.D.
24.12.2015 19:51
Let $S = \{n, n - 1, \cdots, n - k + 1\}.$ We will show that $\tbinom{n}{k}$ is divisible by at most $k - 1$ elements of $S.$ For an equality case, consider $n = k!$, and note that \[\binom{n}{k} = \frac{n(n - 1)\cdots(n - k + 1)}{k!} = (n - 1)\cdots(n - k + 1)\]is clearly divisible by $k - 1$ elements of $S.$ It remains to show that $\tbinom{n}{k}$ cannot be divisible by all elements of $S.$ Choose a prime divisor $p \mid k$ and let $\alpha = \max_{x \in S} v_p(x).$ Then if $\beta > \alpha$, there is no multiple of $p^{\beta}$ between $n - k$ and $n$, implying that $\left\lfloor \frac{n - k}{p^{\beta}} \right\rfloor = \left\lfloor \frac{n}{p^{\beta}} \right\rfloor.$ Thus, by Legendre's Formula, \begin{align*} v_p\left[\binom{n}{k}\right] &= \sum_{j \ge 1} \left(\left\lfloor \frac{n}{p^j} \right\rfloor - \left\lfloor \frac{n - k}{p^j} \right\rfloor - \left\lfloor \frac{k}{p^j} \right\rfloor\right) \\ &\le \sum_{j = 1}^{\alpha} \left(\left\lfloor \frac{n}{p^j} \right\rfloor - \left\lfloor \frac{n - k}{p^j} \right\rfloor - \left\lfloor \frac{k}{p^j} \right\rfloor\right). \end{align*}But recall that \begin{align*} \lfloor x + y \rfloor - \lfloor x \rfloor - \lfloor y \rfloor &= \{x\} + \{y\} - \{x + y\} \\ &= \left\{ \begin{array}{ll} 1 \text{ if } \{x\} + \{y\} < 1 \\ 0 \text{ otherwise} \end{array} \right. \end{align*}Hence, evaluating the first term by hand, the above sum is at most \[\left(\left\lfloor \frac{n}{p} \right\rfloor - \left\lfloor \frac{n - k}{p} \right\rfloor - \left\lfloor \frac{k}{p} \right\rfloor\right) + (\alpha - 1).\]But since $\{k / p\} = 0$, the above reasoning implies that $\left\lfloor \frac{n}{p} \right\rfloor - \left\lfloor \frac{n - k}{p} \right\rfloor - \left\lfloor \frac{k}{p} \right\rfloor = 0.$ Therefore, $v_p\left[\tbinom{n}{k}\right] \le \alpha - 1 < \max_{x \in S} v_p(x).$ Thus, if $x \in S$ satisfies $v_p(x) = \alpha$, it is clear that $x \nmid \tbinom{n}{k}.$ Consequently, $\tbinom{n}{k}$ is not divisible by all elements of $S$, as desired. $\square$