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
sarjinius
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}$.
pln23
13.08.2023 17:09
We claim that all $n \neq 2$ work.
It's not hard to see that $\frac{1}{a_1} + \frac{1}{a_2} = 1$ has no solution in positive integers by multiplying and factoring the resulting expression.
To prove that all other $n$ work, we will construct the numbers $a_1$ to $a_n$.
Construction: We say that $n$ is bad if $n$ is of the form $j(j+1)$ for some positive integer $j$ and good otherwise.
If $n = 1$ we simply take $a_1 = 1$. For $n > 3$, it follows from partial fraction decomposition or some other method that $\sum_{i=1}^{n-1} \frac{1}{i(i+1)}+\frac{1}{n} = 1$.
If $n$ is good, we can simply set $a_i = \frac{1}{i(i+1)}$ and $a_n = \frac{1}{n}$ to get a valid construction.
If $n$ is bad, then $\frac{1}{n}$ appears twice in the above construction. To solve that problem, note that
$\frac{1}{6} = \frac{1}{9}+\frac{1}{18}$ and $\frac{1}{n} + \frac{1}{(n-1)n} = \frac{1}{n-1}$.
Since $n \geq 6$, we may change the above construction to
$a_2 = \frac{1}{9}, a_3 = \frac{1}{18}, a_i = \frac{1}{(i-1)i}$ for $4 \leq i \leq n-1$ and $a_n = \frac{1}{n-1}$. Since $n-1$ is good, the above construction satisfies the requirement.