Maths Olympiad Prep

Track / Stage 7 / 187 of 300 #1587 of 1964

Problem 1587

National Olympiad second round; IMO P1/P4
Number theory Difficulty 7.3 Find the answer

Given a positive integer NN, determine all positive integers nn, satisfying the following condition: for any list d1,d2,…,dkd_1,d_2,\ldots,d_k of (not necessarily distinct) divisors of nn such that 1d1+1d2+…+1dk>N\frac{1}{d_1} + \frac{1}{d_2} + \ldots + \frac{1}{d_k} > N, some of the fractions 1d1,1d2,…,1dk\frac{1}{d_1}, \frac{1}{d_2}, \ldots, \frac{1}{d_k} add up to exactly NN.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Next problem →

Official solution

1. Identify the problem and the given condition:
We need to determine all positive integers n n such that for any list d1,d2,…,dk d_1, d_2, \ldots, d_k of (not necessarily distinct) divisors of n n satisfying
1d1+1d2+…+1dk>N, \frac{1}{d_1} + \frac{1}{d_2} + \ldots + \frac{1}{d_k} > N,
some of the fractions 1d1,1d2,…,1dk \frac{1}{d_1}, \frac{1}{d_2}, \ldots, \frac{1}{d_k} add up to exactly N N .

2. Propose the solution:
The solution claims that the answer is all powers of primes, i.e., n=pl n = p^l for some prime p p and positive integer l l .

3. Verify the solution for powers of primes:
Consider n=pl n = p^l . Let di=pai d_i = p^{a_i} for 1≤i≤k 1 \leq i \leq k . Assume that
∑i=1k1pai>N. \sum_{i=1}^k \frac{1}{p^{a_i}} > N.
Let t=max⁡(a1,…,ak) t = \max(a_1, \ldots, a_k) . Then, we can rewrite the inequality as:
∑i=1k1pai=∑i=1kpt−aipt=1pt∑i=1kpt−ai>N. \sum_{i=1}^k \frac{1}{p^{a_i}} = \sum_{i=1}^k \frac{p^{t-a_i}}{p^t} = \frac{1}{p^t} \sum_{i=1}^k p^{t-a_i} > N.
This implies:
∑i=1kpt−ai>Npt. \sum_{i=1}^k p^{t-a_i} > N p^t.
We need to find a subset S⊆{1,2,…,k} S \subseteq \{1, 2, \ldots, k\} such that:
∑i∈Spt−ai=Npt. \sum_{i \in S} p^{t-a_i} = N p^t.

4. Prove the claim:
Let x1,…,xk x_1, \ldots, x_k be positive integers less than t t such that:
∑i=1kpxi>Npt. \sum_{i=1}^k p^{x_i} > N p^t.
We need to show that there exists a subset S⊆{1,2,…,k} S \subseteq \{1, 2, \ldots, k\} such that:
∑i∈Spxi=Npt. \sum_{i \in S} p^{x_i} = N p^t.
We use induction on t t :
- **Base case t=1 t = 1 :** Clear since pxi=1 p^{x_i} = 1 and we can always find such a subset.
- Inductive step: Assume the statement holds for t−1 t-1 . If all xi x_i are larger than 1, divide the inequality by p p and reduce to the case for t−1 t-1 . If some xi=1 x_i = 1 , let r r be the number of such xi x_i . Then:
r+∑1≤i≤k,xi≠1pxi>Npt. r + \sum_{1 \leq i \leq k, x_i \neq 1} p^{x_i} > N p^t.
If ∑i=1kpxi=Npt+u \sum_{i=1}^k p^{x_i} = N p^t + u where u u is a positive integer, we have two cases:
- If r≥u r \geq u , pick all xi≠1 x_i \neq 1 and r−u r-u of the xi=1 x_i = 1 .
- If r<u r < u , then ∑1≤i≤k,xi≠1pxi>Npt \sum_{1 \leq i \leq k, x_i \neq 1} p^{x_i} > N p^t and reduce to the case of t−1 t-1 .

5. Conclude the proof for powers of primes:
The claim ensures that we can choose a subset S S such that:
∑i∈Spai=Npt. \sum_{i \in S} p^{a_i} = N p^t.
This proves that all powers of primes indeed work.

6. Disprove other cases:
Assume n n has two prime divisors p<q p < q . Consider:
∑i=1q−11q+1p>1. \sum_{i=1}^{q-1} \frac{1}{q} + \frac{1}{p} > 1.
There must exist a positive integer k k such that:
kq+1p=1, \frac{k}{q} + \frac{1}{p} = 1,
which is impossible. This contradiction shows that n n cannot have more than one prime divisor.

The final answer is n=pl \boxed{ n = p^l } for some prime p p and positive integer l l .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.