19
$\begingroup$

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 ?

$\endgroup$
11
  • 2
    $\begingroup$ I suggest you start by finding an answer for $\{1,2\}$ and $\{2,3\}$. If you edit the question to show a few more examples and some real work maybe we can help. $\endgroup$ Aug 6, 2020 at 16:01
  • $\begingroup$ For {$1,2$} and {$2,3$} they are the are the subsets of {$1,2,3$} , which is a special set . $\endgroup$
    – Anonymous
    Aug 6, 2020 at 16:09
  • 2
    $\begingroup$ Well $6$ and $28$ are perfect numbers. What about $\{1,5\}$? Rather than answer my challenges one at a time, take few hours to find lots of examples. Then edit to tell us what you observe and where you are stuck. You can also tell us where this problem comes from and why it interests you. Note: I don't know how to do the problem. I'm just telling you how people attack questions like this. $\endgroup$ Aug 6, 2020 at 16:32
  • 2
    $\begingroup$ Another data point: For $\{1,2,3,4,5,6,7\}$ one special set (not necessarily the smallest; it's the result of trial and error) is $\{1,2,3,4,5,6,7,21,42,84,105,140\}$. Note that this set violates the observation in my previous comment, so that doesn't seem to be universal for special sets. $\endgroup$
    – celtschk
    Aug 7, 2020 at 8:21
  • 2
    $\begingroup$ The problem appears here: artofproblemsolving.com/community/c267568h1304775 $\endgroup$
    – Steve Kass
    Aug 8, 2020 at 16:49

4 Answers 4

6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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 $$

$\endgroup$
1
  • $\begingroup$ Your algorithm is interesting . Will take a note of it . $\endgroup$
    – Anonymous
    Aug 7, 2020 at 11:04
3
+50
$\begingroup$

TL;DR: With any non-special set $A$ of distinct integers, let the sum of the elements be $s$. The $\operatorname{lcm}$ of all of the elements of $A$, call it $q$, can always become a practical number, call it $m$, by multiplying with an appropriate integer. There then exists a set $B$ of distinct multiples of $s$, where each element divided by $s$ is a factor of $m$ and the sum of the elements is $(m - 1)s$. Then $A \cup B$ is a special set.


If the finite set of positive integers is a special set itself, then you can use just it. In particular, any single integer itself forms a special set, so if $n$ is the number of elements, any non-special set has $n \gt 1$. Also, in those cases, have the set be $A = \{a_i\}_{i=1}^{n}$ and let

$$s = \sum_{i=1}^{n}a_i \tag{1}\label{eq1A}$$

Consider adding multiples of $s$ to form a special set. For example, if $A = \{2,3\}$, then $s = 5$, with $2(5) = 10$ and $3(5) = 15$ being sufficient to add on to form a special set with a new sum of $30 = (2)(3)5$. In general, at the minimum, the new total sum must have a factor of the $\operatorname{lcm}$, call it $q$, of all of the $a_i$, plus $s$ must divide the sum as well, but it can have more factors than this if need be.

For some $j \ge 1$, let $B = \{b_i(s)\}_{i=1}^{j}$, where $b_i$ are distinct positive integers, be a set of multiples of $s$ which are being added, to get

$$S_t = s + \sum_{i=1}^{j}b_i(s) = s(1 + \sum_{i=1}^{j}b_i) \tag{2}\label{eq2A}$$

where $S_t$ is the total sum of the elements in $A \cup B$. Next, let

$$m = 1 + \sum_{i=1}^{j}b_i \tag{3}\label{eq3A}$$

You must have $b_i \mid m \; \forall \; 1 \le i \le j$, plus $q \mid ms$.

Note a practical number is

... a positive integer $n$ such that all smaller positive integers can be represented as sums of distinct divisors of $n$.

This means if $m$ is a practical number, there are distinct $b_i$, which are all factors of $m$, that give $\sum_{i=1}^{j}b_i = m - 1$. Regarding the requirements to be a practical number, the Characterization of practical numbers section states

A positive integer greater than one with prime factorization $n=p_1^{\alpha_1}\ldots p_k^{\alpha_k}$ (with the primes in sorted order $p_1 \lt p_2 \lt \dots \lt p_k$) is practical if and only if each of its prime factors $p_{i}$ is small enough for $p_{i}-1$ to have a representation as a sum of smaller divisors. For this to be true, the first prime $p_{1}$ must equal $2$ and, for every $i$ from $2$ to $k$, each successive prime $p_{i}$ must obey the inequality $$p_{i} \leq 1 + \sigma(p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\dots p_{i-1}^{\alpha_{i-1}}) = 1 + \prod_{j=1}^{i-1}\frac{p_{j}^{\alpha_{j} + 1} - 1}{p_{j} - 1}$$ where $\sigma(x)$ denotes the sum of the divisors of $x$.

As previously stated, you can add more factors if needed, e.g., just a sufficiently large power of $2$ or, alternatively, any one or more single or multiple factors of any primes up to the largest required prime. In any case, this means you can always easily create an $m$ which is a practical number and which satisfies the other conditions, resulting in $A \cup B$ forming a special set.

$\endgroup$
1
$\begingroup$

Another partial answer with a different approach. This is related to Egyptian fractions, representing a rational number with a sum of fractions that have numerator $1$ and different denominators. If you divide a special set by the sum of its elements, you get a set of Egyptian fractions that sum to $1$. Your set $\{1,2,3\}$ represents the fact that $1=\frac 66=\frac 16+\frac 26+\frac 36$ If you are given a starting set, the final sum must be a multiple of the least common multiple of the elements of the set. For example, take $\{3,7\}$ as our starting set. The LCM is $21$, so the sum of our special set will be a multiple of $21$. We can just start trying multiples of $21$ until we find one that works. One way to do this is to factor a multiple $21k$, then look for a set of divisors including $3,7$ that add to $21k$. For $k=1$ the divisors are $1,3,7,21$ and no set works. For $k=2$ the divisors are $1,2,3,6,7,14,21,42$ and again nothing works. For $k=4$ we have $1,2,3,4,6,7,12,14,21,28,42,84$ and we find $84=3+7+1+4+6+21+42$, so our set is $\{1,3,4,6,7,21,42\}$. It is known that the greedy algorithm for Egyptian fractions always terminates, but the denominator can get large. Unfortunately, we cannot use that to show that one can always find a special set because the fraction to be represented changes with the multiple $k$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .