Find all positive integers $n$ for which there exists a set of exactly $n$ distinct positive integers, none of which exceed $n^2$, whose reciprocals add up to $1$.
Problem
Source: Philippine MO 2022/5
Tags: number theory
20.03.2022 16:31
Let $S_n = \{a_1, a_2, \dots, a_n\}$ be a set of $n$ distinct positive integers where $a_1 < a_2 <\dots< a_n \le n^2$ and $\sum_{i=1}^n \frac{1}{a_i} = 1$. For $n = 1$, let $S_1 = \{1\}$. For $n = 2$, $\frac{1}{a_1} + \frac{1}{a_2} = 1 \iff (a_1 - 1)(a_2 - 1) = 1 \implies (a_1, a_2) = (2, 2)$. But $a_1 \ne a_2 $, contradiction. So $S_2$ does not exist. For $n \ge 3$, we will show $S_n$ exists. If $n$ cannot be expressed as $m^2+m$ for some integer $m \ge 2$, then let $S_n = \{k(k+1) | 1 \le k \le n - 1\} \cup \{n\}$. Then $\sum_{k=1}^{n-1} \frac{1}{k(k+1)} + \frac{1}{n} = 1 - \frac{1}{n} + \frac{1}{n} = 1$. If $n = m^2+m$ for some integer $m \ge 2$ (so $n \ge 6$), then let $S_n = \{k(k+1) | 2 \le k \le n - 3\} \cup \{3, 8, 24, n-2\}$. Then $\sum_{k=2}^{n-3} \frac{1}{k(k+1)} + \frac{1}{n-2} + \frac{1}{3} + \frac{1}{8} + \frac{1}{24} = \frac{1}{2} - \frac{1}{n-2} + \frac{1}{n-2} + \frac{1}{2} = 1$. Since $3, 8, 24, 5, 10, 26$ cannot be expressed as $m^2+m$ for some integer $m \ge 2$, then $S_n$ contains $n$ distinct positive integers. Thus, the answer is $\boxed{\text{all positive integers} \: n \ne 2}$.
13.08.2023 17:09