Find the smallest $\lambda \in \mathbb{R}$ such that for all $n \in \mathbb{N}_+$, there exists $x_1, x_2, \ldots, x_n$ satisfying $n = x_1 x_2 \ldots x_{2023}$, where $x_i$ is either a prime or a positive integer not exceeding $n^\lambda$ for all $i \in \left\{ 1,2, \ldots, 2023 \right\}$. Proposed by Yinghua Ai
Problem
Source: China MO 2024, Day 1, Problem 1
Tags: number theory
28.11.2023 09:29
应该是 $\frac{1}{1012}$ 直接归纳就行了 唉我同字母用了两次,恐怕今天只有 18+0+0=18 希望别铜
28.11.2023 10:08
The answer, for $2023$ replaced by $k$, is $\boxed{\lambda(k)=\frac{2}{k+1}}$. We prove this by induction on $k$. For $k=1$, clearly $\lambda(k)=1$ by taking $n$ to be any composite number. Now assume $\lambda(k-1)=\frac{2}{k}$ for some $k \geq 2$. We want to factorize $n$ into $k$ parts. If $n$ has a prime factor $p$ greater than $n^{\frac{1}{k+1}}$, then take $x_1=p$, and the rest is at most $n^{\frac{k}{k+1}}$, so by induction hypothesis we can choose $x_2,x_3, \dots , x_k$ appropriately. Now assume every prime factor of $n$ is less than $n^{\frac{1}{k+1}}$. Let the prime factors be $p_1 \leq p_2 \leq \cdots$. Let $l$ be the largest positive integer such that $p_1p_2 \cdots p_l \leq n^{\frac{2}{k+1}}$. Then $p_1p_2 \cdots p_l > n^{\frac{1}{k+1}}$: else $p_1\cdots p_lp_{l+1} \leq n^{\frac{1}{k+1}}p_{l+1} \leq n^{\frac{2}{k+1}}$, contradicting maximality of $l$. So, if we choose $x_1=p_1p_2 \cdots p_l$, then $\frac{n}{x_1}<n^{\frac{k}{k+1}}$, so we are again done by induction. Now we prove that this $\lambda(k)$ is tight. Assume some smaller $\lambda'<\frac{2}{k+1}$ worked. Choose $n=2^{k+1}$. Then the only prime factor of $n$ is $2$, and the only divisors of $n$ not exceeding $n^{\lambda'}<4$ are $1$ and $2$, so each $x_i$ is at most $2$. But then, $$2^{k+1}=x_1x_2\cdots x_k \leq 2^k$$Contradiction!
28.11.2023 23:38
28.11.2023 23:43
Looks like this is the actual thread The answer is $\lambda=\frac{1}{1012}$. For necessity, take $n$ to be the product of $2024$ distinct primes in the range $[m^4,(m+1)^4]$ for some $m$ (possible since a prime exists in $[m^3,(m+1)^3]$ for all sufficiently large $m$). If we write $n=x_1\ldots x_{2023}$, at least one product must be the product of at least two primes, so it's at least $m^{4\cdot 2}$ while $n$ is at most $(n+1)^{4\cdot 2024}$. Sending $m \to \infty$ implies necessity. For sufficiency, set $\lambda=\frac{1}{1012}$ and take an arbitrary positive integer $n$. Take its representation $x_1\ldots x_{2023}$ such that the largest non-prime $x_i$ is minimal and suppose it equals $n^k$ and suppose $k>\frac{1}{1012}$. There must exist some prime divisor of $x_i$ that's at most $n^{k/2}$. Remove it (dividing out) from $x_i$ and attach it to the minimal $x_j$. Obviously $j \neq i$, so we have $\log_n(x_j)\leq \frac{1-k}{2022}$. But now $$\frac{1-k}{2022}+\frac{k}{2}<k \impliedby k>\frac{1}{1012},$$which is a contradiction. Remark: Not sure why I thought our $2024$ primes had to be different
22.12.2023 23:49
The answer can not be 1/1024. The problem states that for all n, the factors x_i are positive integers and can not exceed n^lambda. This makes n=13 one of many counter examples since 13^lambda is a very small number, just above 1. The only positive integer meeting this criteria is 1.
23.12.2023 01:01
ArcaniteCartel wrote: The answer can not be 1/1024. The problem states that for all n, the factors x_i are positive integers and can not exceed n^lambda. This makes n=13 one of many counter examples since 13^lambda is a very small number, between 0 and 1. There are no positive integers which satisfy that condition. $x_i$ is either any prime number, or some positive integer that doesn't exceed $n^\lambda$. If $x_i$ is a prime then there is no size restriction.
23.12.2023 04:20
Ah. I see what you are saying.
20.01.2024 17:57
Compared to recent CMO problem 1, I think this problem is slightly easier since there is a rather natural way to motivate oneself to reach the solution. Did a video explanation of the solution: https://youtu.be/3mFMzLh59fU
20.01.2024 18:12
renrenthehamster wrote: Compared to recent CMO problem 1, I think this problem is slightly easier since there is a rather natural way to motivate oneself to reach the solution. Did a video explanation of the solution: https://youtu.be/3mFMzLh59fU Lol, I saw ur video and came here to see others answer ! Great Video btw
18.06.2024 17:53
希望别铜[/quote] Look forward to the next day,You’ll do a great job
27.06.2024 18:05
We will solve the more general problem were $2023$ is replaced by a positive integer $k$. The answer is $\lambda=\frac{2}{k+1}$. Bound: Consider $n=2^{k+1}$. Clearly one of $x_1,x_2,\dots,x_k$ must have at least $2$ factors of $2$, as desired. Construction: We will proceed by induction with the trivial base case $k=1$. Now we will go from $k-1\mapsto k$. If any $p|n$ is prime and at least $n^{\frac{1}{k+1}}$ then we can remove it and induct down. Otherwise, we distribute the primes amongst the $x_i$, one by one. If at some point adding $p$ would bust any of the $x_i$ we would have that all $x_i$ are at that point larger than $n^{\frac{2}{k+1}}p^{-1}$. Multiplying cyclically we get that $p>n^{\frac{1}{k+1}}$, a contradiction.