Difference between revisions of "2024 USAMO Problems/Problem 1"
Mathophobia (talk | contribs) (→Solution (Explanation of Video)) |
|||
(9 intermediate revisions by 2 users not shown) | |||
Line 3: | Line 3: | ||
d_2-d_1 \leq d_3-d_2 \leq \cdots \leq d_k-d_{k-1} . | d_2-d_1 \leq d_3-d_2 \leq \cdots \leq d_k-d_{k-1} . | ||
</cmath> | </cmath> | ||
+ | |||
+ | ==Solution (Explanation of Video)== | ||
+ | |||
+ | We can start by verifying that <math>n=3</math> and <math>n=4</math> work by listing out the factors of <math>3!</math> and <math>4!</math>. We can also see that <math>n=5</math> does not work because the terms <math>15, 20</math>, and <math>24</math> are consecutive factors of <math>5!</math>. Also, <math>n=6</math> does not work because the terms <math>6, 8</math>, and <math>9</math> appear consecutively in the factors of <math>6!</math>. | ||
+ | |||
+ | Note that if we have a prime number <math>p>n</math> and an integer <math>k>p</math> such that both <math>k</math> and <math>k+1</math> are factors of <math>n!</math>, then the condition cannot be satisfied. | ||
+ | |||
+ | If <math>n\geq7</math> is odd, then <math>(2)(\frac{n-1}{2})(n-1)=n^2-2n+1</math> is a factor of <math>n!</math>. Also, <math>(n-2)(n)=n^2-2n</math> is a factor of <math>n!</math>. Since <math>2n<n^2-2n</math> for all <math>n\geq7</math>, we can use [[Bertrand's Postulate]] to show that there is at least one prime number <math>p</math> such that <math>n<p<n^2-2n</math>. Since we have two consecutive factors of <math>n!</math> and a prime number between the smaller of these factors and <math>n</math>, the condition will not be satisfied for all odd <math>n\geq7</math>. | ||
+ | |||
+ | If <math>n\geq8</math> is even, then <math>(2)(\frac{n-2}{2})(n-2)=n^2-4n+4</math> is a factor of <math>n!</math>. Also, <math>(n-3)(n-1)=n^2-4n+3</math> is a factor of <math>n!</math>. Since <math>2n<n^2-4n+3</math> for all <math>n\geq8</math>, we can use Bertrand's Postulate again to show that there is at least one prime number <math>p</math> such that <math>n<p<n^2-4n+3</math>. Since we have two consecutive factors of <math>n!</math> and a prime number between the smaller of these factors and <math>n</math>, the condition will not be satisfied for all even <math>n\geq8</math>. | ||
+ | |||
+ | Therefore, the only numbers that work are <math>n=3</math> and <math>n=4</math>. | ||
+ | |||
+ | ~alexanderruan | ||
+ | |||
+ | As listed above, <math>n=3</math> and <math>n=4</math> work but <math>n=5</math> and <math>n=6</math> don't. Assume <math>n>6</math>, let <math>p</math> be the smallest positive integer that doesn't divide <math>n!</math>. It is easy to see <math>p</math> is the smallest prime greater than <math>n</math>. It is easy to see that both <math>p-1</math> and <math>p+1</math> are divisors of <math>n!</math> Let <math>q</math> be the smallest positive integer greater than <math>p</math> that is 2 mod 6. We see that either <math>q=p+3</math> or <math>q=p+1</math> but <math>q</math>, <math>q+1</math>, <math>q+2</math> must all be divisors of <math>n!</math> giving a difference of 1 after a difference of 2. Therefore, all <math>n>6</math> fail. | ||
+ | ~mathophobia | ||
==Video Solution== | ==Video Solution== | ||
https://youtu.be/ZcdBpaLC5p0 [video contains problem 1 and problem 4] | https://youtu.be/ZcdBpaLC5p0 [video contains problem 1 and problem 4] | ||
+ | |||
+ | ==See Also== | ||
+ | {{USAMO newbox|year=2024|before=First Question|num-a=2}} | ||
+ | {{MAA Notice}} |
Latest revision as of 18:21, 12 May 2024
Find all integers such that the following property holds: if we list the divisors of in increasing order as , then we have
Solution (Explanation of Video)
We can start by verifying that and work by listing out the factors of and . We can also see that does not work because the terms , and are consecutive factors of . Also, does not work because the terms , and appear consecutively in the factors of .
Note that if we have a prime number and an integer such that both and are factors of , then the condition cannot be satisfied.
If is odd, then is a factor of . Also, is a factor of . Since for all , we can use Bertrand's Postulate to show that there is at least one prime number such that . Since we have two consecutive factors of and a prime number between the smaller of these factors and , the condition will not be satisfied for all odd .
If is even, then is a factor of . Also, is a factor of . Since for all , we can use Bertrand's Postulate again to show that there is at least one prime number such that . Since we have two consecutive factors of and a prime number between the smaller of these factors and , the condition will not be satisfied for all even .
Therefore, the only numbers that work are and .
~alexanderruan
As listed above, and work but and don't. Assume , let be the smallest positive integer that doesn't divide . It is easy to see is the smallest prime greater than . It is easy to see that both and are divisors of Let be the smallest positive integer greater than that is 2 mod 6. We see that either or but , , must all be divisors of giving a difference of 1 after a difference of 2. Therefore, all fail. ~mathophobia
Video Solution
https://youtu.be/ZcdBpaLC5p0 [video contains problem 1 and problem 4]
See Also
2024 USAMO (Problems • Resources) | ||
Preceded by First Question |
Followed by Problem 2 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.