Given a positive integer , determine all positive integers , satisfying the following condition: for any list of (not necessarily distinct) divisors of such that , some of the fractions add up to exactly .
Problem 1573
Official solution
1. Identify the problem and the given condition:
We need to determine all positive integers such that for any list of (not necessarily distinct) divisors of satisfying
some of the fractions add up to exactly .
2. Propose the solution:
The solution claims that the answer is all powers of primes, i.e., for some prime and positive integer .
3. Verify the solution for powers of primes:
Consider . Let for . Assume that
Let . Then, we can rewrite the inequality as:
This implies:
We need to find a subset such that:
4. Prove the claim:
Let be positive integers less than such that:
We need to show that there exists a subset such that:
We use induction on :
- **Base case :** Clear since and we can always find such a subset.
- Inductive step: Assume the statement holds for . If all are larger than 1, divide the inequality by and reduce to the case for . If some , let be the number of such . Then:
If where is a positive integer, we have two cases:
- If , pick all and of the .
- If , then and reduce to the case of .
5. Conclude the proof for powers of primes:
The claim ensures that we can choose a subset such that:
This proves that all powers of primes indeed work.
6. Disprove other cases:
Assume has two prime divisors . Consider:
There must exist a positive integer such that:
which is impossible. This contradiction shows that cannot have more than one prime divisor.
The final answer is for some prime and positive integer .