Find all integers $x$ so that there is an integer y so that ${x\choose y} = 1999000$.

Question

(HMMT 2000 Guts round #45). Find all integers $x$ so that there is an integer y so that ${x\choose y} = 1999000$.

The point of this question is to better understand a post on AoPs. I'm not even sure if the post is entirely correct. I'd say the main point I don't get is why we can't have $y> 1999$. I don't quite understand why their use of Bertrand's postulate works, since it might not ensure there is a prime exceeding y between $x-y+1$ and $x$. The Sylvester-Schur theorem mentioned below can be used to ensure this, but I don't think it is necessary.

I checked out the solution here at AOPS.

Is there a way to shorten the solution on AoPs that avoids using Bertrand's postulate?

Answer 1

To shorten the AOPS answer:

Claim: $x = 1999000, x=2000$ are the only solutions.

Set $N = 1999000$ for simplicity. $\binom{N}{1} = N$ and $\binom{2000}{2} = N$ are nearly trivial. Now we show there are no other solutions. We consider three cases:

1. $x<1999$
2. $x = 1999$
3. $x>1999$

For the first case, note that $1999$ is prime. Since $N$ has a factor of $1999$, no binomial coefficient with $x < 1999$ can be equal to $N$, so there are no solutions to the first case.

It's easy to show that $\binom{1999}{3} > N > \binom{1999}{2}$, and thus there are no solutions to the second case.

For the third case: we know the binomial formula. Let's consider what happens if we increase $y$ by $1$ while keeping $N$ constant, and we assume our new $x$ will be $x+n$, and for the moment that $n$ is positive:

$$ \begin{gather} N = \frac{x!}{y! \cdot (x-y)!} = \frac{(x+n)!}{(y+1)! \cdot (x+n-y-1)!} \\[1ex] (x+n)! \cdot (x-y)! \cdot y! = x! \cdot (y+1)! \cdot (x+n-y-1)! \\[1ex] (x+n)(x+n-1)\cdots (x+1) = (y+1) \cdot [(x-y+n-1)(x-y+n-2) \cdots (x-y+1)] \\[1ex] y+1 = \frac{(x+n)(x+n-1)\cdots(x+1) \color{red}{ \ [n \text{ terms}}]} {(x-y+n-1)(x-y+n-2) \cdots (x-y+1) \color{blue}{ \ [\mathbf{n-1} \text{ terms}}]} \\[1ex] y+1 = (x+1) \prod_{k=1}^n \frac{x+k}{x+k-y-1} \end{gather}$$

We know $x > y$ here, meaning that every term in the product is positive greater than zero, and the product is positive greater than zero (Man, where was my brain when I wrote this?). But this is a contradiction: the equality can't hold if $x>y$. Hence, $n$ must be negative if we increase $y$ by 1. (Perform the same manipulations with $x-n$ and you get equations that could hold.) Because of the symmetry of the binomials, this will be true until $y=x/2$, at which point it $x$ will reach a minimum.

Hence there are no solutions with $x>1999$, and we are done.

Answer 2

Promoting my comment to an answer.

The tricky range is when $x<1999$. The key observation, as explained by Eric Snyder, is that as $1999$ is a prime, there are no solutions in this range.

The rest of the possibilities are easier to cover. Without loss of generality we can assume that $2y\le x$. This is because $$\binom x y=\binom x {x-y}.$$ In other words, the mirror symmetry of Pascal's triangle means that any number in it can be found on the left half. Furthermore, the entries on any row of Pascal's triangle are increasing on the left half: with $0\le y<y'\le x/2$ we have $$ \binom x y <\binom x {y'}. $$

Reusing Eric's observation that $$ \binom {1999}2 < 1999000 <\binom {1999}3 $$ implying that $x=1999$ does not work.

When $x\ge2000$ the key is that we must have $y\le2$. For if $y>2$, then we have $$ \binom x y> \binom x 2 \ge \binom {2000} 2 =1999000. $$ That leaves us the solutions $$ \binom {2000}2=1999000=\binom {1999000}1. $$