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"
Line 10: Line 10:
 
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.
 
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</math> greater than or equal to <math>7</math>.
+
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%.
  
−
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</math> greater than or equal to <math>8</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>.
+
Therefore, the only numbers that work are </math>n=3<math> and </math>n=4$.
  
 
~alexanderruan
 
~alexanderruan

Revision as of 23:31, 11 April 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)

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$ (Error compiling LaTeX. Unknown error_msg)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$ (Error compiling LaTeX. Unknown error_msg)n=3$and$n=4$.

~alexanderruan

Video Solution

https://youtu.be/ZcdBpaLC5p0 [video contains problem 1 and problem 4]

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