Difference between revisions of "1983 AIME Problems/Problem 8"
(→Solution) |
Michaellin16 (talk | contribs) (→Solution 1) |
||
| (24 intermediate revisions by 6 users not shown) | |||
| Line 1: | Line 1: | ||
| + | __TOC__ | ||
| + | |||
== Problem == | == Problem == | ||
What is the largest <math>2</math>-digit [[prime]] factor of the integer <math>n = {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== |
| + | === 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. | 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. | ||
| − | |||
| − | + | ||
| − | <math></math> | + | |
| + | |||
| + | |||
| + | |||
| + | === 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 times 2 and 6l times3 are both between 100-200 the reason for this is becauase if 2 copies of the prime we want to find are on numerater and one copy on the denominater, there will only be 1 copy of the prime we want to find when all the cancelation is made when reducing the origional fraction. | ||
| + | |||
| + | <math>Michaellin16</math> | ||
| + | |||
| + | === 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,) | ||
| + | |||
| + | So basically, <math>p</math> is the largest prime number such that | ||
| + | <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> | ||
| + | |||
| + | ~ Nafer | ||
| + | ==Note== | ||
| + | Similar to 2023 MATHCOUNTS State Sprint #25 | ||
== See Also == | == See Also == | ||
Revision as of 20:00, 26 June 2024
Contents
Problem
What is the largest 
-digit prime factor of the integer 
?
Solution
Solution 1
Expanding the binomial coefficient, we get 
. Let the required prime be 
; then 
. If 
, then the factor of appears twice in the denominator. Thus, we need to appear as a factor at least three times in the numerator, so 
. The largest such prime is 
, 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 times 2 and 6l times3 are both between 100-200 the reason for this is becauase if 2 copies of the prime we want to find are on numerater and one copy on the denominater, there will only be 1 copy of the prime we want to find when all the cancelation is made when reducing the origional fraction.
Solution 2: Clarification of Solution 1
We know that
![\[{200\choose100}=\frac{200!}{100!100!}\]](http://latex.artofproblemsolving.com/c/a/c/cac11b8537859d11a4e3be8efcef3a4a67c333af.png)
Since 
, there is at least 
factor of in each of the 
in the denominator. Thus there must be at least 
factors of in the numerator 
for to be a factor of 
. (Note that here we assume the minimum because as goes larger in value, the number of factors of in a number decreases,)
So basically, is the largest prime number such that
![\[\left \lfloor\frac{200}{p}\right \rfloor>3\]](http://latex.artofproblemsolving.com/d/6/b/d6b4bcf5fed67b290052cae032950a11ab1ad2be.png)
Since 
, the largest prime value for is 
~ Nafer
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 | ||
