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)\mathrm{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 $\mathrm{mod}n!$. Since there are exactly $n!$ such permutations $a$, there exists exactly one permutation $a$ such that $S(a)\equiv s(\mathrm{mod}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)(\mathrm{mod}n!),$$ or $$\sum _{a}S(a)\equiv \frac{n!}{2}(\mathrm{mod}n!).(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+\cdots +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}+\cdots +n{c}_{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 $\left(\genfrac{}{}{0ex}{}{m+1}{\lambda }\right)$ ways to choose $\lambda$ numbers $i_1,i_2,\dots ,i_{\lambda }$ from the set $\{1,3,\dots ,2m+1\}$ and $\left(\genfrac{}{}{0ex}{}{m}{r-\lambda }\right)$ 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)!(\genfrac{}{}{0ex}{}{m+1}{\lambda }\left)\right(\genfrac{}{}{0ex}{}{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 }(\genfrac{}{}{0ex}{}{m+1}{\lambda }\left)\right(\genfrac{}{}{0ex}{}{m}{r-\lambda }),$$ $$O=r!(n-r)!\sum _{2|\lambda }(\genfrac{}{}{0ex}{}{m+1}{\lambda }\left)\right(\genfrac{}{}{0ex}{}{m}{r-\lambda }),$$ and $$E-O=r!(n-r)!\sum _{\lambda =0}^r(-1{)}^{\lambda }\left(\genfrac{}{}{0ex}{}{m+1}{\lambda }\right)\left(\genfrac{}{}{0ex}{}{m}{r-\lambda }\right).$$ 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 }(\genfrac{}{}{0ex}{}{m+1}{\lambda }\left)\right(\genfrac{}{}{0ex}{}{m}{r-\lambda }).$$ On the other hand, $$f(x)=(1-x^2{)}^m(1-x)=\sum _{i=0}^m(\genfrac{}{}{0ex}{}{m}{i})(-1{)}^i{x}^{2i}(1-x)$$ $$=\sum _{i=0}^m\left(\genfrac{}{}{0ex}{}{m}{i}\right)((-1{)}^i{x}^{2i}+(-1{)}^{i+1}{x}^{2i+1}).$$ Therefore, $$[x^r]f(x)=\lfloor \frac{m}{\frac{r+1}{2}}\rfloor \cdot (-1{)}^{\lfloor \frac{r+1}{2}\rfloor }\ne 0,$$ implying that $E-O\ne 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(\mathrm{mod}n!)$. As $n!$ is even, this implies that $E=O$, contradicting that fact $E-O\ne 0$. Thus, we have proven the desired conclusion.