Maths Olympiad Prep

Track / Stage 7 / 173 of 300 #1573 of 1964

Problem 1573

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. Spacing and $ signs are ignored.

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 1ik 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=1kptaipt=1pti=1kptai>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=1kptai>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:
iSptai=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:
iSpxi=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 t1 t-1 . If all xi x_i are larger than 1, divide the inequality by p p and reduce to the case for t1 t-1 . If some xi=1 x_i = 1 , let r r be the number of such xi x_i . Then:
r+1ik,xi1pxi>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 ru r \geq u , pick all xi1 x_i \neq 1 and ru r-u of the xi=1 x_i = 1 .
- If r<u r < u , then 1ik,xi1pxi>Npt \sum_{1 \leq i \leq k, x_i \neq 1} p^{x_i} > N p^t and reduce to the case of t1 t-1 .

5. Conclude the proof for powers of primes:
The claim ensures that we can choose a subset S S such that:
iSpai=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=1q11q+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 and solution reproduced as published; topic, difficulty and ordering added by this site.