Find all positive integers n for which there exists a set of exactly n distinct positive integers, none of which exceed n2, whose reciprocals add up to 1.
Problem
Source: Philippine MO 2022/5
Tags: number theory
20.03.2022 16:31
Let Sn={a1,a2,…,an} be a set of n distinct positive integers where a1<a2<⋯<an≤n2 and ∑ni=11ai=1. For n=1, let S1={1}. For n=2, 1a1+1a2=1⟺(a1−1)(a2−1)=1⟹(a1,a2)=(2,2). But a1≠a2, contradiction. So S2 does not exist. For n≥3, we will show Sn exists. If n cannot be expressed as m2+m for some integer m≥2, then let Sn={k(k+1)|1≤k≤n−1}∪{n}. Then ∑n−1k=11k(k+1)+1n=1−1n+1n=1. If n=m2+m for some integer m≥2 (so n≥6), then let Sn={k(k+1)|2≤k≤n−3}∪{3,8,24,n−2}. Then ∑n−3k=21k(k+1)+1n−2+13+18+124=12−1n−2+1n−2+12=1. Since 3,8,24,5,10,26 cannot be expressed as m2+m for some integer m≥2, then Sn contains n distinct positive integers. Thus, the answer is all positive integersn≠2.
13.08.2023 17:09