If each term in a sum of positive integers divides that sum, then there must be one term that divides another.

Question

Let $\begin{align} \{ x_i \}_{i=1}^n \end{align}$ be a finite sequence such that $x_i\in\mathbb{N}$. Prove that if $x_i$ divides $\sum_{i=1}^n x_i$, $\forall{ 1\le i\le n}$ then there are $1\le j\neq h\le n$ such that $x_j$ divides $x_h$.
I know that I should avoid asking questions without trying to solve on my own, but I don't know where to start - I tried with induction but except the basis case of $n=2$. I couldn't reach anything.

Let $x_1,x_2\in\mathbb{N}$ such that $x_1|(x_1+x_2)$ and $x_2|(x_1+x_2)$ so $\exists k_1,k_2$ such that $$k_1\cdot x_1=x_1+x_2 \implies (k_1-1)\cdot x_1=x_2\implies x_1|x_2 \\k_2\cdot x_2=x_1+x_2\implies(k_2-1)\cdot x_2=x_1\implies x_2|x_1\\ \Longrightarrow x_1=x_2 $$

Probably induction won't help, but I also thought that maybe the pigeonhole principle might come in handy, but could not think about anything. Please help

Answer 1

Update:

This conjecture is false - note that it is equivalent to this conjecture, which was disproved by Nechemia Burshtein (See Example 2 after Question 6 here - Thanks to Lucid in the comments section of the other question for providing another reference that led to this.)

---

Note that to see the two conjectures are equivalent, we can observe that $x_j\mid \sum_{i=1}^n x_i$ for each $j$ if and only if $y_j:=\frac{\sum_{i=1}^n x_i}{x_j}$ is an integer, in which case we have $$\sum_{j=1}^n \frac{1}{y_j}=\sum_{j=1}^n \frac{x_j}{\sum_{i=1}^n x_i}=1,$$ and then $x_j\mid x_k$ if and only if $y_k\mid y_j$.

---

Original remark:

Here is an observation (too long for a comment, and actually leading to an answer for small $n$.)

Lemma. The conjecture is true whenever $\frac{\sum_{i=1}^nx_i}{x_k}$ has only one distinct prime factor for some $k$.

Proof.

Suppose $\sum_{i=1}^nx_i=p^mx_k$, for some prime $p$ and some $m$. Let $p^l$ be the largest power of $p$ such that $p^l\mid x_k$. If the conjecture fails, then for each $j\neq k$ we have $x_j\nmid x_k$ but $x_j\mid p^mx_k$, so we must have $p^{l+1}\mid x_j$, as otherwise multiplication by a power of $p$ will not change divisibility of $x_k$ by $x_j$. Since $p^{l+1}\nmid x_k$, we then have $p^{l+1}\nmid \sum_{i=1}^n x_i$, contradicting $p^{l+1}\mid x_j\mid \sum_{i=1}^n x_i$ when $j\neq k$.

Corollary. The conjecture is true for $n\leq 6$.

Proof.

Let $x_k$ be the largest value. With no loss of generality every other number is strictly smaller, so we have $$\frac{\sum_{i=1}^nx_i}{x_k}<\frac{nx_k}{x_k}=n\leq 6,$$ so $\frac{\sum_{i=1}^nx_i}{x_k}$ has only one distinct prime factor.

Answer 2

Too long for a comment (but not a complete solution):

Consider the case $n=3$. We assume the three natural numbers $a,b,c$ are distinct (else the problem is trivial). Without loss of generality take $a<b<c$.

We claim that $(a,b,c)$ is a multiple of $(1,2,3)$. To see this, note that $a+b<2c$ yet $c$ divides $a+b$, so $a+b=c$. Similarly, $2a<a+b=c<2b\implies a+c<3b$ But since $b\,|\,(a+c)$ we must have $a+c=2b$. Combining this we see that $2a=b$ and $3a=c$, as desired.

Conjecture: The only examples of these sequences (with distinct terms) consist of multiples of the first $n$ terms of $ A=\{1,2,3, 6, 12, 24, 48, \cdots\}$ where the infinite sequence is defined by $A[1]=1, A[2]=2, A[n]=\sum_{i=1}^{n-1}A[i]$ for $n>2$. Of course, that establishes the desired result (though it remains to be proven, and, of course, it might not even be true).

Update I: A commenter (@JohnOmielan) has produced counterexamples to my (admittedly over optimistic) conjecture. For $n=4$, he found $1,4,5,10$ and for $n=5$, he found $1, 3,5,6,15$. As he remarks, the largest term in both of these is indeed the sum of the prior ones, but there is no particular reason to imagine that even this holds for all examples. I add that these examples are "non-inductive", by which I mean that deleting the largest term does not produce a sequence of the form we want.

Update II: A second commenter (@CalvinLin) produced $2,5,6,12,15,20$ which fails even the weaker notion (that the largest term should be the sum of the others). I think that puts the final stake in the heart of the over-optimistic conjecture.