Maths Olympiad Prep

Track / Stage 6 / 229 of 400 #1869 of 2604

Problem 1869

National Olympiad, first round
Number theory Difficulty 6.4 Prove it Chinese Mathematical Olympiad · China

Determine the smallest real number λ\lambda with the following property: every positive integer nn can be written as a product n=x1x2⋯x2023n = x_1x_2\cdots x_{2023}, with each xix_i either a prime number or a positive integer that is less than or equal to nλn^\lambda.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solutions — 4

Solution 1

The number λ\lambda is 11012\frac{1}{1012}.
The minimal such λ\lambda is 11012\frac{1}{1012}.
To see that λ<11012\lambda < \frac{1}{1012} does not work, we take n=p2024n = p^{2024} for some prime number pp. Then when writing nn as the product of 20232023 integers, at least one of the integers is pαp^\alpha for some α≥2\alpha \ge 2 (which is not a prime number); then pα≥p2=n11012>nλp^\alpha \ge p^2 = n^{\frac{1}{1012}} > n^\lambda.
Now we prove that λ=11012\lambda = \frac{1}{1012} satisfies the condition of the problem. To start, we write nn as the product of its prime factors n=p1p2⋯prn = p_1p_2\cdots p_r (allowing some pip_i's to be equal), where we order the primes so that p1≥p2≥⋯p_1 \ge p_2 \ge \cdots.
Now starting from p1p_1, let r1≥1r_1 \ge 1 be the smallest integer such that x1=p1p2⋯pr1>n1/2024x_1 = p_1p_2\cdots p_{r_1} > n^{1/2024}. Note that this x1x_1 satisfies the condition of the problem, namely, if r1=1r_1 = 1, x1x_1 is a prime number; otherwise r1≥2r_1 \ge 2, then we must have p1≤n1/2024p_1 \le n^{1/2024}. This means that pr≤n1/2024p_r \le n^{1/2024}; so
x1=(p1p2⋯pr−1)pr≤n1/2024⋅n1/2024=n1/1012, x_1 = (p_1p_2\cdots p_{r-1})p_r \le n^{1/2024} \cdot n^{1/2024} = n^{1/1012},
where the first inequality holds by minimality of r1r_1.
Next, let r2≥r1+1r_2 \ge r_1 + 1 be the smallest integer such that x2=pr1+1⋯pr2>n1/2024x_2 = p_{r_1+1}\cdots p_{r_2} > n^{1/2024}. The same argument as above shows that either x2x_2 is a prime number or x2≤n1/1012x_2 \le n^{1/1012}.
Continue this process. If we run out of pip_i's before reaching x2023x_{2023}, then set the rest of xjx_j to be 11, and then n=x1x2⋯x2023n = x_1x_2\cdots x_{2023} gives the needed decomposition. Otherwise, we have constructed x1,x2,…,x2022x_1, x_2, \dots, x_{2022} satisfying the condition of the problem (and that each xi>n1/2024x_i > n^{1/2024} by construction), then we must have
x2023:=nx1⋯x2022<n(n1/2024)2022=n1/1012. x_{2023} := \frac{n}{x_1 \cdots x_{2022}} < \frac{n}{(n^{1/2024})^{2022}} = n^{1/1012}.
The decomposition n=x1x2⋯x2023n = x_1x_2\cdots x_{2023} satisfies the conditions of the problem.

Solution 2

The proof for that λ<11012\lambda < \frac{1}{1012} does not work is the same as Solution 1. We prove that λ=11012\lambda = \frac{1}{1012} satisfies the requirement. Let n=p1p2⋯prn = p_1p_2\cdots p_r be the prime factorization of nn (where p1≥p2≥⋯≥prp_1 \ge p_2 \ge \cdots \ge p_r). For i=1,2,…,1012i = 1, 2, \dots, 1012, define
yi=∏1≤j≤rj≡i(mod1012)pj. y_i = \prod_{\substack{1 \le j \le r \\ j \equiv i \pmod{1012}}} p_j.
Then y1≥y2≥⋯≥y1012y_1 \ge y_2 \ge \cdots \ge y_{1012} and y1y2⋯y1012=ny_1y_2\cdots y_{1012} = n.
If y1≤n1/1012y_1 \le n^{1/1012}, then let x1,…,x2023x_1, \dots, x_{2023} be y1,y2,…,y1012y_1, y_2, \dots, y_{1012} plus 10111011 ones.
If y1>n1/1012y_1 > n^{1/1012}, since y1012≤n1/1012y_{1012} \le n^{1/1012}, suppose yk>n1/1012≥yk+1y_k > n^{1/1012} \ge y_{k+1}, then 1≤k≤10111 \le k \le 1011.
For 1≤i≤k1 \le i \le k, we have
yipi≤y1012≤n1/1012. \frac{y_i}{p_i} \le y_{1012} \le n^{1/1012}.
Let x1,x2,…,x2023x_1, x_2, \dots, x_{2023} be y1p1,…,ykpk,yk+1,…,y1012,p1,…,pk\frac{y_1}{p_1}, \dots, \frac{y_k}{p_k}, y_{k+1}, \dots, y_{1012}, p_1, \dots, p_k and 1011−k1011 - k ones.

Solution 3

The proof for that λ<11012\lambda < \frac{1}{1012} does not work is the same as Solution 1. We prove that λ=11012\lambda = \frac{1}{1012} satisfies the requirement. Express nn as n=x1x2⋯x2023n = x_1x_2\cdots x_{2023} such that

x1+x2+⋯+x2023x_1 + x_2 + \cdots + x_{2023} is minimized. (Since there are a finite number of ways to express this, such a representation must exist.) Next, we prove that every xix_i greater than n1/1012n^{1/1012} is a prime number.
We use proof by contradiction. Suppose x1>n1/1012x_1 > n^{1/1012} and x1x_1 is not a prime number. Let x1=abx_1 = ab where a>1a > 1 and b>1b > 1, and without loss of generality, assume a≥ba \ge b. Since
x2⋯x2023=nx1<x11012x1=x11011=(x1)2022≤a2022, x_2 \cdots x_{2023} = \frac{n}{x_1} < \frac{x_1^{1012}}{x_1} = x_1^{1011} = (\sqrt{x_1})^{2022} \le a^{2022},
there exists an xi<ax_i < a. Assume without loss of generality that x2<ax_2 < a.
Express nn as n=a⋅b⋅x2⋅x3⋯x2023n = a \cdot b \cdot x_2 \cdot x_3 \cdots x_{2023}. Since
(ab+x2+x3+⋯+x2023)−(a+bx2+x3+⋯+x2023)=(b−1)(a−x2)>0, (ab + x_2 + x_3 + \cdots + x_{2023}) - (a + bx_2 + x_3 + \cdots + x_{2023}) = (b-1)(a-x_2) > 0,
the expression n=x1x2⋯x2023n = x_1x_2\cdots x_{2023} is not the one that minimizes x1+x2+⋯+x2023x_1+x_2+\cdots+x_{2023}, which is a contradiction!
Therefore, λ=11012\lambda = \frac{1}{1012} satisfies the problem's conditions.

Solution 4

The proof for that λ<11012\lambda < \frac{1}{1012} does not work is the same as Solution 1. We prove that λ=11012\lambda = \frac{1}{1012} satisfies the requirement. Let n=p1p2⋯pkn = p_1p_2\cdots p_k, where p1≥p2≥⋯≥pkp_1 \ge p_2 \ge \cdots \ge p_k are all the prime factors of nn.
If k≤2023k \le 2023, then express nn as the product of p1,p2,⋯ ,pkp_1, p_2, \cdots, p_k and 2023−k2023-k ones.
If k>2023k > 2023, first express nn as n=p1p2⋯pkn = p_1p_2\cdots p_k. Then, perform the following operation: in each step, select the smallest two factors and combine them into their product, continue this process until only 20232023 factors remain. In each step, as the current number of factors is ≥2024\ge 2024, the product of the smallest two numbers will be ≤n2/2024=n1/1012\le n^{2/2024} = n^{1/1012}. This indicates that every "composite" number formed after each operation is ≤n1/1012\le n^{1/1012}.
Combining this with the fact that the initial numbers are primes, it can be concluded that when the operation ends, the 20232023 factors are either prime or do not exceed n1/1012n^{1/1012}. Hence, λ=11012\lambda = \frac{1}{1012} satisfies the conditions of the problem.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.