記一道數(shù)論題（IMO的），這道題難度不大但是有點意思。
題目：任意給定整數(shù)\(k_1...k_n\)（\(n\)是正奇數(shù)），定義\(F(a)\)（a為\(1...n\)的排列）\(=\sum_{i=1}^nk_ia_i\)。
證明：存在\(c,d\)，\(S(c)\equiv S(d)(\mod n!)\)。設(shè)所有\(1...n\)的排列構(gòu)成集合\(T\)。
\(n=1\)時顯然。假設(shè)\(n>1\)，考慮反證法，假設(shè)不存在存在\(c,d\)使得\(S(c)\equiv S(d)(\mod n!)\)。
那么由于排列有\(n!\)個，它們對\(n!\)取模的結(jié)果只可能是\(0,1,...n!-1\)，所以定義\(G(a)=F(a)\)對\(n!\)取余的結(jié)果，對于所有\(0\leq x<n!\)，只存在恰好一個排列\(a\)使得\(x=G(a)\)。
考慮計算\(\sum_{a\in T} F(a)\). 考慮每個位置\(j\)的貢獻。對于所有排列，\(k_i\)放在位置\(j\)有\((n-1)!\)種情況，權(quán)值為\(k_ij(n-1)!\)
所以\(\sum_{a\in T} F(a)=(\sum_{i=1}^n)(\sum_{i=1}^n)k_ij(n-1)!=(\sum_{i=1}^n k_i)(n-1)!\frac{n(n+1)}{2}\)
而由于對于所有\(0\leq x<n!\)，只存在恰好一個排列\(a\)使得\(x=G(a)\)。所以\(\sum_{a\in T} G(a)=n!\frac{(n!-1)}{2}\)
而且根據(jù)\(G\)的定義，我們知道\(\sum_{a\in T} F(a)\)對\(n!\)取余的結(jié)果和\(\sum_{a\in T} G(a)\)相同，所以\(n!\frac{(n!-1)}{2}\equiv(\sum_{i=1}^n k_i)(n-1)!\frac{n(n+1)}{2} \mod n!\)
由于\(n\)是奇數(shù)，\(\frac{n+1}{2}\)是整數(shù)，所以存在\(\frac{n+1}{2}\)使得\(\frac{n+1}{2}n!(\sum_{i=1}^n k_i)=(\sum_{i=1}^n k_i)(n-1)!\frac{n(n+1)}{2}\)，所以\((\sum_{i=1}^n k_i)(n-1)!\frac{n(n+1)}{2}\equiv 0(\mod n!)\)
所以一定存在整數(shù)\(k\)使得\(kn!=n!\frac{(n!-1)}{2},k=\frac{(n!-1)}{2}\)。由于\(n>1\)，\(n!\)是偶數(shù)，\(n!-1\)是奇數(shù)，所以\(k\)不是整數(shù)，矛盾。