MathLabs

Problem 4

Let n>1 n>1 be an odd integer and let k1,k2,…,kn k_1,k_2,\dots,k_n be integers. For each permutation a=(a1,…,an)\mathbf a=(a_1,\dots,a_n) of 1,…,n1,\dots,n , define S(a)=∑i=1nkiai S(\mathbf a)=\sum_{i=1}^n k_i a_i . Prove that there are distinct permutations b,c\mathbf b,\mathbf c such that n! n! divides S(b)S(c) S(\mathbf b)S(\mathbf c).
Step 2 of 4: Assume distinct residues
Previous stepNext step
{S(a) mod n!}={0,1,…,n!−1}.\{S(\mathbf a)\bmod n!\}=\{0,1,\dots,n!-1\}.
Detailed analysis

If the desired pair did not exist, the n factorial residues would all be distinct.