Given a positive integer $N$, determine all positive integers $n$, satisfying the following condition: for any list $d_1,d_2,\ldots,d_k$ of (not necessarily distinct) divisors of $n$ such that $\frac{1}{d_1} + \frac{1}{d_2} + \ldots + \frac{1}{d_k} > N$, some of the fractions $\frac{1}{d_1}, \frac{1}{d_2}, \ldots, \frac{1}{d_k}$ add up to exactly $N$.
Problem
Source: RMM Extralist 2021 N1
Tags: RMM Shortlist, number theory, unit fractions, Divisors
19.09.2023 10:17
The answer is all powers of primes, i.e. $n=p^l$ for some prime $p$ and positive integer $l$. To show that these indeed work, consider the sequence $a_i$, $1\le i\le k$ of integers so that $d_i=p^{a_i}$. Then, assume that \[\sum_{i=1}^k\frac{1}{p^{a_i}}>N\]Let $t=\max(a_1,\hdots, a_k)$. Then, we have that $\frac{1}{p^{a_i}}=\frac{p^{t-a_i}}{p^t}$, so, the given inequality can be re-written as: \[\sum_{i=1}^kp^{t-a_i}>Np^t\]It therefore suffices to choose some subset $S$ of $[k]$ so that \[\sum_{i\in S}p^{t-a_i}=Np^t\]Now, we prove a claim: Claim: Let $x_1,\hdots,x_k$ be positive integers less than $t$ so that $\sum_{i=1}^tp^{x_i}>np^t$ where $n$ is a positive integer. Then, we can pick a subset $S$ of $[k]$ so that $\sum_{i\in S}p^{x_i}=np^t$. Proof. We prove this via induction on $t$, with the base-case $t=1$ clear. If all of $x_i$ are larger than $1$, we can just divide the entire inequality by $p$, and get the case for $t-1$, and thus we can conclude. Assume that $r$ of the $x_i$ are equal to $1$. Then, we can write: \[r+\sum_{1\le i\le k,~x_i\neq 1}p^{x_i}>np^t\]Now, if $\sum_{i=1}^k p^{x_i}=np^t+u$, where $u$ is a positive integer, we have two cases, one is, if $r\ge u$. In this case, we can just pick all the $x_i$ which are not $1$ and $r-u$ of the $x_i$ which are $1$, and this will conclude. In the other case, that is, when $r<u$. In this case, we have $\sum_{1\le i\le k,~x_i\neq 1}p^{x_i}>np^t$ already, and this can be reduced into the case of $t-1$, and so we can conclude here as well. This shows that we are done for all cases, and therefore we are done with the proof of this claim. Getting back to the problem, this claim above ensures that we can choose a subset $S$ of $[k]$ for which \[\sum_{i\in S}p^{a_i}=Np^t\]This proves that all powers of primes indeed work. For the other part of the problem, assume for the sake of contradiction that $n$ has two prime divisors $p<q$. Then, as: \[\sum_{i=1}^{q-1}\frac{1}{q}+\frac{1}{p}>1\]there must exist a positive integer $k$ so that: \[\frac{k}{q}+\frac{1}{p}=1\]which can clearly not happen. This is a contradiction, and therefore we are done.