AIME 1983 · 第 8 题

Solution

Solution 1

Expanding the binomial coefficient, we get ${200 \choose 100}=\frac{200!}{100!100!}$. Let the required prime be $p$; then $10 \le p < 100$. If $p > 50$, then the factor of $p$ appears twice in the denominator. Thus, we need $p$ to appear as a factor at least three times in the numerator, so $3p<200$. The largest such prime is $\boxed{061}$, which is our answer.

Solution 1.5, half (desperate)

The only way a single prime number will be left out after all the cancelation will have to satisfy the condition that out of all the multiples of the prime number we want to find, 2 of the multiples will have to be between 100 and 200, $61$ is good for this solution (if you know your primes) because $61 \cdot 2$ and $61 \cdot 3$ both lie in the interval $(100, 200)$.

The reason for this is because if 2 copies of the prime $p$ we want to find are on the numerator and one copy on the denominator (AKA it contains $p^2$ and also $\dfrac{1}{p}$), there will only be 1 copy of the prime we want to find when all the cancellation is made when reducing the original fraction (only $p$ is left after cancellation).

~ $Michaellin16$ (formatted shalomkeshet)

Solution 2: Full Thinking Process of Solution 1.5

We want the largest two‑digit prime factor of

$${200\choose100}=\frac{200\cdot199\cdot\ldots\cdot101}{100\cdot99\cdot\ldots\cdot1}.$$ Let $p$ be a two‑digit prime factor of this number. Any such $p$ that remains after cancellation must appear at least twice in the numerator, because one factor of $p$ in a multiple of $p$ in the numerator will cancel with itself in the denominator. Therefore, there must be at least two multiples of $p$ between $101$ and $200$.

Write such a multiple as $kp$, where $k$ is a positive integer. Then

$$101\le kp\le200.$$ Since $p$ is two‑digit, $10\le p\le99$. Dividing the inequality by $k$ gives

$$\frac{101}{k}\le p\le\frac{200}{k}.$$ For $k=1$, $\frac{101}{1}\le p\le\frac{200}{1}$, which gives $101\le p\le200$, impossible because $p$ is two‑digit.

For $k=2$, $\frac{101}{2}\le p\le\frac{200}{2}$, which gives $50.5\le p\le100$, so

$$51\le p\le99.$$ For $k=3$, $\frac{101}{3}\le p\le\frac{200}{3}$, which gives $33.67\le p\le66.67$, so

$$34\le p\le66.$$ Notice that for larger $k$, the upper bound is smaller, so larger $k$ minimize the maximum possible value of $p$.

Thus the possible range of $p$ that has at least two multiples in $[101,200]$ is the intersection

$$[51,99]\cap[34,66]=[51,66].$$ The largest prime in $[51,66]$ is $61$.

Therefore the largest two‑digit prime factor of ${200\choose100}$ is $\boxed{61}$.

Note: If $p$ was less than or equal to 50, then for $k=2$, $kp$ would not be in the range $[101,200]$. But since we have found a prime greater than 50, $k=2$ and $k=3$ works.

~ $SS240102696$

Solution 3: Clarification of Solution 1

We know that

$${200\choose100}=\frac{200!}{100!100!}$$ Since $p<100$, there is at least $1$ factor of $p$ in each of the $100!$ in the denominator. Thus there must be at least $3$ factors of $p$ in the numerator $200!$ for $p$ to be a factor of $n=\frac{200!}{100!100!}$. (Note that here we assume the minimum because as $p$ goes larger in value, the number of factors of $p$ in a number decreases,)

So basically, $p$ is the largest prime number such that

$$\left \lfloor\frac{200}{p}\right \rfloor>3$$ Since $p<\frac{200}{3}=66.66...$, the largest prime value for $p$ is $p=\boxed{61}$

~ Nafer

Note

Similar to 2023 MATHCOUNTS State Sprint #25

Comment

which came first, 1985 or 2023?