Difference between revisions of "2024 USAMO Problems/Problem 1"
Mathophobia (talk | contribs) (→Solution (Explanation of Video)) |
Scratch123 (talk | contribs) (→Solution (Explanation of Video)) |
||
Line 20: | Line 20: | ||
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. | 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 | ~mathophobia | ||
+ | |||
+ | ==Solution 2== | ||
+ | |||
+ | We claim only <math>n = 3</math> and <math>n = 4</math> are the only two solutions. First, it is clear that both solutions work. | ||
+ | |||
+ | Next, we claim that <math>n < 5</math>. For <math>n \geq 5</math>, let <math>x</math> be the smallest <math>x</math> such that <math>x+1</math> is not a factor of <math>n!</math>. Let the smallest factor larger than <math>x</math> be <math>x+k</math>. | ||
+ | |||
+ | Now we consider <math>\frac{n!}{x-1}</math>, <math>\frac{n!}{x}</math> and <math>\frac{n!}{x+k}</math>. Since <math>\frac{n!}{x-1} > \frac{n!}{x} > \frac{n!}{x+k}</math>, if <math>n</math> were to satisfy the conditions, then <math>\frac{n!}{x-1}-\frac{n!}{x} \geq \frac{n!}{x} - \frac{n!}{x+k}</math>. However, note that this is not true for <math>x \geq 5</math> and <math>k > 1</math>. | ||
+ | |||
+ | Note that the inequality is equivalent to showing <math>\frac{1}{x(x-1)} \geq \frac{k}{x(x+k)}</math>, which simplifies to <math>x+k \geq kx-k</math>, or <math>\frac{x}{x-2} \geq k \geq 2</math>. This implies <math>x \geq 2x-4</math>, <math>x \leq 4</math>, a contradiction, since the set of numbers <math>\{1, 2, 3, 4, 5\}</math> are all factors of <math>n!</math>, and the value of <math>x</math> must exist. Hence, no solutions for <math>n \geq 5</math>. | ||
==Video Solution== | ==Video Solution== |
Revision as of 04:33, 23 June 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
Solution 2
We claim only and
are the only two solutions. First, it is clear that both solutions work.
Next, we claim that . For
, let
be the smallest
such that
is not a factor of
. Let the smallest factor larger than
be
.
Now we consider ,
and
. Since
, if
were to satisfy the conditions, then
. However, note that this is not true for
and
.
Note that the inequality is equivalent to showing , which simplifies to
, or
. This implies
,
, a contradiction, since the set of numbers
are all factors of
, and the value of
must exist. Hence, no solutions for
.
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.