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 < \dots < d_k = n!$, then we have \[ d_2 - d_1 \leq d_3 - d_2 \leq \dots \leq d_k - d_{k-1}. \] Proposed by Luke Robitaille.
Problem
Source: 2024 USAMO Problem 1
Tags: USAMO, number theory
20.03.2024 07:03
Solved with SOCOURGE. We can check manually that $n < 5$ works, and that $n = 5$ doesnt. Now, consider $n > 6$ and the interval $I = [n, 2n]$. This interval contains at least $3$ odd numbers. FTSOC suppose that $n!$ works. Call a pair $(k, k+1)$ killing if they are both composite. Then any prime $p > n$ in $I$ must come after a killing pair. Now, consider $2n - 1, 2n + 1, 2n + 3$. If $k = 2n - 1, 2n + 1$ are composite, Bertrand's gives us a prime before $k$, and $k \mid n!$. As such, they must both be prime. Then $2n + 3$ must composite by taking $\pmod{3}$. If $2n + 2$ is composite as well we get our killing pair. Else, $n + 1$ must be prime. However, since $n + 1$ is in the interval, it follows that one of $n + 3, n + 5$ is composite giving us a killing pair.
20.03.2024 07:08
Let $k$ be the smallest integer such that $k$ does not divide $n!$. Let $m$ be the smallest integer greater than $k$ such that $m|n!$. Obviously $k-2, k-1, m$ are consecutive divisors of $n!$. Thus, it follows $\tfrac{n!}{m}, \tfrac{n!}{k-1}, \tfrac{n!}{k-2}$ are consecutive divisors of $n!$. The main claim is as follows: Claim: For all $n>5,$ we have $\tfrac{n!}{k-2}-\tfrac{n!}{k-1}<\tfrac{n!}{k-1}-\tfrac{n!}{m}.$ Proof. Factor out $n!$ to obtain $\tfrac{1}{k-2}-\tfrac{1}{k-1}<\tfrac{1}{k-1}-\tfrac{1}{m},$ but $m \ge k+1$ by definition, so it suffices to prove \[\frac{1}{k-2}-\frac{1}{k-1}<\frac{1}{k-1}-\frac{1}{k+1}.\]But this is just \[\frac{1}{(k-2)(k-1)}<\frac{2}{(k-1)(k+1)} \implies (k-1)(k+1)<2(k-2)(k-1) \implies k>5.\]But $k>5$ holds for all $n>5,$ so it suffices to check $n \le 5,$ which gives us $n=3,4.$
20.03.2024 07:20
Note that: $n=3$ and $n=4$ satisfies this inequality (proof omitted) $n=5$ does not satisfy this inequality, because $24-20<20-15$ $n=6$ does not satisfy this inequality, because $9-8<8-6$ $n=7,8,9$ does not satisfy this inequality, because $15-14<12-10$ Now, assume that $10\le n\le 22$. Note that $n!$ is a multiple of $25$ and $24$, but not $23$. Let $d$ be $n!$'s largest divisor under $24$; we are guaranteed that $25-24<24-d$ since $d\neq 23$, which is bad. Now, assume that $23\le n\le 108$. Note that $n!$ is a multiple of $121$, $120$ and $110$, but not $109$. Let $d$ be $n!$'s largest divisor under $109$; we are guaranteed that $121-120<110-d$ since $d\neq 109$, which is bad. Now, assume that $n\ge 109$. Let $p$ be the greatest prime divisor of $n$ under $\frac{n}{2}$. Bertrand guarantees that $p\ge \frac{n-3}{4}$. $p^2$ is a factor of $n!$ since $p$ and $2p$ are under $n$, and so is $p^2-1$ since $p-1$ and $p+1$ are under $n$. However, $$\left(\frac{n-3}{4}\right)^2>2(n+1)$$which means that there exists a prime $q$ strictly between $n$ and $p^2$ by Bertrand. Let $a$ be the smallest divisor of $n!$ greater than $q$, which must be less than or equal to $p^2$, and let $b$ be the largest divisor of $n$ less than or equal to $q$. Since $q\nmid n!$, we are guaranteed that $a-b$ is one of the differences in the problem statement, but $a-b\ge 2>p^2-(p^2-1)$, which is bad. Having exhausted all cases, $\boxed{n=3,4}$ are the only answers. @2below nice solution, i feel pretty silly now
20.03.2024 07:27
thank you maa for giving us an easy prob so we dont feel stupid
20.03.2024 07:28
I used Bertrand too: let $x$ be the largest even number less than $n$; then, $x^2$ and $x^2-1$ both divide $n!$, so every integer from $1$ thru $x^2$ must be a divisor of $n!$. But when $n \geq 6$, Bertrand's tells us there is a prime in the range $[n+1, x^2]$, so there are no solutions for $n \geq 6$.
20.03.2024 07:31
$n=3,4$ work. We claim that $n\geq 5$ does not. Take the minimal $i$ such that $d_{i}-d_{i-1}=1$ but $d_{i+1}-d_{i}>1$; such an $i$ must exist by Bertrand, for instance. Then, $\frac{n!}{d_{i+1}},\frac{n!}{d_{i}},\frac{n!}{d_{i-1}}$ are $d_{j-1},d_{j},d_{j+1}$ in order for some $j$, giving: $$\frac{d_{j}-d_{j-1}}{d_{j+1}-d_{j}} = \frac{d_{i-1}}{d_{i+1}}\frac{d_{i+1}-d_{i}}{d_{i}-d_{i-1}}=(d_{i}-1)(1-\frac{d_{i}}{d_{i+1}})$$Because $d_{i+1}\geq d_{i}+2$: $$\geq \frac{2(d_{i}-1)}{d_{i}+2} > 1$$Because $d_{i}\geq 6$ for $n\geq 5$. Thus, $n$ does not work.
20.03.2024 08:09
Can we use bertrand’s without proving it?
20.03.2024 14:47
Ambivalence wrote: Can we use bertrand’s without proving it? Yes Let $p<2n$ be the smallest prime greater than $p$. Now, $\frac{n(n-3)}2+1=\frac{(n-1)(n-2)}2$, contradiction for $n\geq7$.
20.03.2024 14:52
Ambivalence wrote: Can we use bertrand’s without proving it? Yes Let $p<2n$ be the smallest prime greater than $p$. Now, $\frac{n(n-3)}2+1=\frac{(n-1)(n-2)}2$, contradiction for $n\geq7$.
20.03.2024 15:36
Select the minimum prime p>n, construct $p+1, p-1, p-2$ when $p>4$
20.03.2024 15:37
Solution
20.03.2024 16:35
Only slightly harder than 2023 IMO 1 (which also looks very similar to this problem)
20.03.2024 17:42
ihatemath123 wrote: 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 < \dots < d_k = n!$, then we have \[ d_2 - d_1 \leq d_3 - d_2 \leq \dots \leq d_k - d_{k-1}. \] Proposed by Luke Robitaille. For $n>=8$ we now that there exist a prime between $(n,2n-3)$ for thiw we can get that $2n-3,2n-1,2n+1$ are all primes contradiction $mod3$ Cheking for $n<=7$ we get that only $n=3,4$ works. brainfertilzer wrote: Only slightly harder than 2023 IMO 1 (which also looks very similar to this problem) I thing that is slightly easier than 2023 IMO 1
20.03.2024 17:45
thiis problem is very easy Answer is $n=3,4$. Proof is trivial (I just listed out the factors and said "it works") Note that if consecutive factors of $n!$ are $m-1, m, m+k$ for $k>1$ and $m>4$, $\frac{n!}{m+k}, \frac{n!}{m}, \frac{n!}{m-1}$ are consecutive factors satisfying: $$\frac{n!}{m-1}-\frac{n!}{m}<\frac{n!}{m}-\frac{n!}{m+k}$$ I now present 2 strategies for proving such $m$ and $k$ exist: Strategy 1: no Bertrand's. To show that such $m$ exists for $n\geq 5$, AFSOC it does not. Thus as $1,2,3,4,5$ are factors of $n!$ all factors must then be consecutive, thus all integers from $1$ to $n!$ are factors of $n!$. This is clearly absurd. Contradiction. Strategy 2: Bertrand's. There exists some prime $n\leq P\leq 2n\leq n!$. P does not divide $n!$, but there must also obviously exist some factor of $n!$ greater than $P$, thus not all factors of $n!$ are consecutive. Thus, there exists some $m$ such that $m,m-1$ are factors of $n!$ but $m+1$ is not. This problem was pretty easy, I would say MOHS 5-10
20.03.2024 17:58
Answer is n = 3, 4 manually verify n = 3, 4 work for n>=5, we let p_k<=n<p_{k+1}, for two consecutive primes p_k, p_{k+1} note that p_{k+1}-2, p_{k+1}-1, p_{k+1}+1 are divisors so a!/(those three) are divisors, which is contradiction for p_{k+1}>=5 since n>=5, we have p_{k+1}>=7, which proves contradiction for all n>=5
20.03.2024 18:09
The smallest prime $p\nmid n!$ satisfies $p\le 2n-1$. Consider pairs of potential divisors \[((n-1)^2,n(n-2))\]\[((n-2)^2,(n-1)(n-3)).\]Also take $n\ge 7$. Notice: \[n(n-2),(n-1)(n-3)\ge 2n-1\ge p\]and thus \[(n-1)^2\nmid n!\]\[(n-2)^2\nmid n!\]implying $n-1$ and $n-2$ are both prime, a contradiction. Now $n\in \{3,4,5,6\}$ is easy to check. Answer is $n\in \{3,4\}$.
20.03.2024 18:41
pinkpig wrote: Answer is n = 3, 4 manually verify n = 3, 4 work for n>=5, we let p_k<=n<p_{k+1}, for two consecutive primes p_k, p_{k+1} note that p_{k+1}-2, p_{k+1}-1, p_{k+1}+1 are divisors so a!/(those three) are divisors, which is contradiction for p_{k+1}>=5 since n>=5, we have p_{k+1}>=7, which proves contradiction for all n>=5 I think some more work needs to be done to show exactly why $p_{k+1}+1$ is divisor (not a power of two) along with some work to show that the smallest nondivisor has to be prime.
20.03.2024 19:10
Nice problem! I will analyze case $n>5$. Let $k$ be minimal natural number such a $k+2 \not | n!$. Clearly, $k>3$ and $k<n!-2$. Then for some $t>1$ we have $d_t=\frac{n!}{k+1}, d_{t+1}=\frac{n!}{k}$ and $d_{t-1} \leq \frac{n!}{k+3}$, so $d_t-d_{t-1}>d_{t+1}-d_t$, because $\frac{1}{k}-\frac{1}{k+1}<\frac{1}{k+1}-\frac{1}{k+3}$ for $k>3$. By this reason $n>5$ don't works.
20.03.2024 21:05
Here is a weird solution using bertrand postulate. $\newline$ For $n\ge 9$ let $p$ prime minimum such that $p>n$. By bertrand we can ensure that $p<2n$. $\newline$ Claim: There exist $x>p$ such that $x,x+1$ both divide $n!$ $\newline$ Proof: Let $x$ minimum greater than $p$ such that $x\equiv 8(mod 12)$. Then $x\leq p+9$ and since $x=\frac{x}{4}\cdot 4$ and $x\leq p+9 \leq 2n+8 \leq 4n$ clearly $x$ divides $n!$. $\newline$ On the other hand $x+1=\frac{x+1}{3} \cdot 3$ and $x+1\leq 2n+9 \leq 3n$ we are again done $\newline$ Now the problem is solved: since $p>n$, $p$ doesn't divide $n!$ and take s,l the divisors that are right before $p$ and after $p$ we have $l-s\geq 2$, but $x$ and $x+1$ are consectutive after $l$ and $s$ because $x>p$ and their difference is $1$,false !
20.03.2024 21:53
22.03.2024 16:17
We claim the answer is $n = 3$ and $n = 4$. First, we show that $n = 3$ and $n = 4$ work. We have the divisors of $3! = 6$ are $1,2,3,6$ in that order, hence the consecutive differences are $1,1,3$, which is nondecreasing, so $n =3$ works. For $n = 4$, $4! = 24$,. Similarly, the divisors of $24$ in that order are $1,2,3,4,6,8,12,24$, and the consecutive differences are $1,1,1,2,2,4,12$, which is nondecreasing, so $n =4 $ also works. Now we show that $n > 4$ does not work. We define consecutive divisors of $n!$ to be $d_i$ and $d_{i+1}$ for $1 \le i \le k - 1$. The difference between $d_i$ and $d_{i+ 1} $ must be nondecreasing from $1 \le i \le k - 1$ for $n$ to work. Claim: $n = 5$ does not work Proof. Suppose otherwise. Notice that $15,20,24$ divide $5! = 120$, but $16,17,18,19,21,22,23$ do not divide $5! = 120$. Hence if $d_i = 15$ for some $ 1 \le i \le k - 1$, (must exist as $15 \mid 120$), then $d_{i + 1} = 20$ and $d_{i + 2} = 24$. But we have $d_{i + 2} - d_{i + 1} = 4$ and $d_{i+1} - d_i = 5$, contradiction since $4 < 5$. Hence $n = 5$ fails. $\square$ Now assume $n > 5$. Let $p$ be the smallest prime over $n$ (greater than $n$). By Bertrand's Postulate, there is at least one prime in $[n+1, 2n + 2]$, so $p \le 2n + 2$. Since $2n + 2 > 2$ is even, it cannot be prime, so $p < 2n + 2$. Claim: $p + 3$ divides $n!$ Proof: Suppose otherwise. Since $p > n > 2$, $p + 3$ is even. Case 1: $p + 3 \le 2n$ Then note that $2$ and $\frac{p+3}{2}$ are distinct positive integers less than or equal to $n$ (since $\frac{(p+3)}{2} $ cannot equal $2$), so $2 \left( \frac{n+3}{2} \right)$ divides $1\cdot 2\cdot 3 \ldots \cdot n = n!$, hence $p + 3 \mid n!$, absurd. Case 2: $p + 3 > 2n$. Let $m$ be the largest divisor of $p + 3$ that is less than or equal to $4n$. Note $m \ge 2$ as $2 \mid p + 3$. If $m = 2$, then all divisors of $p + 3$ that aren't $1$ or $2$ are greater than $n$. But then $\frac{p+3}{3} < \frac{(2n+2) + 3}{3} < n $ for $n > 5 $, so the divisors of $p + 3$ must be $1, 2, \frac{p+3}{2}, p + 3$. Since no divisors of $p + 3$ are strictly between $2$ and $\frac{p+3}{2}$, Either $1$ or $2$ must be the largest proper divisor of $\frac{p+3}{2}$. Since $\frac{p+3}{2} $ is odd (otherwise we could take $m = 4$), $\frac{p+3}{2}$ must be prime. But, $n < \frac{p+3}{2} < p$, so this is a contradiction to the minimality of $p$. Hence $m \ne 2$, so $m > 2$. But then if $m^2 \ne p + 3$, we have that $m$ and $\frac{p+3}{m}$ are distinct positive integers $\le n$ (since $\frac{p+3}{m} \le \frac{p+3}{3} < \frac{2n + 5}{3} < n$ ). So $m \cdot \frac{p+3}{m} = p + 3$ must divide $n!$, absurd. Hence $m^2 = p + 3$. If $m \le \frac n2 $, then $m$ and $2m$ are less than or equal to $n$ and distinct, so $2m^2$ divides $n!$, meaning that $p + 3 \mid 2m^2 \mid n!$, absurd. Hence $m > \frac{n}{2} $. But then $m^2 > \frac{n^2}{4}$, so $\frac{n^2}{4} < p + 3 < 2n + 5$, meaning that $n^2 < 8n + 20$, so $(n-4)^2 < 36$, so $n < 10$. If $n = 6$, then $p = 7$, $p + 3 = 10$, which divides $6!$. If $n = 7,8,9$, then $p + 3 = 14$, which divides $7!, 8!, 9!$, absurd. Hence $p + 3$ must divide $n!$. Since $p > n >3$, $p\equiv \{1,2 \} \pmod 3$. Let $x$ be the largest divisor of $n!$ less than $p$ and $y$ be the smallest divisor of $n!$ greater than $p$. Clearly $x,y$ are consecutive divisors with difference greater than $1$. Case 1: $p\equiv 1\pmod 3$. Claim: $p + 2 \mid n!$. Proof: This is obvious when $n = 6$ since $9 \mid 6!$. Assume $n > 6$, so $p > 7$. Now, $3 \mid p + 2$ and $\frac{p+2}{3} < \frac{2n + 4}{3} < n$, so $3$ and $\frac{p+2}{3}$ are distinct positive integers $ \le n$, so $3 \cdot \frac{p+2}{3} =p + 2 \mid n!$. Now note that $p + 2, p + 3$ are consecutive divisors of $n!$ and $p + 2 >x $ and $p + 3 > y$, so $(p + 3) - (p + 2) $ must be at least $y - x > 1$, absurd since $(p + 3) - (p + 2) = 1$. Case 2: $p \equiv 2\pmod 3$. Claim: $p+4 \mid n!$ Proof: Since $n \ge 6$ and $7 \not \equiv 2\pmod 3$, $p > 7$. We have $3\mid p + 4$ and $\frac{p+4}{3} < \frac{2n + 6}{3} \le n$, so $3$ and $\frac{p+4}{3}$ are distinct positive integers $\le n$ (since $\frac{p+4}{3} > \frac{7+4}{3} > 3$). Hence $3 \cdot \frac{p+4}{3} = p + 4$ divides $ n!$. $\square$ Now, note that $p + 3$ and $p + 4$ are consecutive divisors of $n!$ and $p + 3 > x, p + 4 > y$, so $(p+4) - (p+3) $ must be at least $y - x > 1$, absurd since $(p + 4) - (p + 3) = 1$. We have exhausted all cases, so $n > 5$ all fails. $\square$ Hence $n = 3,4 $ are the only solutions.
22.03.2024 17:44
tfw you got it right but forgot the name of bertrands postulate so you used some bs prime between (n,n^2) thing and now you probably only get 1 point despite everything else being right
24.03.2024 10:13
The answer is $\boxed{n=3\text{ and }n=4}$. Indeed, they both work because we have\[2-1=3-2=4-3<6,\ \text{ and}\]\[2-1=3-2=4-3<6-4=8-6<12-8<24-12.\] We will show that $n\geq5$ does not work. Take an index $m$ such that $d_m+1=d_{m+1}$ and $d_{m+1}+1<d_{m+2}$. This obviously exists, because the first few divisors of $n!$ are consecutive integers, but not all naturals less than $n!$ are factors. Now, using the fact that $d_i\times d_{k+1-i}=n!$ for $i=1,2,\ldots, k$, and that $d_m>4$ for $n\geq5$, we obtain\begin{align*} d_{k-m}-d_{k-m-1}=\frac{n!}{d_{m+1}}-\frac{n!}{d_{m+2}}&\geq \frac{n!}{d_{m+1}}-\frac{n!}{d_{m+1}+2}\\&=n!\left(\frac2{d_{m+1}^2+2d_{m+1}}\right)\\&>n!\times\left(\frac2{d_{m+1}^2+2d_{m+1}}\right)\times\frac12\times\frac{d_{m+1}+2}{d_{m+1}-1}\\&=n!\times\left(\frac1{d_{m+1}^2-d_{m+1}}\right)\\&=\frac{n!}{d_{m+1}-1}-\frac{n!}{d_{m+1}}\\&=d_{k-m+1}-d_{k-m}, \end{align*}which violates the problem requirement.
25.03.2024 02:19
oops. The answer is $n=3$ and $n=4$, which clearly work. $n=5$ does not work because $15,20,24$. $n=6$ does not work because 7 does not divide $6!$ but $8\mid 6!$ and $9\mid 6!$. $n=7,8,9,10$ does not work because $11\nmid n!$ but $14\mid n!$ and $15\mid n!$. From now on, assume $n\geq 11$. Let $p$ be the smallest prime larger than $n$. By Bertrand's postulate, $p\leq 2n+1$. Note that either $p+2$ or $p+4$ is divisible by $3$, and either $p+3$ is divisible by $4$ or $p+1$ and $p+5$ both are. Thus, there exist a multiple of 3 and a multiple of 4 that are consecutive and both greater than $p$ and at most $p+5$. Note that $$\frac{p+5}{3}\leq \frac{2n+1+5}{3}\leq n$$and of course $$\frac{p+5}{4}\leq n$$as well. Thus, the "multiple of 3 and multiple of 4 consecutive" are both expressible as a product of two positive integers at most $n$, as $\frac{p+5}{3}\leq n$, one of which is 3 or 4. If the other one is 3 or 4, then since $9\mid n!$ and $16\mid n!$, we have two consecutive divisors of $n$ greater than $p$. Otherwise, they are a product of two distinct positive integers at most $n$, which obviously divides $n!$. Thus, $n!$ has two consecutive divisors greater than $p$, and we are done.
26.03.2024 05:05
Looks similar to a Chinese IMO TST problem. . Their source of question was a 16 page paper on the number of divisors of n! by Erdos,C Pomerance,S W Graham,A Ivic
30.03.2024 15:26
We can see that it's satisfied for $3, 4$ and doesn't work for $5, 6, 7, 8, 9, 10, \dots$. We claim it doesn't work for all $n \geq 5$, say it doesn't hold for $\{5, 6, \dots, n - 1\}$. We will now show that it doesn't work for $n$ as well. By Bertrand's, we know there exists a prime $p$ greater than $n$ such that $n < p \leq 2n - 3$. Clearly $\frac{p - 1}{2} \leq \frac{2n - 4}{2} = n - 2$, which means $p - 1 \mid n!$. Since $p$ is a prime greater than $n$, $p \nmid n!$, while $\frac{p + 1}{2} \leq \frac{2n - 2}{2} = n - 1$, which means $p + 1 \mid n!$. If $p + 2 \mid n!$, then we are done, which means $p + 2 \neq 0\mod{3} \implies p \equiv 2\mod{3}$. $\frac{p + 3}{2} \leq$, so $p + 3 \mid n!$. Clearly, $3 \mid p + 4$, and $\frac{p + 4}{3} \leq n$, so $p + 4 \mid n!$, which means the condition is broken, so we are done.
07.04.2024 15:10
Too many Bertrand solutions Check that $n=3,4$ work. Now consider the smallest integer $x$ such that $x\nmid n!$, clearly as $5!\mid n!$ we get $x\geq 7$. Then we have that $d_i,d_{i+1},d_{i+2}$ are $x-2,x-1,x+m$ for some $i$ and $m\geq 1$. This implies $d_{k+1-i},d_{k-i},d_{k-1-i}$ are $\frac{n!}{x-2},\frac{n!}{x-1},\frac{n!}{x+m}$. Writing down the inequality for these numbers and dividing out $n!$ gives: $$\frac{1}{x-2}-\frac{1}{x-1}\geq\frac{1}{x-1}-\frac{1}{x+m}\geq\frac{1}{x-1}-\frac{1}{x+1}.$$However, by expanding out we get a contradiction for $x>5$, thus no integer $n\geq5$ satisfies the problem condition.
09.04.2024 00:50
The answer is $n \in \{3,4\}$. These can be checked by listing all the divisors: For $n=3$ we have $(1,2,3,6)$. For $n=4$ we have $(1,2,3,4,6,8,12,24)$. We prove these are the only ones. The numbers $5 \le n \le 12$ all fail because: For $n = 5$ we have $20 - 15 > 24 - 20$. For $n = 6$ we have $18 - 15 > 20 - 18$. For $7 \le n \le 12$ we have because $14-12 > 15-14$ (and $13 \nmid n!$). Now assume $n \ge 13$. In that case, we have \[ \left\lfloor \frac n2 \right\rfloor^2 - 1 \ge 2n. \]So by Bertrand postulate, we can find a prime $p$ such that \[ n < p < \left\lfloor \frac n2 \right\rfloor^2 - 1. \]However, note that \[ \left\lfloor \frac n2 \right\rfloor^2 - 1 = \left( \left\lfloor \frac n2 \right\rfloor - 1 \right) \left( \left\lfloor \frac n2 \right\rfloor + 1 \right), \qquad \left\lfloor \frac n2 \right\rfloor^2 \]are consecutive integers both dividing $n!$ (the latter number divides $\left\lfloor \frac n2 \right\rfloor \cdot \left( 2 \left\lfloor \frac n2 \right\rfloor \right)$). So the prime $p$ causes the desired contradiction.
11.04.2024 04:26
the divisors of $3!$ are $\{1,2,3,6\}$ and the divisors of $4!$ are $\{1,2,3,4,6,8,12,24\}$, so both $n=3$ and $n=4$ work $n=5$ does not work as $15,20,24|5!$ and $16,\dots,19,21,\dots,23\not|5!$ $n=6$ does not work as $6,8,9|6!$ and $7\not|6!$ $n=7,\dots,12$ does not work as $12,14,15|n!$ and $13\not|n!$ $n=13,\dots,18$ does not work as $18,20,21|n!$ and $19\not|n!$ $n=19,\dots,22$ does not work as $22,24,25|n!$ and $23\not|n!$ $n=23,\dots,30$ does not work as $30,32,33|n!$ and $31\not|n!$. by engineer's induction we're done I'll edit in construction later
20.04.2024 12:49
I feel pretty dumb seeing these solutions, but nonetheless, here's my approach: Let $p$ be the smallest prime larger than $n$. This means that the $d_i - d_{i-1}$ is now at least $2$. I want to prove that there exist two consecutive divisors larger than $p$ for all $n$ after some point. Notice that there must be an odd number divisible by $15$ between $p$ and $p+30$. Now, this number $j = 3 \times 5 \times r$, and it's clear that if $r < p$ then $j \mid n!$. As for $j+1 = 2 \times q$, if $q < p$ then we are done and $n$ isn't a solution. So we just need to consider $n$ where $2p < 2q \leq p+30 \Leftrightarrow p < 30$. Thanks to @above for checking said cases. We get $n=3 ,4$ only solutions.
21.04.2024 01:10
Springles wrote: Thanks to @above for checking said cases. We get $n=3 ,4$ only solutions. glad i could help
26.04.2024 07:27
10.05.2024 21:37
We uploaded our solution https://calimath.org/pdf/USAMO2024-1.pdf on youtube https://youtu.be/SpCOVwNKazY.
28.05.2024 09:23
Test the first $5$ values of $n$ to get that $n=3,4$ work, but $n=5$ to $n=16$ do not work. $n=5$ does not work because $20-15 > 24-20$, $n=6$ does not work because $8-6 > 16-15$. $n=7$ does not work because $12-10 > 16-15$. $n=8,9,...,16$ do not work because $18-16 > 64-63$. Let $p$ be the first positive integer that does not divide $n!$. Claim: $p$ is prime Proof: All primes greater than $n$ do not divide $n!$. There must be a prime between $n+1$ and $2(n+1)-2=2n$. So $n<p<2n$. Let $p=ab$, where $a,b \neq 1$. Note that $a,b < n$, since then, $p$ would either be too small or too big. Case 1: $a \neq b$. Because they are less than $n$, $a$ and $b$ are each found in the product from $n$ to $1$, which is $n!$. So $p=ab$ divides $n!$ for $a \neq b$. Case 2: $a=b$. This means that $p=a^2$ and $a=\sqrt{p}<\frac{p}{4}<\frac{2n}{4}<\frac{n}{2}$. So the product from $n$ to $1$ includes at least $2$ multiples of $a$, so $p=a^2$ divides $n!$ for $a=b$. As a result, $p$ has to be prime. This can be extended to get that all the composite numbers between $n$ and $2n$ divide $n!$. Note that $p+1$ divides $n!$, since it is less than or equal to $2n$ and is even, so it is composite. If it is equal to $2n$, then get that the product from $n$ to $1$ includes $n$ and $2$, so it divides $n!$. Otherwise, use the proof above to get that it divides $n!$. Also, $p-1$ works and $p$ does not work by definition. Out of $2p-1$ and $2p+1$, one of them divides $3$, since $2p-1, 2p$, and $2p+1$ are consecutive integers, so one of them divides $3$, but $2p$ cannot divide $3$ since $2$ and $p$ do not divide $3$, so one of $2p-1$ and $2p+1$ divides $3$. That number divided by $3$ is $\frac{2p}{3} \pm \frac{1}{3} < \frac{2p+1}{3} < \frac{4n+1}{3} < 2n$. So by the proof above, that number divided by $3$ divides $n!$. However, $2p \pm 1 < 4n+1 < 3^{\lfloor \frac{n}{3} \rfloor} < 3^{\lfloor \frac{n}{3} \rfloor+\lfloor \frac{n}{9} \rfloor+...}$. This is because this works at $n=16$, and after that, as $n$ increases by $3$, the RHS function gets multiplied by $3$, which is more than the LHS function getting added by $12$ since the RHS will remain more than $4$. So one of $2p-1$ and $2p+1$ divide $n!$, since there are not enough $3$s in their prime factorization to have more powers of $3$s than $n!$. WLOG $2p+1$ divs $3$. Then, note that $2p+2=2(p+1)$. Because $2$ works and $p+1$ works, $2(p+1)$ also works. Use similar logic as the previous part to get that $2p+2$ is too small to have more powers of $2$ than $n!$. So $2p+1$ and $2p+2$ both work. If $2p-1$ worked instead, then $2p-2$ would also work. Because $(p+1)-(p-1) > (2p+2)-(2p+1)$, no other $n$ work.
08.06.2024 06:17
We can see that $n=3$ and $n=4$ work, but $n=5$ doesn't. For $n \geq 6$, we use Bertrand's Postulate, which says that at least one prime exists in the range $(n, 2n-2)$. Let $p$ be the largest such prime. Clearly, $p$ is odd, so $p+1$ must divide $n!$. Since $p$ is the largest prime in $(n, 2n-2)$, unless $p = 2n-3$, $p+2$ is also composite and divides $n!$. If $p = 2n-3$, then consider $2n-1$ and $2n+1$. Using $mod 3$, all three of $2n-3, 2n-1, 2n+1$ cannot be prime. Also, $2n \vert n!$, so either $(2n-1, 2n)$ or $(2n, 2n+1)$ are 2 consecutive factors of $n!$, proving $n \geq 6$ doesn't work.
27.06.2024 16:25
The answer is $\boxed{n=3,4}$, which can be verified to work. Noticing that $n=1,2,5,6$ fail so assume that $7\leq n$. Let $k$ be the largest integer such that $2k<n$. Then $4k^2=2\cdot k\cdot 2k|n!$ and $4k^2-1=(2k-1)(2k+1)|n!$. Thus every integer in between $1$ and $4k^2$ must divide $n!$ but $2n<4k^2$, so we clearly have a contradiction by Bertrand's Postulate.
11.07.2024 21:28
We first claim that if $n > 3$, then any composite number in the interval $[n, 2n]$ divides $n!$. Such a composite number $k$ is clearly not divisible by any prime $> n$, and if it is the power of a prime it is easy to verify that $\nu_p(k) \leq \nu_p(n)$, so $k \mid n$. Now, FTSOC $n \geq 6$. Then the interval $[n, 2n]$ must contain at least $3$ odd consecutive numbers, so not all odd numbers in range $[n, 2n]$ are prime. Thus, there are two consecutive divisors of $n$ in $[n, 2n]$. By Bertrand's postulate we have that there is some prime number $p$ in range $[n, 2n - 2]$ that does not divide $n$. If the only prime $p$ is $p = 2n - 3$ then at least one of $2n - 1$ and $2n + 1$ is composite. Since $2n - 3$ is the only prime, we get an immediate contradiction since all composite numbers less than $2n$ divide $n!$. We can easily repeat this if $p \leq 2n - 3$, so $n \geq 6$ does not work. If $n = 5$ then we can manually check that this does not work, and we can check that $n = 3, 4$ works so we are done.
20.08.2024 01:51
Divisors of n! are [1, 2, ..., n, (some divisors/no divisors of n!) n!/n, n!/(n-1), ..., n!/1](if n≠3) We know that if n!/k - n!/(k+1) ≥ n!/(k+1) - n!/(k+3) then k ≤ 3. So if the lesser but maximum divisor of n!/k is n!/(k+1) then the lesser but maximum divisor of n!/(k+1) is n!/(k+2). So n - 1 is ≤ 3. I mean n ≤ 4. [Otherwise by repeating the process of assuming k from n!/(n-1) we can get the conclusion that divisors of n! are 1, 2, ..., n! If n ≥ 5 Which is not possible.] Only chances for n = 3, 4 and by verifying both n = 3, 4.(edited:sorry please understand my solution I don't know latex)
01.10.2024 15:25
Assume that for $n\ge 10$, there exists such $n$. There exists a prime number between $n$ and $2n$, implying that there cannot be consecutive divisors after $2n$. Consider the numbers $x(x+2)$ and $(x+1)^2$. Choose $x \in \{ \lfloor \sqrt{2n} \rfloor +1, \lfloor \sqrt{2n} \rfloor+2, \lfloor \sqrt{2n} \rfloor+3\}$ such that $3|x+1$. It is true that $x,x+2 \le n \implies x(x+2)|n!$; $9, \frac{(x+1)^2}{9} \le n \implies (x+1)^2|n!$ for $x \neq 8$ but it is true also for $x=8$. Additionally, $x(x+2) \ge 2n$. Thus consecutive numbers $x(x+2)$ and $(x+1)^2$ divide $n!$ which gives a contradiction. Now you need to check for $n \le 9$.
05.11.2024 18:25
Solved with stillwater_45. More painful 23IMO1 memories, though this one was appreciably harder than that. Still, its the exact same idea. We claim that the only solutions are $n=3$ and $n=4$ which can quite easily be verified, by simply listing out all the divisors. Say there exists some $n\ge 5$ for which the conditions holds. Consider the largest $i$ for which $d_{i}=i$. It is fairly clear due to size reasons ($\sqrt{n}>\frac{\tau(n)}{2}$) that $i<\frac{\tau(n)}{2}$. Thus, $d_{i-1}=i-1$ , $d_i=i$ and $d_{i+1}>i+1$ are consecutive divisors of $n!$ while so are $\frac{n!}{d_{i-1}} > \frac{n!}{d_i} > \frac{n!}{d_{i+1}}$ (which are all distinct from $d_{i-1},d_i,d_{i+1}$). But then, \begin{align*} \frac{n!}{d_{i-1}} - \frac{n!}{d_i} &\ge \frac{n!}{d_i} - \frac{n!}{d_{i+1}} \\ \frac{1}{i-1} - \frac{1}{i} &\ge \frac{1}{i} - \frac{1}{d_{i+1}}\\ \frac{1}{d_{i+1}} & \ge \frac{2}{i} - \frac{1}{i-1}\\ d_{i+1} & \le \frac{i(i-1)}{i-2} < i+2 \end{align*}since $i>4$ for all $n\ge 5 $ (the first $n$ divisors of $n!$ are $1,2,\dots , n$ anyways). But this is a clear contradiction since $i+1 < d_{i+1}<i+2$, so the condition cannot hold for any $n\ge 5$ and we are done.