In what follows, the notation \(x\mid y\pm z\) means \(x\mid y+z\) or \(x\mid y-z\), and \(x\nmid y\pm z\) means \(x\nmid y+z\) and \(x\nmid y-z\). We prove the following via induction on \(n\): Let \(S\) be a set of \(n\) positive integers, none of which is the sum of two different numbers in \(S\). There is a permutation of \(S\) such that each of the middle \(n-2\) integers divides neither the sum nor difference of its neighbors. Our base case is \(n=2\), for which there is nothing to show. Now assume the permutation \[a_1,\;a_2,\;a_3,\;\ldots,\;a_n\]obeys the required conditions. For \(A>\max\{a_1,\ldots,a_n\}\) with \(A\ne a_i+a_j\) for all \(i\), \(j\), we will show we can insert \(A\) somewhere in \(a_1\), \(\ldots\), \(a_n\). First note that for all \(i\), \(j\) we have \(A\nmid a_i+a_j\). This is because \(|a_i-a_j|<A\) and \(a_i+a_j<2A\) always. Now assume for contradiction \(A\) cannot be inserted anywhere. Then the following assertions all hold: \(a_2\mid a_3\pm A\) (else \(a_1\), \(A\), \(a_2\), \(a_3\), \(\ldots\) works); \(a_2\mid a_1\pm A\) or \(a_3\mid a_4\pm A\) (else \(a_1\), \(a_2\), \(A\), \(a_3\), \(\ldots\)); \(a_3\mid a_2\pm A\) or \(a_4\mid a_5\pm A\) (else \(a_1\), \(a_2\), \(a_3\), \(A\), \(\ldots\)); $\ldots$ \(a_{n-2}\mid a_{n-3}\pm A\) or \(a_{n-1}\mid a_n\pm A\) (else \(\ldots\), \(a_{n-2}\), \(A\), \(a_{n-1}\), \(a_n\)); \(a_{n-1}\mid a_{n-2}\pm A\) (else \(\ldots\), \(a_{n-2}\), \(a_{n-1}\), \(A\), \(a_n\)); However, note for all \(i\) that \(a_i\mid a_{i-1}\pm A\) and \(a_i\mid a_{i+1}\pm A\) cannot simultaneously hold, since otherwise \(a_i\mid a_{i-1}\pm a_{i+1}\), contradiction. It follows that \begin{align*} a_2\mid a_3\pm A &\implies a_2\nmid a_1\pm A\implies a_3\mid a_4\pm A\\ &\implies a_3\nmid a_2\pm A\implies a_4\mid a_5\pm A\\ &\implies a_4\nmid a_3\pm A\implies a_5\mid a_6\pm A\\ &\implies\cdots\\ &\implies a_{n-2}\nmid a_{n-3}\pm A\implies a_{n-1}\mid a_n\pm A\\ &\implies a_{n-1}\nmid a_{n-2}\pm A, \end{align*}contradiction.

Let the numbers in $\mathcal S$ be $x_1>x_2>...>x_n$, then \newline\newline Claim 1. If $i>j>k$ then $$x_i\nmid x_j+x_k$$\newproof We have $2x_i>x_i+x_j$, so if $x_i|x_i+x_j$ then $x_k=x_i+x_j$, contradiction. $\blacksquare$ \newline\newline Claim 2. If $i>j,k$ and $$x_i|x_j+x_l$$for some $l$ then $x_i\nmid x_k+x_l$. \Proof Otherwise $|x_i|\leq |x_j-x_k|$, contradiction. $\blacksquare$ \newline\newline Now for each $2\leq m\leq n$ we inductively construct a sequence $x_1,...,x_m$, denoted by $y_1,y_2,...,y_m$ such that (a)$y_i\nmid y_{i-1}+y_{i+1}$ for each $i=2,3,...,m-1$ (b)At least one of the following hold (i) $y_1\nmid x_i+y_2$ for all $m+1\leq i\leq n$ (ii) $y_m\nmid x_i+y_{m-1}$ for all $m+1\leq i\leq n$ We say $y_1$ is good if $2(i)$ holds, and $y_m$ is good if $2(ii)$ holds. \newline\newline Notice that by Claim 1 the sequence $\{x_1,x_2\}$ satisfies the condition. \newline\newline Now suppose $y_1,...,y_m$ is defined we find a sequence $z_1,...,z_{m+1}$ satisfying the conditions. \newline\newline If both $y_1,y_m$ are good then just let $$(z_1,...,z_{m+1})=(x_{m+1},y_1,...,y_m)$$Suppose $y_m$ is good, if $$y_1\nmid x_{m+1}+y_2$$then we are done, otherwise, by Claim 2, after we put $x_{m+1}$ to the right of $y_m$, $y_1$ is good, so we are done in either case.

IndoMathXdZ wrote: Let $\mathcal{S}$ be a set consisting of $n \ge 3$ positive integers, none of which is a sum of two other distinct members of $\mathcal{S}$. Prove that the elements of $\mathcal{S}$ may be ordered as $a_1, a_2, \dots, a_n$ so that $a_i$ does not divide $a_{i - 1} + a_{i + 1}$ for all $i = 2, 3, \dots, n - 1$. Order the elements of $S$ as $a_1<a_2<\dots<a_n$. Claim: For $1\leq k\leq n-1$, if $a_k\mid a_{k+1}+a_{k-1}$, then $a_k\nmid a_{k+1}+a_i$ for all $i<k-1$. Proof: Suppose not. Then $a_k\mid a_{k+1}+a_{k-1}$ and $a_k\mid a_{k+1}+a_i$ implies that $a_k\mid a_{k-1}-a_i$, but $a_k>a_{k-1}-a_i>0$, contradiction. $\blacksquare$ Claim: $a_n\nmid a_i+a_j$ for all $1\leq i<j\leq n-1$ Proof: We have $2a_n=a_n+a_n>a_i+a_j>0$, and $a_i+a_j\neq a_n$ by the condition. By the claims we can easily construct such an sequence inductively.

@above how can you easily construct a sequence inductively by those claims?

Justanaccount wrote: @above how can you easily construct a sequence inductively by those claims? Not exactly the same inductive method i was talking about say FTSOC $a_i|a_{i-1}+a_{i+1}$ then by claim 1 we can easily replace $a_i$ from $a_k$ and we can keep repeating this process for a finish. For example at $n=4$ we have $1,2,4,6$ which we can replace by $1,2,6,4$ To show the steps don't get stuck just use both the claims

Sorry, but i'm not convinced that the process will not get struck. Please write a complete solution.

IndoMathXdZ wrote: Let $\mathcal{S}$ be a set consisting of $n \ge 3$ positive integers, none of which is a sum of two other distinct members of $\mathcal{S}$. Prove that the elements of $\mathcal{S}$ may be ordered as $a_1, a_2, \dots, a_n$ so that $a_i$ does not divide $a_{i - 1} + a_{i + 1}$ for all $i = 2, 3, \dots, n - 1$. We inductively prove this statement, with the base case clear. Assume that there is such an ordering for \(\mathcal{S}\) with cardinality \(n\), and let the ordering be \[\{a_1,a_2,\hdots,a_n\}\]Now we need to show that we can place \(a_{n+1}>\max\{a_1,a_2,\hdots,a_n\}\) in such a way that the condition of the statement holds true with one of the elements being \(a_{n+1}\). Firstly, we cannot have \(a_{n+1}\mid a_i+a_j\) for any \(i,j\) (need not be consecutive), because \(a_i+a_j<2a_{n+1}\) and \(a_i+a_j\) cannot be equal to \(a_{n+1}\), since \(\mathcal{S}\) is sum-free. Now, assume for the sake of contradiction that we cannot place \(a_{n+1}\) between any two consecutive terms \(a_i\) and \(a_{i+1}\), i.e. \(a_i\mid a_{n+1}+a_{i+1}\) or \(a_{i+1}\mid a_{n+1}+a_{i+2}\) (the case \(a_{n+1}\mid a_i+a_{i+1}\) being excluded due to what we proved above). I emphasize on or because both the statements cannot be true at once: If they were both true then we get \(a_i\mid a_{i-1}+a_{i+1}\) contradicting our inductive assumption. Therefore, one of them is true and the other is false. Therefore, we must have that \(a_i\mid a_{i+1}+a_{n+1} \) for all \(2\leq i\leq n-1\) and \(a_i\nmid a_{i-1}+a_{n+1}\) for all \(2\leq i\leq n\) (\(a_2\mid a_3+a_{n+1}\) implies that \(a_3\mid a_4+a_{n+1}\) because \(a_{2}\nmid a_1+a_{n+1}\) and so on). But that means that \(a_{n-1}\nmid a_{n-2}+a_{n+1}\) and so if we place \(a_{n+1}\) in the middle of \(a_{n-1}\) and \(a_n\), we get that that particular ordering indeed satisfies the statement of the problem, contradicting the assumption that no matter where you place \(a_{n+1}\) the statement fails. This completes the proof of the problem.

First, order the elements of $S$ in decreasing order $a_1>a_2>a_3> \dots > a_n.$ We then make two crucial observations: Lemma 1: Let $2 \le i,j \le n$ be two distinct indexes, then $a_1 \nmid a_i+ a_j.$ Proof: Since $a_1$ is maximal, we must have $a_1 > {a_i}{/2} + {a_j}{/2};$ and by problems condition $a_1 \ne a_i + a_j$ so the result follows. Lemma 2: Let $i$ and $j$ be any distinct indexes; then the number of indexes $i<k\le n$ such that $a_i \mid a_k+ a_j$ is at most 1 Proof: Suppose otherwise that, $a_i \mid a_k+ a_j$ and $a_i \mid a_l+ a_j$ for distinct indexes $i <k,l\le n.$ Then, $a_i \mid |a_k - a_l|;$ hence, since $a_k \ne a_l,$ we must have $a_i \le |a_k - a_l|,$ which is absurd since $a_i >a_k,a_l.$ Now we will order the sequence such that it satisfies problems condition. Start with the sequence $a_1;$ we will say that a sequence is valid if it satisties problems condition. We will add the numbers $a_2,a_3,\dots, a_n,$ "one by one" such that the sequence continues valid. We perform the following algorithm: $\bullet$ At first, let $i_1$ be the maximal such that the sequence $a_1,\dots , a_{i_1}$is valid; if $i_1 = n$ we finish the algorithm. $\bullet$ For $j \ge 2,$ at the $j^{th}$ step of the algorithm (if it has not finished yet), if $j$ is even(respectively odd) we add the numbers $a_{i_{j-1} +1},\dots , a_{i_j}$ to the left (respectively right) of the sequence; if $i_j = n,$ we stop the algorithm. For showing the algorithm works until we reach $n,$ we only need to show $i_j \ge i_{j-1} + 1$ for all $j.$ Indeed, we have that $i_2 \ge i_1$ since if $i_1 \ne n,$ we can add the number $a_{i_1+1}$ to the left of the sequence keeping it valid unless $a_1 \mid a_{2} + a_{i_1+1},$ which cannot happen by Lemma 1,. Now, we proceed by induction, assume we have contructed the sequence up to the $j^{th}$ step without finish or get stucked; then we must have by construction $$ a_{i_{j-1}} \mid a_{i_{j-1}-1} + a_{i_{j-1}+1}$$Hence, by Lemma 2, we have $$a_{i_{j-1}} \nmid a_{i_{j-1}-1} + a_{ i_j+1}$$since by induction hiphothesis $i_j + 1 > i_{j-1} +1;$ so we can add $a_{ i_j+1}$ to the sequence thus $i_{j+1} \ge i_j +1.$ So the algorithm works.

Call such an order a cute order. If $n = 3$, it is possible as, if the numbers are $a < b < c$, then $c \nmid a+b$ as $c \neq a+b$ and $2c > a+b$. Suppose its true until $n$, I'll show it for $n+1$, let $M$ be the maximum of the numbers, and by induction let the remaining numbers be ordered $a_1, a_2, \cdots, a_n$. I claim there exists a way to add $M$ while still keeping the ordering cute. First, note that $M$ cannot divide the sum of any two other elements as the set is sum free and $M$ is the maximum. Try to place $M$ in between $a_1$ and $a_2$, if this makes the ordering not cute, then it must be that $a_2 | M + a_3$. By induction I claim that $a_i | M + a_{i+1}$ for all $2 \leqslant i \leqslant n-1$. The base case is done so for the inductive step suppose its true for $i = 2,3,\cdots,k-1$ and we need it for $k$. Note that if placing $M$ between $a_{k-1}$ and $a_k$ causes a problem, then either $a_{k-1} | M + a_{k-2}$ or $a_k | M + a_{k+1}$. But since $a_{k-1} | M+a_k$ by induction, it follows that $a_{k-1} | a_{k} - a_{k-2}$. It would be nice if this led to a contradiction but it unfortunately does not. But not all is lost. To remedy this, we will actually induct on the stronger hypothesis that you can order the elements such that each element divides neither the sum nor the difference of its neighbors. Now, similar to the above paragraph, but to simplify things, call a pair $(i,i+1)$ or $(i,i-1)$ annoying if $a_i | a_{i \pm 1} \pm M$ and $2 \leqslant i \leqslant n-1$. Note that we cannot have $a_i | a_{i-1} \pm M$ and $a_i | a_{i+1} \pm M$, as if both have the same sign, then $a_i | a_{i+1} - a_{i-1}$, impossible by induction, and if both have opposite signs, then $a_i | a_{i-1} + a_{i+1}$, again impossible by induction. Consider inserting $M$ in any of $n-1$ places - after $a_1$ or after $a_2$ until after $a_{n-1}$. An annoying pair can be seen to eliminate exactly one such position. But since for a fixed $i$, it can be annoying with at most one of its neighbours by the above paragraph, it follows that there are at most $n-2$ annoying pairs, and since there are $n-1$ positions, it follows that there exists a position where $a_n$ can be inserted, completing the induction. $\blacksquare$

Note that for two elements $a,b$, if $a>b$ then $a,b,c$ and $c,b,a$ can be problematic for at most one element $c<b$, and if $a<b$ then $a,b,c$ and $c,b,a$ can be problematic for $0$ elements $c<b$ because that would require $b=a+c$. Thus, we may start with the largest element, put the second largest element on one side of it and keep adding elements to that side (going in decreasing order always) until we get an element for which we cannot. Now, we are guaranteed to be able to put it on the other side, and the for the side which we could not put it all smaller elements can go there so we just keep adding elements to the other side until we cannot, then switch back to the original side and add elements until we cannot, and so forth. This process is then guaranteed to end and work.

Fairly simple? We induct on $n$ to prove that we can insert the integer $X > \max{a_i}$ s.t. $X \neq a_i + a_j$ for some $i \neq j$ some where in the sequence, in the base case $n=2$ there is nothing to show, Assume we have established this statement till $n =k$., we will prove this for $n=k+1$ So we must have \(a_2\mid a_3\pm X\), \(a_3\mid a_4\pm X\) or \(a_2\mid a_1\pm X\), \(a_{k-2}\mid a_{k-3}\pm X\) and \(a_{k-1}\mid a_k\pm X\), For all $i$, we cannot have both \(a_i\mid a_{i+1}\pm X\) and \(a_i\mid a_{i-1}\pm X\). Then its easy to get a contradiction now. Done.

We induct on $n \ge 3$. Base case: Set $n=3$. Then, let $S=\{a, b, c\}$, where $a<b<c$. I contend that the ordering $a, c, b$ works. Since $0<a+b<c+c=2c$ and $a+b \neq c$, $c \nmid a+b$, so this ordering indeed works. Inductive step: Let $S=\{a_1, a_2, \dots, a_n\}$, where $a_i$ is a strictly increasing sequence. Let $a_{n+1}>a_n$ be a positive integer not expressible as $a_i+a_j$ for all $1 \le i < j \le n$. Let $b_1, \dots, b_n$ be a valid ordering of $S$. We will show that $a_{n+1}$ can be placed in the ordering such that the ordering remains valid, where we extend the definition of valid to the middle number dividing the sum or difference of the first and third number. Assume for contradiction that this isn't the case. First, we note that $b, a_{n+1}, c$ is a valid triple for all $b$ and $c$ smaller than $a_{n+1}$; the explanation is that $0<|b\pm c|<2a_{n+1}$ and $|b \pm c| \neq a_{n+1}$, which implies that $a_{n+1} \nmid b \pm c$. The key claim is the following: Claim: If $b, c, a_{n+1}$ is not a valid triple, then $a_{n+1}, c, b'$ is for all $b'<b$. Proof. We have that $c \mid b\pm a_{n+1}$, and since $0 < b' < b$, $b'\pm a_{n+1}$ leaves a nonzero residue $\bmod{\ c}$, as desired. Note that $b_2 \mid b_3 \pm a_{n+1}$, or else $a_{n+1}$ can be placed between $b_1$ and $b_2$. Likewise, for each $k$, either $b_{2k} \mid b_{2k-1} \pm a_{n+1}$ or $b_{2k+1} \mid b_{2k+2} \pm a_{n+1}$, and $b_{n-1} \mid b_{n-2} \pm a_{n+1}$. Let the assertion that \[ b_{\lfloor j/2 \rfloor + 2} \mid b_{\lfloor j/2 \rfloor + 3 + 2(-1)^{j+1}} \pm a_{n+1} \]for $1 \le j \le n-2$ be called $P(n-1)$. Then $P(1)$ is true, and the $P(i)$ alternate between true and false henceforth. Thus $P(n-2)$ is false, a contradiction. The inductive step is complete.

We'll prove the following statement by proceeding induction on $n$: Let $S$ be a set consisting of $n \ge 3$ positive integers, none of which is a sum of two other distinct elements of $S$. Then, we can order the elements of $S$ as $a_1, a_2, \dots, a_n$ so that $a_i \nmid a_{i-1} + a_{i+1}$ and $a_i \nmid a_{i-1} - a_{i+1}$ for all $2 \le i \le n-1$. Base case $n = 3$ is clear. Now assume it's true on $n-1$ and lets prove on $n$. Let $a = \max(S)$. By induction hypothesis, we may assume that the elements of $S\backslash \{a\}$ can be ordered as $a_1, a_2, \dots, a_{n-1}$ so that $a_i \nmid a_{i-1} + a_{i+1}$ and $a_i \nmid a_{i-1} - a_{i+1}$ for all $2 \le i \le n-2$. Our goal is to find an integer $i$ such that the sequence $(a_1, a_2, \dots, a_{i}, a, a_{i+1}, \dots, a_n)$ satisfies the condition. Note that for any $\varepsilon_1, \varepsilon_2 \in \{-1, 1\}, a_k \mid a + \varepsilon_1a_{k-1}$ and $a_k \mid a + \varepsilon_2a_{k+1}$ cannot simultaneously hold, otherwise we get $a_k \mid a_{k-1} + \varepsilon a_{k+1}$ for some $\varepsilon \in \{-1, 1\}$, a contradiction. Call an integer $k$ is left if $a_k \mid a + \varepsilon a_{k-1}$ for some $\varepsilon \in \{-1, 1\}$ and call it right if $a_k \mid a + \varepsilon a_{k-1}$ and call it good otherwise. Then, note that $1$ has to be left and $n-1$ has to be right, otherwise, we may insert $a$ into beginning or ending of the sequence $(a_1, a_2, \dots, a_{n-1})$. If there is an integer $k$ such that $k$ is not right and $k+1$ is not left, then we may insert $a$ into $(a_k, a_{k+1})$. Exclude all good indices as they are irrelevant. Then, since $1$ is left and $n-1$ is right, at some point, there is an integer $k$ such that $k$ is left and $k+1$ is right. Thus, we can insert $a$ into $(a_k, a_{k+1})$ and add good numbers we erased, we get our desired permutation. Hence, our induction step is completed, so we're done. $\blacksquare$ Remark: All motivation came from checking little cases as $n = 3,4,5$. While checking $n=4,5$, it motivates a deeper focus on size arguments, which led me to generalize the problem statement. Also, after reading the problem, induction instantly came into my head and the generalized problem wasn't so hard to prove.

Claim: It is possible to order the elements of $\mathcal S$ as $a_1,\dots, a_n$ such that $a_i$ does not divide $a_{i-1}+a_{i+1}$ or $a_{i-1}-a_{i+1}$. Proof: We will prove this by induction on $n$. In the case $n=1$ this is clearly true. Assume $n>1$. Order the smallest $n-1$ elements of $\mathcal S$ as $b_1,\dots,b_{n-1}$ such that they satisfy the given properties. Let $M$ be the highest element of $S$. We claim there is a pair $(b_i, b_{i+1})$ such that $M$ can be inserted between them while still satisfying the given properties. For any $i$, because $b_i$ and $b_{i+1}$ are distinct and less than $M$, \[b_i-b_{i+1}\not\equiv 0\pmod{M}.\]Because $b_i+b_{i+1}\neq M$, \[b_i+b_{i+1}\not\equiv 0\pmod{M}.\]So, it suffices to make sure that $b_i\not \mid M+b_{i-1}, M-b_{i-1}$ and $b_{i+1}\not\mid M+b_{i+2}, M-b_{i+2}$. Under each element of $b_1,\dots b_{n-1}$, we will draw a left or right arrow. Draw a right arrow under $b_1$ and a left arrow under $b_{n-1}$. Let $1<i<n-1$. If $b_{i-1}\equiv M\pmod{b_i}$, draw a left arrow under $b_i$. If $b_{i+1}\equiv M\pmod{b_i}$, draw a right arrow. Otherwise, if $b_{i-1}+M\not\equiv 0 \pmod{b_i}$, draw a right arrow, and if $b_{i+1}+M\not\equiv 0 \pmod{b_i}$, draw a left arrow. There must be a right arrow directly pointing to an adjacent left arrow. Then, we can put $M$ between the right and left arrows without breaking any of the rules.

Let the values be $x_1>x_2>\dots>x_n$, clearly we have that if $i>j, k$, $x_i\nmid x_j+x_k$, we also clearly have that if $i>j, k$ for any value $l$ if $x_i\mid x_j+x_l$, $x_i\nmid x_k+x_l$. Now I will prove that such a permutation exists, start the permutation by placing $x_1$ down, than place each subsequent value to either side of the chain of values we are building such that $x_{i-1}$ is only not placed next to $x_i$, if the value next to $x_i$ when summed with $x_{i-1}$ gives a value divisible by $x_i$, doing this ensures that one side always has the value which makes it divisble placed so when we can't place $x_{i-1}$ next to $x_i$ we can always place it on the other side.