A finite set of distinct positive numbers is special if each integer in the set divides the sum of all integers within the set. Prove that every finite set of positive integers is a subset of some special set.
What I Tried :- I tried to attack this problem by means of Contradiction. Suppose there dosen't exist a finite set of positive integers which is a subset of some special set . Let the set contain elements $(a_1,a_2,…,a_k)$ . Then there dosen't exist a bigger set with all the same elements than this set which is special. From here I couldn't go solving it .
Edit :- As small examples we have $(1,2,3)$ a special set ; hence $(1,2),(2,3),(1,3)$ are subsets of this set . For $(1,4)$ we have $(1,2,4,7,14)$ , although $6$ and $28$ are perfect numbers.
If we have a set which is not a subset of the factors of a perfect number , say $(1,5)$ ; we still have a special set $(1,4,5,10)$ where $(1,5)$ lies at it's subset . I am not getting any clues or ways to get these special sets.
Now can anyone help ?
Best Answer
Say we're given a set $S$, with sum $s$. We assume that $S$ does not consist of only powers of $2$; if it does, we can simply add to the set the number $3$. First, let $a$ be large enough so that $2^a > 2s$, meaning $2^a - s \not \in S$, and define $S' = S \cup \{2^a - s\}$, so $S'$ has sum $2^a$. Let $n$ be the product of all elements of $S'$, and let $b$ be large enough so that $2^b > n$.
We now construct a set $S''$ containing $S'$ with sum $2^{a+b} n$, all elements of which divide $2^{a+b} n$. Since $n-1$ is less than $2^b$, using its binary representation we can express $n-1$ as a sum of distinct elements of $\{1, 2, 4, \dots, 2^{b-1}\}$, and thus we can express $2^a(n-1)$ as a sum of distinct elements of $\{2^a, 2^{a+1}, \dots, 2^{a+b-1}\}$. Let $T$ be the subset of elements appearing in the latter sum. Then define $$S'' = S' \cup T \cup \{2^an, 2^{a+1}n, \dots, 2^{a+b-1}n\}.$$ As you can check, all elements of $S''$ divide $2^{a+b} n$, and the three sets in this union are disjoint (since $n$ is not a power of $2$), and thus $S''$ has sum $2^a + 2^a(n-1) + (2^{a+b} n - 2^a n) = 2^{a+b} n$, meaning $S''$ is special.