For $n = 1$ and $a_1 = 2$ you will only have even integers, so we must be at least add the condition $n>1$. Is there any other missing condition? Pierre.

pbornsztein wrote: For $n = 1$ and $a_1 = 2$ you will only have even integers, Hmm... if $a_1 = 2$, then the greatest common divisor is 2, not 1... I think I have some steps towards the solution of the problem: At first, $0\in S$, and moreover, if $x\in S$ and $y\in S$ and $x+y\in S$, then for every integer m and n we have $mx+ny\in S$. Now, if we succeed to find two relatively prime elements in S, then we will be done. Darij

darij grinberg wrote: Now, if we succeed to find two relatively prime elements in S, then we will be done. Just to comment on that, I think a lot of contestants made the mistake by claiming that there are two a_i, a_j, which are relatively prime. But this is not necessarily true, say for {6, 10, 15}. Here's an outline of my solution. I first showed that any integer s can be writen as $\sum a_i t_i$ for some integer vector $(t_1, \ldots, t_n)$. If n=2, then it's bezout's theorem. Otherwise we have by induction $s = \sum_{i=1}^{n-1} a_i t_i +\gcd(a_{n},a_{n+1}) t_n$. And then write $\gcd(a_{n},a_{n+1})$ as some $a_{n} p_n+a_{n+1} p_{n+1}$. Then, by using some iteration/induction, we can show that $a \in S$ implies $ma \in S$ for each integer m. We can carry further by showing that $a, b \in S$ implies $pa+qb \in S$ for any integer p, q. And so on, so $\sum a_i t_i \in S$ for any vector (t). And we are done by the first claim.

Just a little variation: it is nown that for any set of integers, there is a linear combination of them equal to their biggest common divisor, so in our special case, there is a linear combination of the ai equal to 1, and result follows!

billzhao wrote: $a, b \in S$ implies $pa+qb \in S$ for any integer p, q. This is the only piece of the problem that I do not see how to do. Could you please post your proof of this lemma?

Why does this problem lie in Solved Section? I don't see solution. Moreover, I also don't believe some billzhao's arguments. I will move it to Unsolved Section. Ok. Let's do some steps. 1) $a\in S$ implies $ma\in S$. Indeed, $0\in S$, $a\in S$ and $0+a\in S$, so $-a=0-a\in S$. Suppose $ka\in S$ and $(k-1)a\in S$, then $ka+(-a)\in S$ implies $(k+1)a=ka-(-a)\in S$. So $ma\in S$ for all $m\in\mathbb{N}$. So $-ma=m(-a)\in S$. 2) For all $a_i$ and $a_j$ numbers $pa_i+qa_j\in S$. By induction, for example: $a_i-a_j\in S$ implies $a_i+a_j\in S$, $(a_i+a_j)-a_j\in S$ implies $a_i+2a_j\in S$ and so on (induction on $|p|+|q|$).

Here is the rest of solution: Let 2^e_i||a_i and wlog assume $e_1\geq\ e_2...\geq\e_n$ Let $d_i =gcd(a_1;...a_i)$ we will prove by induction that S contain all multiple of d_i,case i=n is the desired result Assume that S contains all multiple of d_i for some $2\leq\i<n$.Let T be the set of integers m such that m is divisible by d_i and $m+ra_{i+1}\in S$for all integers r.Then T contains nonzero positive and negative numbears,namely any multiple of a_i.If $t\in T$ and s is divisible by d_i s.t $t-s\in T$ and $t+s\in T$.By taking t=s=d_i we deduce that $2d_i\in T$;by induction we have $2md_i\in T$ for any integer m It's easy to see that we can find integer f,g with f even s.t fd_i+ga_{i+1}=d_{i+1}.Then for any integer r we have $rfd_i\in T$ and so $rd_{i+1}\in S$.We are done

Okay, now looking back at my old "solution" (TWO YEARS AGO!!!!), I probably made the incorrect assumption that clause (b) read "if $x, y \in S$ then $x - y \in S$", which simplifies the problem dramatically. Sorry guys ... (still, it was two years ago) Wow, this is such a cruel realization. I always thought that I had solved this problem. Well, I guess it would feel better to realize it now than it would have been two years ago ...

wait.... how do we know that d_i is in set T?

0 = a_i - a_i for any i={1,2,...,n} (prop 2 ).Hence 0 belongs to S. There exist integers k_1, k_2,...k_n such that k_1a_1 +k_2a_2 + ...+ k_na_n = 1 ->bezout's theorem Suppose a k_i, where i={1,2,...n} is positive, it can be obtained by adding a_i to itself.( n-1 operations required)( again prop 2, this is trivial,go for induction for rigour) Since 0- k_i belongs to S(prop 3), any negative co efficient may be obtained. =>1 belongs to S. Any +ve or negative integer can be obtained by prop 2 and prop 3.

This problem can perhaps be solved with this in mind. Obviously "zero" lies in the set. SO negative numbers of same absolute values as positives can be generated. That is, if a is +ve ; a belongs to s and 0 belongs to S So does -a.... So we will prove that we can generate all the positives only... Consider 2 +ve integers to each other on a board. U can place any positive difference of the numbers on the board if it does not exist already. clearly the smallest number u place is the gcd "d" of the numbers say "a' and "b". And the numbers b-d, b-2d, b-3d..d all appear on the board. If gcd (a,b)=1, all numbers less than or equal to b appear. Now u can create all numbers larger than b too which settles the case for n=2. All numbers larger thn b are created by noticng that 1 and 0 lies on the board. there sum is on board. So -1 will can be kept on the board. Do it... b is on board; -1 is on board...there sum b-1 is on board...So b+1 "their diff is on board"... Similarly b+2, b+3 and all bigger numbers can be put on board (or the set S).. For n > 2, take a & b with a gcd d > 1 (possibly)....generate d.... Consider d and a number "c" with gcd(c,d) = e.... Since gcd of all n numbers is 1, sooner or later two number with gcd 1 appear....at which stage the game is over

Here's a weird proof that you can get any linear combination of $ a_{1},a_{2},\ldots,a_{n}$, after which we can prove using the extension of Bezout's Theorem (which is not hard with induction) that we have to have 1 on the board. So we induct on $ n$, showing that we can get linear combinations of any subset of our starting integers. For $ n=2$ (because for $ n=1$ the whole problem is trivial), we can use the Euclidean Algorithm to get down to $ \gcd(a_{1},a_{2})$. Like, we have $ a_{1},a_{2}$, and also $ a_{1}-a_{2}$, and now we have $ a_{1}-a_{2}+a_{2}=a_{1}$, etc. This means we can get any multiple of the gcd, and thus any linear combination of $ a_{1}$ and $ a_{2}$ (by Bezout). Now assume it's proven for n-1 (ok this really should be k instead of n here, but you get my drift). We claim that we can get any $ x_{1}a_{1}+x_{2}a_{2}+\cdots+x_{n}a_{n}$. Say one of the $ x_{i}$ is even. Then, $ x_{1}a_{1}+x_{2}a_{2}+\cdots+\dfrac{x_{1}}{2}a_{i}$ and $ -\dfrac{x_{1}}{2}a_{i}-x_{i+1}a_{i+1}-\cdots-x_{n}a_{n}$ are both attainable, as is their sum, because the $ a_{i}$ term vanishes and it's a linear combination of $ n-1$ of the starting values. Thus, their difference is attainable, which is what we want (of course, we have to modify this argument if i=1 or i=n, but this is easy; apply a "frame shift"). Now it suffices to consider the case when all the $ x_{i}$ are odd. We claim that it will be equal to some other linear combination in which one of the $ x_{i}$ are odd. Take any two of the $ a_{i}$, say $ a_{i}$ and $ a_{j}$. Then we can find integers $ c$ and $ d$ such that $ ca_{i}+da_{j}=0$ and at least one of $ c$ or $ d$ is odd (if they are both even, keep dividing out factors of 2). Then, just add this to our linear combination where all the $ x_{i}$'s are odd, and we'll have an even coefficient somewhere. So we're done.

Actually, it's not necessary to prove that all linear combinations of $ a_i$ are attainable. We can alternatively induct on $ k$ to prove that all linear combinations $ \sum_{i=1}^{k} x_ia_i$ such that all but 2 of the $ x_i$ are even are attainable (this is easily proved by just halving even $ x_i$; actually "all but 1" is sufficient but it's easier to prove "all but 2"). Pick $ a_n$ to be odd, WLOG (obviously they can't be all even). By the condition of the problem $ ((a_1,a_2,\ldots,a_{n-2}, a_{n-1}),a_n)=1$. Let $ G=(a_1,a_2,\ldots,a_{n-2}, a_{n-1})$. Bezout gives $ \sum_{i=1}^{n-1} y_ia_i=G$ for certain $ y_i$. Then $ \sum_{i=1}^{n-1} (2y_i)a_i=2G$ which is still coprime to $ a_n$. Then apply bezout's again and we'll get for some $ p$ and $ q$, $ \sum_{i=1}^{n-1} (2y_ip)a_i+qa_n=1$, and this linear combination is achievable by induction above.

The idea is to show any linear combination of the $a_i$ are in $S$, which implies (by Bezout) that $S = {\mathbb Z}$. This is pretty intuitive, but the details require some care (in particular there is a parity obstruction at the second lemma). First, we make the following simple observations: $0 \in S$, by putting $i=j=1$ in (b). $s \in S \iff -s \in S$, by putting $x=0$ in (c). Now, we prove that: Lemma: For any integers $c$, $d$, and indices $i$, $j$, we have $ca_i + da_j \in S$. Proof. We will assume $c,d > 0$ since the other cases are anologous. In that case it follows by induction on $c+d$ for example $ca_i + (d-1)a_j$, $a_j$, $ca_i + da_j$ in $S$ implies $ca_i + (d+1)a_j \in S$. $\blacksquare$ Lemma: For any nonzero integers $c_1$, $c_2$, \dots, $c_m$, at least one of which is even, and any indices $i_1 < i_2 < \dots < i_m$, we have \[ \sum_k c_k a_{i_k} \in S. \] Proof. By induction on $m$, with base case $m \le 2$ already done. Assume WLOG $c_1 \neq 0$ is even and note that \begin{align*} x &\overset{\text{def}}{=} \frac{1}{2} c_1 a_{i_1} + \sum_{k \ge 2} c_k a_{i_k} \in S \\ y &\overset{\text{def}}{=} -\frac{1}{2} c_1 a_{i_1} \in S \\ x+y &= \sum_{k \ge 2} c_k a_{i_k} \in S \\ \implies x-y &= \sum_{k \ge 1} c_k a_{i_k} \in S. \end{align*}This implies the result. $\blacksquare$ Now by taking $m = n$ in the above, any nontrivial linear combination of the $a_i$ with at least one even coefficient are attainable. So suppose that \[ 1 = \sum_{i=1}^n c_i a_i \]is given by Bezout. The only obstruction possible is if all $c_i$ are either zero or odd, so WLOG the first $k \ge 2$ are odd and the rest are zero (if $k = 1$, then $1 = |a_1| \in S$ already). WLOG again $a_1$ is odd. Then we also have \[ 1 = (c_1 + a_2) a_1 + (c_2 - a_1) a_2 + c_3a_3 + \dots \]which has at least one even coefficient, namely $c_2-a_1 \equiv 0 \pmod 2$.

@v_Enhance sorry I'm a bit confused. In the proof for your second lemma, how do we know that $x$ and $x+y$ are in $S$? Doesn't $x$ include $m$ $a_{i_j}$s instead of less than $m$ for the induction? (Is there an underlying additional induction on $\sum_i |c_i|$ or something like that?) Also, why couldn't all of $c_2, \ldots, c_m$ be odd (against the induction for $x+y \in S$)?

You're correct on both counts, sorry. I'll try to patch it.

Darn. Your finish with the $c_1 a_1 + c_2 a_2 + c_3 a_3 + \cdots \Longrightarrow (c_1 + a_2)a_1 + (c_2 - a_1)a_2 + c_3 a_3 + \cdots$ seemed really cool and clever regardless! I guess something like CatalystOfNostalgia's approach is the same in principle: first get length $m$ sequences with at least one even coefficient $x_{i_r}$ with $x_{i_1} a_{i_1} + x_{i_2} a_{i_2} + \cdots +\frac{x_{i_r}}{2} a_{i_r}$ and $-\frac{x_{i_1}}{2}a_{i_r} - x_{i_{r+1}} a_{i_{r+1}} - \cdots - x_{i_m} a_{i_m}$, both in $S$ by induction (relabeling indices to "cut" at a middle term if $r = 1$ or $r = m$), as well as their sum. For all odd coefficients, realize that such an expression can be expressed in an equivalent form using at least one even coefficient by taking $y_{i_1}, y_{i_2}$ such that $y_{i_1} a_{i_1} = y_{i_2} a_{i_2}$ where $y_{i_1}$ and $y_{i_2}$ are not both even (by canceling factors of $2$ as necessary) and then adding this expression to the all-odd-coefficients expression. (Again, credit to CatalystOfNostalgia above.)

https://imgur.com/a/gCdI1oM

$i=j$ on condition $b$ implies $0\in S$, and condition c implies $y\in S\implies -y\in S$ Use the Euclidean Algorithm (which works because condition b) on $a_1, a_2$ to get that $\gcd(a_1,a_2)\in S$, and then use Euclidean Algorithm on $\gcd(a_1, a_2)$ and $a_3$ to get $\gcd(a_1, a_2, a_3)\in S$, and continue this until we run through all of $a_i$, and get that $\gcd(a_1, a_2, a_3,\dots, a_n)=1\in S$. This means $-1\in S$. Now, we prove inductively (on absolute value) that all integers are in the set. The base case is true, because we proved 0, 1, -1 are in the set. Assume for some $n$, all integers with absolute value less than $n$ are in $S$. Then, $n\in S$ because $-1, n-1, n-2\in S$ and we just plug in $x=n-1$, $y=-1$ into condition c. This also implies $-n\in S$, which means the induction is complete and $S=\mathbb{Z}$

i have a solution using strong induction but i cant write it properly in here bc i dont know latex but i can give hints if anyone is interested

ok i kinda learned latex and im writing my solution , first we induct on n for base $n=2$ is trivial so lest just say we want to solve it with $n$ knowing that $n-1$ is correct since at least 1 of $a_i$ is not even we say like $a_n$ is odd now by induction if we say $GCD(a_2 , a_3 , ... , a_n) = d$ we know that we have every number $x$ in $S$ such that $d|x$ now we have that $a_1 - a_i$ is in $S$ and we have that $m a_1 - n a_i$ is in $S$ for for integer $m,n$ now we know that $m a_1 - n a_2$ and $(d-m)a_1 - t a_3 $ is in $S$ and since the difference is devided by $d$ we have that $(2m-d)a_1 - na_2 - ta_3$ is in $S$ we can say with induct that $[2^i m - (2^i -1)d]a_1 -(W)$ such that $i=n-2$ and $W$ is a linear combination of $a_2 , a_3 , ... , a_n$ hence we can just say $W=dk$ for an integer $k$ so we have $ 2^i a_1 - dk$ is in $S$ and since $a_n$ was odd so $d$ cant be even so we have $ GCD(2^i a_1,d)=1$ so there exists a linear combination of these 2 such that $2^i a_1 x + dy =1$ so we have that $T 2^i a_1 x + Tdy = T$ is in $S$ for any integer $T$ so we have that all integers are in $S$ so we are done

Call the sequence $\{a_1,a_2,\dots a_n \}$ an "ancestral sequence" of $S$ Let $Q(a_i,a_j)$ and $P(x,y)$ denote the second and the third conditions respectively First, some basic remarks :- 1. $Q(a_i,a_i) \implies 0 \in S$ 2.$P(0,x) \implies x\in S \implies -x \in S $ 3.$P(x,y),P(x,-y) \implies x+y \in S \iff x-y \in S $ CLAIM : $2a_i-a_j \in S$ Proof : $P(a_j-a_i,a_i) \implies a_j-2a_i \in S \implies 2a_i-a_j \in S$ CLAIM: If $\{x_1,x_2, \dots ,x_n \} $ is an ancestral sequence of $S$ , then so is the sequence $\{x_1,x_2-x_1, \dots ,x_n-x_1\}$ Proof: This follows from the previous claim due to the fact that gcd of the numbers remains unchanged in the algorithm (say , by the Euclidean algorithm) Now assuming WLOG that $|a_1|$ is minimal , if we repeat the algorithm, we will eventually reach a stage when $a_1=0$ . We can then repeat the algorithm for the next $n-1$ numbers. Hence we will eventually reach the sequence $$\{ \underbrace{0,0,\dots,0}_{n-1 \text{ zeroes}},1 \}$$ So $1,-1 \in S$ . Now we can use strong induction based on the fact that $n-1 \in S \implies n+1 \in S$ (this is the 3rd basic remark) and also the second basic remark ensures that we can focus on only naturals Hence , done

This is a pretty cool problem and definitely one that requires great care.

Fix $n$. We use strong induction on $\mu = |a_1| + |a_2| + \cdots + |a_n|$. $i=j$ in (b) gives $0 \in S$ and $x=0$ in (c) gives $-y \in S$ whenever $y \in S$. In general, if $y \in S$, then an easy induction (on $k$) gives $ky \in S ~ \forall ~ k \in \mathbb Z$. This resolves all the cases when some $a_i$ equals $1$. In particular, this resolves all base cases of $\mu \le n$. Now we do the inductive step. Assume $\mu > n$. Note $a_i,-a_j \in S$ and $a_i - a_j \in S$ implies $a_i + a_j \in S$. So we may change negative $a_i$'s to $-a_i$, so that all $a_i$'s are non-negative (this preserves all conditions and doesn't increase $\mu$). WLOG $a_1$ be the smallest non-zero $a_i$ and $a_n = \max(a_1,\ldots,a_n)$. Note $a_1 \ne a_n$, as otherwise all positive $a_i$'s are equal, and $\gcd$ condition would force all of them to equal $1$, contradicting $\mu > n$. Now change $a_n \to a_n - 2a_1$. This easily preserves $\gcd$ condition. Also, $x=-a_1,y=a_1 - a_n$ gives $a_n - 2a_1 \in S$. So (a) is also preserved. (c) is preserved by definition. It suffices to show $(b)$ is preserved. So we want to show $a_n - 2a_1 - a_j \in S$. Just take $x=a_n - a_1, y = a_i + a_j$. Lastly, as this decreases $\mu$, so we are done by induction hypothesis. $\blacksquare$

We will show that any linear combination of the $a_i$ is in $S$, so $S=\mathbb{Z}$ by Bezout's Lemma. First note that $a_1-a_1=0 \in S$, so for any $x \in S$, we have $0,x,0+x \in S \implies -x \in S$. I will now prove the following preliminary claim: Claim: $ca_i+da_j \in S$ for all $c,d \in \mathbb{Z}$. Proof: This follows by strong induction. I don't feel like writing out the details. To extend this to any number of elements, we will use strong induction again. I will first prove that for $m \geq 3$ indices $i_1,\ldots,i_m$, $c_1a_{i_1}+\cdots+c_ma_{i_m} \in S$ by strong induction (the base case has already been proven). I will first prove it in the case that one of $c_1,\ldots,c_m$ is even. WLOG let $i_1=1,\ldots,i_m=m$, and $c_1$ even. Then, \begin{align*} \frac{1}{2}c_1a_1+\sum_{i=3}^m c_ia_i &\in S\\ -\frac{1}{2}c_1a_1-c_2a_2 &\in S\\ -c_2a_2+\sum_{i=3}^m c_ia_i &\in S\\ \implies c_1a_1+\sum_{i=3}^m c_ia_i+c_2a_2=\sum_{i=1}^m c_ia_i &\in S. \end{align*}Note that the first expression has $m-1$ terms, the second $2$, and the third $m-1$. To extend to all odd indices, "un-WLOG" everything and pick $1 \leq x<y \leq m$ such that $x \neq y$. Let $p,q$ be the minimal positive integers such that $pc_x=qc_y$, so $p,q$ are not both even. Then if $p,q$ are both odd let $c_x,c_y$ be arbitrary evens and the rest odds, so $$c_1a_{i_1}+\cdots+c_xa_{i_x}+\cdots+c_ya_{i_y}+\cdots+c_ma_{i_m}=c_1a_{i-1}+\cdots+(c_x-p)a_{i_x}+\cdots+(c_y+q)a_{i_y}+\cdots+c_ma_{i_m} \in S$$and since we can pick everything arbitrarily it follows that all choices of $c_i$ all odd work as well. The case where one is even (WLOG $p$) and the other odd is similar, where we let $c_y$ be even and $c_x$ odd. This completes the induction, so we're done. $\blacksquare$

I'm a bit surprised that no one has pointed out the similarity between this and 2012 N1 yet.

Sketches are sketchy: Note that picking $i=j$ for criteria $(b)$ shows that $0\in S$. Now, if $i\in S$ then set $x=0,y=i$ for criteria $(c)$ to get that $-i\in S$. If $y\in S$ then $-y\in S$, so $x+(-y)\in S\implies x-(-y)=x+y\in S.$ $~$ Now, since $x-x\in S$, $x+x\in S$ and by induction $kx\in S$ for all $x\in S$ and $k\in \mathbb Z$. Now, if $x-y\in S$ then from similar logic $kx-y\in S$ and so $kx+ly\in S$ by induction. $~$ Since $a_1,a_2,\dots, a_n$ are coprime, there exist numbers $b_1,\dots, b_n$ such that $b_1a_1+b_2a_2+\dots + b_na_n=x$ for each $x\in \mathbb Z.$ From similar logic as above, we can get $b_1a_1+b_2a_2+\dots + b_na_n=x.$ Thus, we are done.

First, get some easy stuff out of the way. Part (b) with $i = j$ tells us $0 \in S$. Setting $y = 0$ in part (c) tells us that $x \in S \Longrightarrow -x \in S$. The central claim of this problem is Claim: Linear combinations of the form $$c_1a_1 + c_2a_2 + \cdots + c_na_n$$can be achieved if at least $n - 2$ of the $c_i$'s are even. Proof: We can induct on $n$. The base case is showing that $c_1a_1 + c_2a_2$ can be achieved for any $c_1, c_2$. We will now do an inner induction on $M = |c_1| + |c_2|$. The base case of $M = 0$ and $M = 1$ were handled earlier. Consider targeting $(c_1, c_2)$ where $|c_1| + |c_2| = M$, with $c_1 \ge 1$. Then, we know $$(c_1 - 1)a_1 + c_2 a_2 \in S \qquad a_1 \in S \qquad (c_1 - 2)a_1 + c_2a_2 \in S$$because $|c_1 - 2| < |c_1|$ due to $c_1 \ge 1$ assumption. So, using (c), we get $c_1a_1 + c_2a_2 \in S$, for $c_1 \ge 1$. We can cover the $c_1 \le -1$ case by using the fact $x \in S \Longrightarrow -x \in S$. And, if $c_1 = 0$, replicate the proof but replace $c_1$ with $c_2$. Note that while we proved $c_1a_1 + c_2a_2 \in S$, we can generalize this proof to show $c_ia_i + c_ja_j \in S$ for any $i, j$. So the base case for the induction on $n$ is handled. Let's now suppose $c_{i_1}a_{i_1} + \cdots + c_{i_{k-1}}a_{i_{k-1}}$ can be achieved at least $k - 3$ of the $c$'s are even. Let us try to achieve $c_1a_1 + c_2a_2 + \cdots + c_ka_k$ where $c_3$ through $c_k$ are even. We can get the following \begin{align*} x &= c_2a_2 + \cdots + c_{k-1}a_{k-1} + \frac{c_k}{2}a_k \\ y &= c_1a_1 + \frac{c_k}{2} a_k \\ x - y &= -c_1a_1 + c_2a_2 + \cdots + c_{k-1}a_{k-1} \end{align*}we know that $x \in S$ by induction, because $c_3$ through $c_{k-1}$ are even. We know $y \in S$ by our base case earlier for $n = 2$. And, we know $x - y \in S$ again by induction. Therefore, $x + y \in S$, meaning $c_1a_1 + \cdots + c_ka_k \in S$, as desired. $\Box$ Now it remains to show a generalized version of Bezout's, where if $a_1$ through $a_n$ are relatively prime, $c_1a_1 + \cdots + c_na_n$ can hit all positive integers $n$ with at least $n - 2$ of the $c_i$'s even. Let $z$ be any positive integer. By Bezout's we know that there exists some $d_1$ through $d_n$ such that $$d_1a_1 + d_2a_2 + \cdots + d_na_n = z$$where some of these $d_i$ might be odd. Let's say $a_1$ is odd, WLOG. For each odd $d_i$, we can replace $d_i$ with $$(d_1 + a_i)a_1 + d_2a_2 + \cdots + (d_i - a_1)a_i + \cdots + d_na_n$$which means for any $i \neq 1$, we can make $d_i$ even. So there exists a linear combination of $a_i$ that achieves $z$ with at least $n - 1$ even coefficients. This is certainly better than $n - 2$. Remark: If we think about just the coefficients $c_1$ through $c_n$ without semantically considering that $a_1$ through $a_n$ are numbers (i.e., just treating $a_1,\ldots, a_n$ as "symbols"), then we can actually show that the coefficients that are achievable must have at least $n - 2$ evens. The reasoning is simple. By rules (a) and (b), everything there has at least $n - 2$ even coefficients, namely $0$. In part (c), if you were somehow able to get $x - y$ to be some expression with less than $n - 2$ evens, then $x + y$ itself must have already had less than $n - 2$ evens. A classic infinite descent. This means that solutions that claim to be able to generate all linear combinations of $a_1$ through $a_n$ wouldn't be correct unless they take into account the semantic information that $a_i$ themselves are actually integers with some value.

Proceed by induction. I claim that for any $x, y \in {a_i}$ we can obtain the multiples of $\gcd(x,y)$. However this might require rewriting some of the rules here. Observe that $0$ is always in $S$. Therefore if $x$ is in $S$, so is $-x$. Henceforth focus on positive integers only, so condition (c) rewrites to two conditions: (c1) For any integers $x, y \in S$, if $x+y \in S$ then $|x-y| \in S$. (c2) For any integers $x, y \in S$, if $|x-y| \in S$ then $x+y \in S$. Now condition $b$ gives us a starting point to work with; consider the starting integers $x$ and $y$, and assume WLOG $x > y$. Observe that $x-y \in S$ and that $x-y + y \in S$. Therefore we can just take their non-negative difference and then the process repeats again. However this is precisely the Euclidean Algorithm so we end up with $\gcd(x,y) \in S$. From here it is not hard to show that if $K$ is in $S$, then $nK$ is as well. Simply note that $K - K \in S$ and induct. Thus the claim is proven. Bring back negative integers to make things easy again. Now suppose that for any $n \ge 2$ integers $a_1, a_2, \cdots a_n$ we can obtain their GCD. I claim that for $n+1$ we can do the same. WLOG we can assume that the GCD of the $n+1$ integers is $1$ (but not the $n$ integers.) Now, for every subset of $n$ integers of the set of $n+1$ integers, we can obtain the multiples of their GCDs. Now observe that pairwise these GCDs must be relatively prime, as otherwise the whole set would have a GCD greater than one. Therefore pick three of these, say $A$, $B$, and $C$. Now observe that $A+Bx=Cy$ has a solution in integers with $\gcd(Bx,A)=1$ by simply taking $\pmod{A}$. Thus we find two integers where the Euclidean Algorithm can be performed (a la proof of $n=2$) to get $1 \in S$, and from there the rest is trivial.

Does this work? I wrote it up sloppily; took me 10 minutes so im not sure why this would be 20 mohs if i solved it that quickly Use an algorithm as follows: From c) we have $a_i-a_j,a_j,a_i\in S\rightarrow a_i-2a_j\rightarrow a_i-ka_j,a_j;a_i-{k-1}a_j\in S\rightarrow a_i-(k+1)a_j\in S;a_i-ka_j,a_i-(k+m)a_j,a_i-(2k+2)a_j\in S\rightarrow ma_j\in S;a_i-a_j,a_k-a_i,a_k-a_j\in S\rightarrow 2a_i-a_j-a_k\in S$ and this easily generalizes to any linear combination of the variables; by Bezout's, we're done.

Its easy to see that $a_i + ka_j \in S$ and then $k_1a_i + k_2a_j \in S$. We use induction. Assume $$k_2a_2 + k_3a_3\dots k_{c}a_{c}, k_1a_{1} + k_2a_{2}\dots +k_{c-1}a_{c-1} \in S$$Then since $k_1a_1 - k_ca_c\in S$, we have $$-k_1a_1 + k_2a_2 + k_3a_3+\dots +2k_{c}a_{c} \in S.$$ This induction can reach all sums such that at most $n-1$ summands have even coefficents. Since there must exist an odd element, we should chose the sum so the $n-1$ other elements are all even coefficents. Then we can write this as $$k_1a_1 + \frac{k_2}{2^{d_2}} (a_2 \cdot 2^{d_2}) + \frac{k_3}{2^{d_3}} (a_3 \cdot 2^{d_3})\dots,$$where $k_1$ is odd and $d_i \leq v_2(k_i)$. Now by bezout, since $\frac{k_i}{2^{d_i}}$ can range over $\mathbb{Z}$ and since $\gcd(a_1, a_2 \cdot 2^{d_2}, a_3 \cdot 2^{d_3} \dots) = 1$ we have $S=\mathbb{Z}$.

Claim: $0 \in S$, and $a \in S \iff -a \in S$. Proof. The first result follows by setting $i = j$. Then taking $x = 0$, $y = a$ for (c) gives the second result. $\blacksquare$ It follows that $a_i + a_j \in S$. Claim: We can inductively get $c_1 a_{i_1} + c_2 a_{i_2} + \dots + c_n a_{i_n} \in S$ Proof. This follows immediately for $n = 1$ as since if $ka, (k+1)a \in S$ then $(k+2)a \in S$. Then since $a_i + a_j \in S$, taking $x = c_1 a_i + c_2 a_j \in S$ for $c_1, c_2 \ge 1$ and $y = a_i$ gives $(c_1+1) a_i + c_2 a_j \in S$. Repeating this gives that $c_1 a_i + c_2 a_j \in S$ for all nonnegative $c_1, c_2$. To construct general $c_1, c_2$, we can subtract $x = (N + c_i)a_i + (N + c_j)a_j$ and $y = Na_i + Na_j$ for $N \ge |\max\{c_i, c_j\}|$. Now, suppose that this holds for $n \ge 2$. Then $((c_1+1) a_{i_1} + c_2 a_{i_2} + \dots + c_n a_{i_n}) - (c_1 a_{i_1} - c_{n+1} a_{i_{n+1}}) \in S$. $\blacksquare$ Since $\gcd(a_1, a_2, \dots, a_n) = 1$, any integer can be expressed as a linear combination as desired.

A solution without using induction and without using bezout

Notice that $0 \in S$, so inductively $na_i \in S$ for any $n \in \mathbb Z$. Now I show inductively that any linear combination of $k \leq n$ of the $a_i$ with at least one coefficient even is in $S$. For the base case $k = 2$, note that $a_i + a_j \in S$, which implies that $d_1a_i + a_j$ and $d_1a_i$ are both in $S$ for any $d_1$. These two conditions imply $d_1 a_i + d_2a_j \in S$ for any $d_1, d_2$. For the inductive step, WLOG the coefficient of $a_k$ is guaranteed to be even. Write $d_1a_1 + d_2a_2+ \cdots + d_ka_k \in S$, where $d_k$ is our even coefficient forced in the $k$-sum, and $d_ka_k + d_{k+1}a_{k+1} \in S$. So $$d_1a_1+d_2a_2+\cdots+d_{k-1}a_{k-1}+2d_ka_k + d_{k+1}a_{k+1} \in S,$$where the sum still covers all possible linear combinations. $\blacksquare$ Now, I claim that there exists a valid linear combination as described above that sums to $1$. There exists a term $a_i$ that is odd by the GCD condition; thus, fix some $j \neq i$ and consider all possible linear combinations with the coefficient of $a_j$ even. There exists an $n$-tuple $(c_1, c_2, \dots, c_n)$ such that $$c_1a_1+c_2a_2+\cdots+c_na_n = 1$$by Bezout. If $c_j$ is even, we're done; if $c_j$ is odd, replace $c_j$ with $c_j + a_i$ and $c_i$ with $c_i - a_j$. Thus, taking multiples of this $1 \in S$ yields $S = \mathbb Z$.

HamstPan wrote: If $c_j$ is even, we're done; if $c_j$ is odd, replace $c_j$ with $c_j + a_i$ and $c_i$ with $c_i - a_j$. Can this argument be replaced by this argument ? If $a_i$ is odd then consider $j \not = i$ So $\text{gcd}(a_1,a_2,\cdots 2a_j,\cdots,a_i,\cdots ,a_n)$ remains $1$ so by bezout we can find a linear combination $(c_1,c_2,\cdots,c_n)$ such that $c_1a_1+\cdots c_j2a_j+\cdots+c_ia_i+\cdots+c_na_n=1$ and we can easily reach it by your algorithm .

HoRI_DA_GRe8 wrote: HamstPan wrote: If $c_j$ is even, we're done; if $c_j$ is odd, replace $c_j$ with $c_j + a_i$ and $c_i$ with $c_i - a_j$. Can this argument be replaced by this argument ? If $a_i$ is odd then consider $j \not = i$ So $\text{gcd}(a_1,a_2,\cdots 2a_j,\cdots,a_i,\cdots ,a_n)$ remains $1$ so by bezout we can find a linear combination $(c_1,c_2,\cdots,c_n)$ such that $c_1a_1+\cdots c_j2a_j+\cdots+c_ia_i+\cdots+c_na_n=1$ and we can easily reach it by your algorithm . Yes this makes it super simple, and it works too. @HamstPan38825 It is my request to add this modification into your solution. Your solution is by far the best among the ones I have read but this modification makes it super simple to understand. I felt that the final line was a bit unmotivated but this addition makes it very instructive.

billzhao wrote: Suppose $a_1, \dots, a_n$ are integers whose greatest common divisor is 1. Let $S$ be a set of integers with the following properties: (a) For $i=1, \dots, n$, $a_i \in S$. (b) For $i,j = 1, \dots, n$ (not necessarily distinct), $a_i - a_j \in S$. (c) For any integers $x,y \in S$, if $x+y \in S$, then $x-y \in S$. Prove that $S$ must be equal to the set of all integers. First of all we start of with an observation that $0 \in S$ which means that. Claim 1: For all $a \in S $ we have that $-a \in S $. Since $0 \in S$ then by (c) as $0+a=a \in S$ then $0-a=-a \in S$. Claim 2: For any $a \in S $, then all of the multiples of $a$ are in $S$ as well. Suppose that $(k-1)a\in S$ and $(k-2)a\in S$. Since $0,a\in S$, we get $-a\in S$. Therefore, we get $ka\in S$ Claim 3: For any integers $d_1,d_2$ and $i,j$ we have that $d_1a_i+d_2a_j \in S$. Assume that $d_1,d_2$ are positive as it's similar if they are negative. Inductively if we have $d_1a_i+d_2a_j, a_j, d_1a_i+d_2a_j \in S$ then $d_1a_i+d_2a_j \in S$. Now let's generalize Claim 3. Claim 4: For any $d_1,d_2, \dots , d_n$ we have that $d_1a_1 + d_2a_2 + \dots + d_na_n \in S$ We will proceed with induction, we proved the base case in Claim 2, Now assume for some $m$ our claim is true, namely. \[d_2a_2+ \dots + d_ma_m \in S\]Now assume WLOG $d_1 \neq 0$ is even then we have $$ x = \frac{1}{2} d_1 a_{1} + \sum_{k \ge 2} d_k a_{k} \in S.$$$$ y = -\frac{1}{2} d_1 a_{1} \in S $$$$ \implies x+y = \sum_{k \ge 2} d_k a_{k} \in S $$$$ \implies x-y = \sum_{k \ge 1} d_k a_{k} \in S.$$But Now assume that all $d_i$ are either zero or odd then replace $d_1$,$d_2$ with the following. \[(d_1+a_i)a_1+a_2+ \dots + (d_i-a_1)a_i+ \dots + a_n \]Making at least one of them being even. Now by Bezout lemma we have some linear coefficients such that. \[d_1a_1+ \dots d_na_n=1\]Since $gcd(a_1,a_2, \dots, a_n)=1$. So this means that $1 \in S$, by \textbf{Claim 2} we have that all the multiples of $1$ are in $S$ as desired

Clearly, if $a$ is in $S$, then all multiples of it also are, since $-a$ also is and then $x=ka,y=-a$. Main Claim: Starting with $a_1,\dots a_n$ and all their pairwise differences, we can reach all linear combinations of $a_1,\dots a_n$. We start with $n=2$. Represent linear combinations as lattice points in the plane. We have $(0,0),(1,0),(0,1),(1,-1),(-1,1)$. Of course we also get $(-1,0)$ and $(0,-1)$. Reflecing $(-1,1)$ across $(0,1)$ gives $(1,1)$, and of course we can also get $(-1,-1)$. Now, we have a 3x3 square. To add another layer to it, point a vector from any point in the layer surrounding it to the closest point in the grid, clearly both the reflection and the vector itself lies in the grid, so that point is also in the set. Repeating this procedure gives us all lattice points. Now we induct on $n$. Assume that $n\geq 3$ and that this is true for $n-1$. Place linear combinations as lattice points in $n$-dimensional space. We know by induction hypothesis that any point with at least one coordinate of zero is in the set. The idea is to consider $$x=(0,a,b,whatever),y=(c,0,-b,whatever).$$Clearly, $x$, $y$, and $x+y$ are all in the set, as they have at least one zero coordinate. However, $x-y=(-c,a,2b,whatever)$. In particular, this reaches any point where the third coordinate is even. Analogously, we can reach any point with at least one even coordinate. However, consider a point with odd coordinates, and suppose that $\frac{a_1}{a_2}=\frac{m}{n}$ for relatively prime positive integers $m$ and $n$. Increase the coefficent of $a_1$ by $n$ and decrease the coefficent of $a_2$ by $m$. Since $m$ and $n$ are not both even, said point is then equal to some point that has at least one even coordinate. Thus, we can reach all values that are linear combinations of the $a_i$. Thus, since the gcd is $1$, we are done. Remark: For $n\geq 3$, an argument that linear combinations with some even coordinate actually covers everything is necessary. This is because the set of "all points with any even coordinate" is a solution. -Clearly this set contains all points with one $1$ and all other $0$s, as well as one $1$, one $-1$, and all other $0$s (as $n\geq 3$). -If $x+y$ has an even coordinate, then so does $x-y$, as they have the same parity. Because of this, a solution with this argument must then argue that "all points with any even coordinate" manages to cover all linear combinations anyways. Fortunately, this is not hard to do by just toggling two coefficents.