Show that for any finite set $S$ of distinct positive integers, we can find a set $T \supseteq S$ such that every member of $T$ divides the sum of all the members of $T$. Original Statement: A finite set of (distinct) positive integers is called a DS-set if each of the integers divides the sum of them all. Prove that every finite set of positive integers is a subset of some DS-set.
Problem
Source: IMO Shortlist 1993, United Kingdom 3
Tags: induction, number theory, Subsets, Additive Number Theory, IMO Shortlist, Divisibility
15.11.2005 23:56
Lemma 1 Given $1,t>1$, we can find a set with the mentioned properties which contains $1$ and $t$ amd such that all its terms except for $1,t$ are divisible by $t+1$. We prove this by induction on $t$. For $t=2$ we take the set $\{1,2,3\}$. Now assume it's proven for $t-1$ and we want to prove it for $t$. If the construction for $t-1$ was $1,t-1,a_1,\ldots,a_k$ with $t|a_i,\ \forall i$, then the construction for $t$ will be $1,t,(t-1)(t+1),a_1(t+1),\ldots,a_k(t+1)$. It's easy to see that it satisfies all the requirements. Lemma 2 Given $a,b\in\mathbb N^*$, we can construct a set with the properties required by the problem which contains $a,b$ and such that $a,b$ are its smallest elements. Obviously, we can assume WLOG that $(a,b)=1$. We find some $t>a,b$ s.t. $a|b+t,b|a+t$, and then, if the construction resulting from Lemma 1 for $t-1$ is $1,t-1,a_1,\ldots,a_k$, then our set will be $a,b,t,(t-1)(a+b+t),a_1(a+b+t),\ldots,a_k(a+b+t)$. Now for the problem itself, we use induction on the number of elements. Suppose we have $n$ elements $x_1,\ldots,x_n$, and we've shown that the statement of the problem holds for $\le n-1$ numbers. We consider a set $\mathcal F$ of positive integers with the required properties which contains $x_1,\ldots,x_{n-1}$. If $S$ is the sum of all the elements in $\mathcal F$, then the set we get by adding $S,2S,4S,8S,\ldots$ to $\mathcal F$ still has the desired property, so we may very well assume that $S>x_n$ (what's important here is that $S\ne x_n$). Now we apply Lemma 2 to the pair of numbers $S,x_n$ to get a set $\{S,x_n,a_1,\ldots,a_k\}$. The set we want for the numbers $x_1,\ldots,x_n$ will be $\mathcal F\cup\{x_n,a_1,\ldots,a_k\}$.
25.09.2010 21:36
Let $n=\max S$. I will prove that there exists a DS-set that contains all the numbers from $1$ through $n$. If $n\ge 6$, then \[1,2,\cdots, n,\frac{n(n-3)}{2},(n)(n-1)(n-3),(n)(n-1)(n-2)(n-4),\cdots \] \[(n)(n-1)\cdots (3)(1)\] has a sum of $n!$ (the first $n+1$ elements sum to $n(n-1)$), all of its elements are distinct, and every element divides $n!$, as desired. If $n<6$, then just use the sequence for $n=6$
24.03.2021 20:06
GoldenFrog1618 wrote: Let $n=\max S$. I will prove that there exists a DS-set that contains all the numbers from $1$ through $n$. If $n\ge 6$, then \[1,2,\cdots, n,\frac{n(n-3)}{2},(n)(n-1)(n-3),(n)(n-1)(n-2)(n-4),\cdots \]\[(n)(n-1)\cdots (3)(1)\]has a sum of $n!$ (the first $n+1$ elements sum to $n(n-1)$), all of its elements are distinct, and every element divides $n!$, as desired. If $n<6$, then just use the sequence for $n=6$ Guess you should prove why this sum equals $n!$.