Difference between revisions of "1983 AIME Problems/Problem 8"

Latest revision as of 10:53, 30 October 2024

Problem

What is the largest $2$ -digit prime factor of the integer $n = {200\choose 100}$ ?

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 $2p$ 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: 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

@@ Line 1: / Line 1: @@
+__TOC__
 == Problem ==
-What is the largest 2-digit [[prime]] factor of the integer <math>{200\choose 100}</math>?
+What is the largest <math>2</math>-digit [[prime]] factor of the integer <math>n = {200\choose 100}</math>?
+==Solution==
+=== Solution 1 ===
+Expanding the [[combination|binomial coefficient]], we get <math>{200 \choose 100}=\frac{200!}{100!100!}</math>. Let the required prime be <math>p</math>; then <math>10 \le p < 100</math>. If <math>p > 50</math>, then the factor of <math>p</math> appears twice in the denominator. Thus, we need <math>p</math> to appear as a factor at least three times in the numerator, so <math>3p<200</math>. The largest such prime is <math>\boxed{061}</math>, 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, <math>61</math> is good for this solution (if you know your primes) because <math>61 \cdot 2</math> and <math>61 \cdot 3</math> both lie in the interval <math>(100, 200)</math>.
+The reason for this is because if 2 copies of the prime <math>p</math> we want to find are on the numerator and one copy on the denominator (AKA it contains <math>2p</math> and also <math>\dfrac{1}{p}</math>), 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 <math>p</math> is left after cancellation).
+~ <math>Michaellin16</math> (formatted shalomkeshet)
+=== Solution 2: Clarification of Solution 1 ===
+We know that
+<cmath>{200\choose100}=\frac{200!}{100!100!}</cmath>
+Since <math>p<100</math>, there is at least <math>1</math> factor of <math>p</math> in each of the <math>100!</math> in the denominator. Thus there must be at least <math>3</math> factors of <math>p</math> in the numerator <math>200!</math> for <math>p</math> to be a factor of <math>n=\frac{200!}{100!100!}</math>. (Note that here we assume the minimum because as <math>p</math> goes larger in value, the number of factors of <math>p</math> in a number decreases,)
-== Solution 1 ==
+So basically, <math>p</math> is the largest prime number such that
-Expanding the [[combination|binomial coefficient]], we get <math>{200 \choose 100}=\frac{200!}{100!100!}</math>. Let the prime be <math>p</math>; then <math>10 \le p < 100</math>. If <math>p > 50</math>, then the factor of <math>p</math> appears twice in the denominator. Thus, we need <math>p</math> to appear as a factor three times in the numerator, or <math>3p<200</math>. The largest such prime is <math>\boxed{061}</math>, which is our answer.
+<cmath>\left \lfloor\frac{200}{p}\right \rfloor>3</cmath>
+Since <math>p<\frac{200}{3}=66.66...</math>, the largest prime value for <math>p</math> is <math>p=\boxed{61}</math>
-== Solution 2: Parity and Logic ==
+~ Nafer
-Expanding <math>{200 \choose 100}</math>,  we find that the remaining product is all the odd number from 199 to 101. We want a prime number to be a factor of one such odd number. If that is the case, the prime number must end in an odd number as well, for the last digit of the multiple must be odd. Therefore the prime number must end in one, and going down the list of two digit multiples we try 71, then 61. We find that 61 does indeed work, as <math>61 \cdot 3 = 183.</math>
+==Note==
+Similar to 2023 MATHCOUNTS State Sprint #25
 == See Also ==

1983 AIME (Problems • Answer Key • Resources)
Preceded by Problem 7	Followed by Problem 9
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search