Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2024 USAMO Problems/Problem 1"

(Created page with "Find all integers <math>n \geq 3</math> such that the following property holds: if we list the divisors of <math>n !</math> in increasing order as <math>1=d_1<d_2<\cdots<d_k=n...")
 
(→‎Solution (Explanation of Video))
 
(12 intermediate revisions by 5 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 Solution)==
 +
 +
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
 +
 +
==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==
 +
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 00:50, 27 July 2024

Find all integers $n \geq 3$ such that the following property holds: if we list the divisors of $n !$ in increasing order as $1=d_1<d_2<\cdots<d_k=n!$, then we have \[d_2-d_1 \leq d_3-d_2 \leq \cdots \leq d_k-d_{k-1} .\]

Solution (Explanation of Video Solution)

We can start by verifying that $n=3$ and $n=4$ work by listing out the factors of $3!$ and $4!$. We can also see that $n=5$ does not work because the terms $15, 20$, and $24$ are consecutive factors of $5!$. Also, $n=6$ does not work because the terms $6, 8$, and $9$ appear consecutively in the factors of $6!$.

Note that if we have a prime number $p>n$ and an integer $k>p$ such that both $k$ and $k+1$ are factors of $n!$, then the condition cannot be satisfied.

If $n\geq7$ is odd, then $(2)(\frac{n-1}{2})(n-1)=n^2-2n+1$ is a factor of $n!$. Also, $(n-2)(n)=n^2-2n$ is a factor of $n!$. Since $2n<n^2-2n$ for all $n\geq7$, we can use Bertrand's Postulate to show that there is at least one prime number $p$ such that $n<p<n^2-2n$. Since we have two consecutive factors of $n!$ and a prime number between the smaller of these factors and $n$, the condition will not be satisfied for all odd $n\geq7$.

If $n\geq8$ is even, then $(2)(\frac{n-2}{2})(n-2)=n^2-4n+4$ is a factor of $n!$. Also, $(n-3)(n-1)=n^2-4n+3$ is a factor of $n!$. Since $2n<n^2-4n+3$ for all $n\geq8$, we can use Bertrand's Postulate again to show that there is at least one prime number $p$ such that $n<p<n^2-4n+3$. Since we have two consecutive factors of $n!$ and a prime number between the smaller of these factors and $n$, the condition will not be satisfied for all even $n\geq8$.

Therefore, the only numbers that work are $n=3$ and $n=4$.

~alexanderruan

As listed above, $n=3$ and $n=4$ work but $n=5$ and $n=6$ don't. Assume $n>6$, let $p$ be the smallest positive integer that doesn't divide $n!$. It is easy to see $p$ is the smallest prime greater than $n$. It is easy to see that both $p-1$ and $p+1$ are divisors of $n!$ Let $q$ be the smallest positive integer greater than $p$ that is 2 mod 6. We see that either $q=p+3$ or $q=p+1$ but $q$, $q+1$, $q+2$ must all be divisors of $n!$ giving a difference of 1 after a difference of 2. Therefore, all $n>6$ fail. ~mathophobia

Solution 2

We claim only $n = 3$ and $n = 4$ are the only two solutions. First, it is clear that both solutions work.

Next, we claim that $n < 5$. For $n \geq 5$, let $x$ be the smallest $x$ such that $x+1$ is not a factor of $n!$. Let the smallest factor larger than $x$ be $x+k$.

Now we consider $\frac{n!}{x-1}$, $\frac{n!}{x}$ and $\frac{n!}{x+k}$. Since $\frac{n!}{x-1} > \frac{n!}{x} > \frac{n!}{x+k}$, if $n$ were to satisfy the conditions, then $\frac{n!}{x-1}-\frac{n!}{x} \geq \frac{n!}{x} - \frac{n!}{x+k}$. However, note that this is not true for $x \geq 5$ and $k > 1$.

Note that the inequality is equivalent to showing $\frac{1}{x(x-1)} \geq \frac{k}{x(x+k)}$, which simplifies to $x+k \geq kx-k$, or $\frac{x}{x-2} \geq k \geq 2$. This implies $x \geq 2x-4$, $x \leq 4$, a contradiction, since the set of numbers $\{1, 2, 3, 4, 5\}$ are all factors of $n!$, and the value of $x$ must exist. Hence, no solutions for $n \geq 5$.

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2024_USAMO_Problems/Problem_1&oldid=223741"