USA IMO

We may as well assume that none of the $a_i$ is equal to $0$. We start with the following observations.

d. $0 = a_1 - a_1 \in S$ by (b).

e. $-s = 0 - s \in S$ whenever $s \in S$, by (a) and (d).

f. If $x, y \in S$ and $x - y \in S$, then $x + y \in S$ by (c) and (e).

By (f) plus strong induction on $m$, we have that $ms \in S$ for any $m \ge 0$ whenever $s \in S$. By (d) and (e), the same holds even if $m \le 0$, and so we have the following.

g. For $i = 1, \dots, n$, $S$ contains all multiples of $a_i$.

We next verify that

h. For $i, j \in \{1, \dots, n\}$ and any integers $c_i, c_j$, $c_i a_i + c_j a_j \in S$.

We do this by induction on $|c_i| + |c_j|$. If $|c_i| \le 1$ and $|c_j| \le 1$, this follows from (b), (d), (f), so we may assume that $\max\{|c_i|, |c_j|\} \ge 2$. Suppose without loss of generality (by switching $i$ with $j$ and/or negating both $c_i$ and $c_j$) that $c_i \ge 2$; then
$$c_i a_i + c_j a_j = a_i + ((c_i - 1)a_i + c_j a_j)$$
and we have $a_i \in S$, $(c_i - 1)a_i + c_j a_j \in S$ by the induction hypothesis, and $(c_i - 2)a_i + c_j a_j \in S$ again by the induction hypothesis. So $c_i a_i + c_j a_j \in S$ by (f), and (h) is verified.

Let $e_i$ be the largest integer such that $2^{e_i}$ divides $a_i$; without loss of generality we may assume that $e_1 \ge e_2 \ge \dots \ge e_n$. Let $d_i$ be the greatest common divisor of $a_1, \dots, a_i$. We prove by induction on $i$ that $S$ contains all multiples of $d_i$ for $i = 1, \dots, n$; the case $i = n$ is the desired result. Our base cases are $i = 1$ and $i = 2$, which follow from (g) and (h), respectively.

Assume that $S$ contains all multiples of $d_i$, for some $2 \le i < n$. Let $T$ be the set of integers $m$ such that $m$ is divisible by $d_i$ and $m + r a_{i+1} \in S$ for all integers $r$. Then $T$ contains nonzero positive and negative numbers, namely any multiple of $a_i$ by (h). By (c), if $t \in T$ and $s$ divisible by $d_i$ (so in $S$) satisfy $t - s \in T$, then $t + s \in T$. By taking $t = s = d_i$, we deduce that $2d_i \in T$; by induction (as in the proof of (g)), we have $2md_i \in T$ for any integer $m$ (positive, negative or zero).

From the way we ordered the $a_i$, we see that the highest power of $2$ dividing $d_i$ is greater than or equal to the highest power of $2$ dividing $a_{i+1}$. In other words, $a_{i+1}/d_{i+1}$ is odd. We can thus find integers $f, g$ with $f$ even such that $f d_i + g a_{i+1} = d_{i+1}$. (Choose such a pair without any restriction on $f$, and replace $(f, g)$ with $(f - a_{i+1}/d_{i+1}, g + d_i/d_{i+1})$ if needed to get an even $f$.) Then for any integer $r$, we have $r f d_i \in T$ and so $r d_{i+1} \in S$. This completes the induction and the proof of the desired result.

(By Tony Zhang) We present a different way of completing the proof after the observing (d) through (h) of the preceding solution. We proceed to prove the following lemma by induction:

Lemma Let $m \ge 2$. For $i_1, i_2, \dots, i_m \in \{1, \dots, n\}$ and $k_{i_1}, \dots, k_{i_m} \in \mathbb{Z}$:
$$(k_{i_1} a_{i_1} + k_{i_2} a_{i_2}) + 2(k_{i_3} a_{i_3} + \dots + k_{i_m} a_{i_m}) \in S.$$
Proof: Observation (h) proves the $m=2$ case, so now assume that the Lemma is true for all $m$ less than or equal to some $r$. Now by induction hypothesis, the following terms are in $S$:
$$(k_{i_1} a_{i_1} + k_{i_{r+1}} a_{i_{r+1}}) + 2(k_{i_3} a_{i_3} + \dots + k_{i_r} a_{i_r}) \in S$$
$$(k_{i_2} a_{i_2} + k_{i_{r+1}} a_{i_{r+1}}) \in S.$$
Yet their difference is
$$(k_{i_1} a_{i_1} - k_{i_2} a_{i_2}) + 2(k_{i_3} a_{i_3} + \dots + k_{i_r} a_{i_r}),$$
which is in $S$ by induction hypothesis, so by observation (f), their sum is in $S$:
$$(k_{i_1} a_{i_1} + k_{i_2} a_{i_2}) + 2(k_{i_3} a_{i_3} + \dots + k_{i_r} a_{i_r} + k_{i_{r+1}} a_{i_{r+1}}),$$
which completes the induction, and the proof of the Lemma.

We apply the Lemma to prove that $1 \in S$; by the comment following observation (f) in the previous solution, this will prove that $S = \mathbb{Z}$. Apply the lemma with $m = n$, $i_1 = 1$, $i_2 = 2$, ..., $i_n = n$. Since we are given that the greatest common divisor of the $a_i$ is $1$, there exist integers $k_1, \dots, k_n$ such that $k_1 a_1 + \dots + k_n a_n = 1$. Since we can't have all $a_i$ even, without loss of generality, assume that $a_1$ is odd. Now let $i$ iterate from $2$ to $n$, and at each stage perform the following operations if $k_i$ is odd:

a. replace $k_i$ with $k_i + a_1$,

b. replace $k_1$ with $k_1 - a_i$.

Note that this preserves the sum $k_1 a_1 + \dots + k_n a_n = 1$, but it makes all the $k_i$ between $2$ and $n$ even; therefore, the lemma applies, and we find that $1 \in S$, as desired.