USA IMO

First Solution. Let $\sum_a$ denote the sum over all $n!$ permutations $a = (a_1, a_2, \dots, a_n)$. We compute $\sum_a S(a) \mod n!$ in two ways, one of which assuming that the desired conclusion is false, and reach a contradiction.

Suppose, for the sake of contradiction, that the claim is false. Then each $S(a)$ must have a different remainder $\mod n!$. Since there are exactly $n!$ such permutations $a$, there exists exactly one permutation $a$ such that $S(a) \equiv s \pmod{n!}$ for each $s = 1, 2, \dots, n!$. Since $n > 1$, $n!$ is even and $n! + 1$ is odd. Hence,
$$\sum_a S(a) \equiv \sum_{s=1}^{n!} s \equiv \frac{n!}{2} \cdot (n! + 1) \pmod{n!},$$
or
$$\sum_a S(a) \equiv \frac{n!}{2} \pmod{n!}. \qquad (1)$$
On the other hand, for $i, k \in \{1, \dots, n\}$, we have $a_i = k$ in exactly $(n-1)!$ permutations $a$. Thus, for $1 \le i \le n$,
$$\sum_a a_i = (n-1)!(1+2+\dots+n) = n! \cdot \frac{n+1}{2}.$$
Hence,
$$\sum_a S(a) = \sum_a \sum_{i=1}^n c_i a_i = \sum_a \sum_{i=1}^n c_i a_i = \sum_{i=1}^n \left( c_i \sum_a a_i \right).$$
Because $n+1$ is even, $n!$ divides $\sum_a a_i = n! \cdot \frac{n+1}{2}$ for each $i$. It follows that $n!$ divides $\sum_a S(a)$, contradicting (1). Therefore, the initial assumption was false, and there do exist distinct permutations $b$ and $c$ such that $n!$ is a divisor of $S(b) - S(c)$.

Second Solution. (by Liang Xiao, China) Let $n = 2m + 1$, and let $r$ be the number of indices $i$ such that $c_i$ is odd. For a permutation $a = (a_1, a_2, \dots, a_n)$ of $\{1, 2, \dots, n\}$, let
$$T(a) = \sum_{i=1}^{n} i c_{a_i} = c_{a_1} + 2c_{a_2} + \dots + nc_{a_n},$$
and let $\lambda_a$ be the number of indices $i$ such that both $i$ and $c_{a_i}$ are odd. Note that $T(a)$ is equal $S(a)$ in a different order.
For any given positive integer $\lambda$, $0 \le \lambda \le r$, we count the number of permutations $a$ of $\{1, 2, \dots, n\}$ with $\lambda_a = \lambda$. There are $\binom{m+1}{\lambda}$ ways to choose $\lambda$ numbers $i_1, i_2, \dots, i_\lambda$ from the set $\{1, 3, \dots, 2m+1\}$ and $\binom{m}{r-\lambda}$ ways to choose $r-\lambda$ numbers $j_1, j_2, \dots, j_{r-\lambda}$ from the set $\{2, 4, \dots, 2m\}$. Once the numbers $i_1, \dots, i_\lambda, j_1, \dots, j_{r-\lambda}$ have been chosen, there are $r!(n-r)!$ permutations $a = (a_1, a_2, \dots, a_n)$ of $\{1, 2, \dots, n\}$ such that $c_{a_{i_1}}, \dots, c_{a_{i_\lambda}}$ and $c_{a_{j_1}}, \dots, c_{a_{j_{r-\lambda}}}$ are all odd. Thus, there are
$$r!(n-r)! \binom{m+1}{\lambda} \binom{m}{r-\lambda}$$
permutations $a$ of $\{1, 2, \dots, n\}$ such that $\lambda_a = \lambda$.

Let $E$ and $O$ be the number of permutations $a$ of $\{1, 2, \dots, n\}$ such that $S(a)$ is even and odd, respectively. Then
$$E = r!(n-r)! \sum_{2|\lambda} \binom{m+1}{\lambda} \binom{m}{r-\lambda},$$
$$O = r!(n-r)! \sum_{2|\lambda} \binom{m+1}{\lambda} \binom{m}{r-\lambda},$$
and
$$E - O = r!(n-r)! \sum_{\lambda=0}^{r} (-1)^{\lambda} \binom{m+1}{\lambda} \binom{m}{r-\lambda}.$$
Denote by $[x^k]h(x)$ the coefficient of $x^k$ in a power series $h(x)$. Let $g_1(x) = (1-x)^{m+1}$, $g_2(x) = (1+x)^m$, and $f(x) = g_1(x)g_2(x)$. Then
$$[x^r]f(x) = \sum_{\lambda=0}^{r} ([x^\lambda]g_1(x)) ([x^{r-\lambda}]g_2(x))$$
$$= \sum_{\lambda=0}^{r} (-1)^\lambda \binom{m+1}{\lambda} \binom{m}{r-\lambda}.$$
On the other hand,
$$f(x) = (1 - x^2)^m (1 - x) = \sum_{i=0}^{m} \binom{m}{i} (-1)^i x^{2i} (1 - x)$$
$$= \sum_{i=0}^{m} \binom{m}{i} ((-1)^i x^{2i} + (-1)^{i+1} x^{2i+1}).$$
Therefore,
$$[x^r]f(x) = \left\lfloor \frac{m}{\frac{r+1}{2}} \right\rfloor \cdot (-1)^{\left\lfloor \frac{r+1}{2} \right\rfloor} \neq 0,$$
implying that $E - O \neq 0$.
In order for the desired result to be false, for each number $i$ from $1$ to $n!$, there must be exactly one permutation $a$ of $1, 2, \dots, n$ such that $S(a) \equiv i \pmod{n!}$. As $n!$ is even, this implies that $E = O$, contradicting that fact $E - O \neq 0$. Thus, we have proven the desired conclusion.