A finite set of distinct positive numbers is special if each integer in the set divides the sum of all integers within the set.

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 ?

Solution 1:

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.

Solution 2:

Here is a partial answer. Clearly, it suffices to show that $[n]=\lbrace 1,2,3,\ldots,n \rbrace$ is contained in a special set for every $n$, since any finite set of positive integers is included in some $[n]$. I describe an algorithm below that I have checked to work on every $[n]$ for $8 \leq n \leq 20$.

Here is the algorithm. It starts with an initial finite set $A$ of positive integers, which we increase one element at a time, until we hit a special set.

Step 1. Compute the sum $s=\sum_{a\in A} a$.

Step 2. Compute $X_1=\lbrace a \in A \ | \ a\not\mid s \rbrace$. If $X_1$ is empty, then $A$ is special and we are done. Otherwise, let $x_1$ be the smallest element in $X_1$.

Step 3. Compute $X_2=\lbrace a \in A \ | \ a\mid s \rbrace$ (so $X_2$ is the complement of $X_1$ in $A$). Denote by $l$ the lcm of the elements of $A$ (in particular, $l=1$ if $X_2$ is empty).

Step 4. Let $M$ be the smallest integer that satisfies the following three conditions : (1) it is larger than the largest element of $A$, (2) it is divisible by $l$, (3) the sum $s+M$ is divisible by $x_1$ (note that the congruence conditions are compatible by construction).

Step 5. Replace $A$ with $A'=A\cup \lbrace M \rbrace$ and return to step 1.

When $n=50$ for example, the algorithm eventually produces the 99-element special set

$$ [50]\cup\lbrace 1275, 2550, 30600, 35700, 142800, 2142000, 28274400, 30630600, 1102701600, 25607181600, 53542288800, 2248776129600, 69872686884000, 72201776446800, 5198527904169600, 213717258282528000, 9200527969062830400, 433301055304911393600, 2656323860782282891200, 12396178016983986825600, 30990445042459967064000, 464856675636899505960000, 511342343200589456556000, 5113423432005894565560000, 6136108118407073478672000, 269988757209911233061568000, 1129043893786901520075648000, 29637402211906164901985760000, 31048707079139791802080320000, 1241948283165591672083212800000, 24776868249153553858060095360000, 469456451036593652047454438400000, 8424135204712208311740432422400000, 142714761115124470222426149273600000, 2274516505272296244169916754048000000, 33966113145399623912937423527116800000, 473099433096637618787342684841984000000, 6113900366171932304328736234881024000000, 72857312696882193293250773465665536000000, 794807047602351199562735710534533120000000, 7868589771263276875671083534291877888000000, 69943020189006905561520742527038914560000000, 550801283988429381296975847400431452160000000, 3776923090206372900322120096460101386240000000, 22032051359537175251879033896017258086400000000, 105753846525778441209019362700882838814720000000, 396576924471669154533822610128310645555200000000, 1057538465257784412090193627008828388147200000000, 1586307697886676618135290440513242582220800000000\rbrace $$