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"

(→‎Solution (Explanation of Video))
(→‎Solution 3)
 
(3 intermediate revisions by 2 users not shown)
Line 4: Line 4:
 
</cmath>
 
</cmath>
  
−
==Solution (Explanation of Video)==
+
==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>.
 
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>.
Line 30: Line 30:
  
 
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>.
 
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>.
 +
 +
==Solution 3==
 +
 +
We claim only <math>n = 3</math> and <math>n = 4</math> are solutions. First, it is clear that both solutions work.
 +
 +
For <math>n = 3</math>, the divisors of <math>3! = 6</math> are <math>1, 2, 3, 6</math> with differences <math>1, 1, 3</math>, which is non-decreasing.
 +
 +
For <math>n = 4</math>, the divisors of <math>4! = 24</math> are <math>1, 2, 3, 4, 6, 8, 12, 24</math> with differences <math>1, 1, 1, 2, 2, 4, 12</math>, which is non-decreasing.
 +
 +
For <math>n \geq 5</math>, we prove the condition fails by examining specific triples of consecutive divisors in <math>n!</math>. Consider <math>n = 5</math>. Among the divisors of <math>5! = 120</math> are <math>12 = 2^2 \times 3</math>, <math>15 = 3 \times 5</math>, and <math>20 = 2^2 \times 5</math>. These are consecutive divisors with no integers between them that divide <math>5!</math>.
 +
 +
The differences between these consecutive divisors are <math>15 - 12 = 3</math> and <math>20 - 15 = 5</math>. Continuing, the next divisor is <math>24 = 2^3 \times 3</math> with a difference of <math>24 - 20 = 4</math>.
 +
 +
Since <math>5 > 4</math>, the sequence of differences is not non-decreasing for <math>n = 5</math>.
 +
 +
For any <math>n \geq 6</math>, we still have these same divisors in <math>n!</math> with the same problematic pattern of differences.
 +
 +
Note that this issue stems from how integers with different prime factorizations create irregular gaps between consecutive divisors. When we have multiple distinct primes <math>(2, 3, 5)</math> contributing to <math>n!</math>, the spacing between consecutive divisors cannot maintain a non-decreasing pattern.
 +
 +
Therefore, <math>n = 3</math> and <math>n = 4</math> are the only solutions.
 +
 +
~ brandonyee
  
 
==Video Solution==
 
==Video Solution==

Latest revision as of 00:08, 7 March 2025

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$.

Solution 3

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

For $n = 3$, the divisors of $3! = 6$ are $1, 2, 3, 6$ with differences $1, 1, 3$, which is non-decreasing.

For $n = 4$, the divisors of $4! = 24$ are $1, 2, 3, 4, 6, 8, 12, 24$ with differences $1, 1, 1, 2, 2, 4, 12$, which is non-decreasing.

For $n \geq 5$, we prove the condition fails by examining specific triples of consecutive divisors in $n!$. Consider $n = 5$. Among the divisors of $5! = 120$ are $12 = 2^2 \times 3$, $15 = 3 \times 5$, and $20 = 2^2 \times 5$. These are consecutive divisors with no integers between them that divide $5!$.

The differences between these consecutive divisors are $15 - 12 = 3$ and $20 - 15 = 5$. Continuing, the next divisor is $24 = 2^3 \times 3$ with a difference of $24 - 20 = 4$.

Since $5 > 4$, the sequence of differences is not non-decreasing for $n = 5$.

For any $n \geq 6$, we still have these same divisors in $n!$ with the same problematic pattern of differences.

Note that this issue stems from how integers with different prime factorizations create irregular gaps between consecutive divisors. When we have multiple distinct primes $(2, 3, 5)$ contributing to $n!$, the spacing between consecutive divisors cannot maintain a non-decreasing pattern.

Therefore, $n = 3$ and $n = 4$ are the only solutions.

~ brandonyee

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=244453"