Σ[i,j=1～n] |i-j||x[i]-x[j]|=(n/2)Σ[i,j=1～n] |x[i]-x[j]| の証明

１．まえがき

　あるサイトに数列 {x_n} が
　　x₁≦x₂≦x₃≦・・・≦x_n ・・・・①
　を満たすとき

　　Σ_i,j=1～n |i-j| |x_i -x_j |=(n/2)Σ_i,j=1～n |x_i -x_j |・・②
　を証明する問題があった。簡単そうに見えたが面倒だった。

　与式の左辺と右辺を L,Rとする。この Lの各項を(i,j)の行列として
　並べると対角線？の部分が0の対称行列

　　0, 1(x₂-x₁), 2(x₃-x₁), 3(x₄-x₁), 4(x₅-x₁),・・・・・・・, (n-1)(x_n - x₁)
　　_,_______,      0    , 1(x₃-x₂), 2(x₄-x₂), 3(x₅-x₂), ・・・, (n-2)(x_n - x₂)
　　_,______ ,_______,      0     , 1(x₄-x₃),  2(x₅-x₃), ・・・, (n-3)(x_n - x₃)
　　　・・・・・・
　　_,_____ ,_____ ,_____ ,・・・・,_________,      0     , 1(x_n - x_n-1 )
　　_,_____ ,_____ ,_____ ,______ ,・・・・・・・,______,        0

　となる。対角線より下側は同じなので省略。

２．準備１

　|i-j|, |x_i -x_j | ともに、i,j を交換しても値は変わらず、i=j のとき、いずれも 0だから、
　①により、i ＞ j の和を２倍すればよい。つまり

　　L=2Σ_j=1～n-1 Σ_i=j+1～n (i-j) (x_i -x_j)
　同様に
　　R=2Σ_j=1～n-1 Σ_i=j+1～n (x_i -x_j)
　である。

　これらは行ごとの和であるが、k=i-j として対角線ごとの和に変換すると
　　L=2Σ_k=1～n-1 Σ_m=1～n-k  k(x_m+k -x_m)
　　 =Σ_k=1～n-1 (2k) Σ_m=1～n-k (x_m+k -x_m)・・・③

　　R=2 Σ_j=1～n-1 Σ_m=1～n-k (x_m+k -x_m)・・・・④

　となる。②は

　　L=(n/2)R・・・・・⑤
　となり、これを証明すれば良い。

　つまり、Lの和の順序して次のような並びを考える。Rも同様。
　上から k=1,2,・・・,(n-1)に対応する。

　　2(x₂-x₁), 2(x₃-x₂), 2(x₄-x₃),・・・・・・・, 2(x_n -x_n-1)
　　__0__  , 4(x₃-x₁), 4(x₄-x₂), 2(x₅-x₃),・・・ , 4(x_n -x_n-2)
　　____0_________ , 6(x₄-x₁), 3(x₅-x₂),・・・ , 6(x_n -x_n-3)
　　　・・・・
　　______0________________, 2(n-2)(x_n-1 -x₁), 2(n-2)(x_n -x₂)
　　________0_____________________________, 2(n-1)(x_n -x₁)

３.準備２

　ここで、
　　A_k=Σ_m=1～n-k (x_m+k -x_m)・・・・⑥
　とおくと③④は
　　L=Σ_k=1～n-1 (2k)A_k ・・・・⑦
　　R=2Σ_k=1～n-1 A_k ・・・・⑧
　となる。

　つぎに、この A_k ( A₁ からk番目のもの )に対して、最後の A_n-1 から、逆方向に k番目
　のものは⑥で k→ n-k として

　　A_n-k =Σ_m=1～k (x_m+n-k -x_m)　であるが、A_k とA_n-k の差を計算すると

　　A_k -A_n-k=( Σ_m=1～n-k x_m+k -Σ_m=1～n-k x_m )
　　　　　　　　　- ( Σ_m=1～k x_m+n-k - Σ_m=1～k x_m )

　　　（m+k, m+n-k → m のパラメータ変換をすると）

　　　=( Σ_m=k+1～n x_m - Σ_m=1～n-k x_m )
　　　　　- ( Σ_m=n-k+1～n x_m - Σ_m=1～k x_m )
　　　=Σ_m=k+1～n-k x_m - Σ_m=k+1～n-k x_m
　　　=0

　ここで、n-k≧k および (n-k+1)≧k+1 を使った。つまり、
　　A_k=A_n-k ・・・・⑨
　をえる。

４.証明

　⑦の級数の k番目の項は (2k)A_k であり、(n-k)番目の項は 2(n-k)A_n-k であるが、
　後者のうち、(n-2k)A_n-k を k番の項に移動して加える。すると⑨により k番目の項は

　(2k)A_k +(n-2k)A_n-k=nA_k となる。もとの(n-k)番の項は
　nA_n-k となる。つまり、⑦⑧から

　　L=n( Σ_k=1～n-1 A_k )=(n/2)R・・・⑩
　となり、⑤が証明された。

　ここで、nが偶数の時、k=1～(n-1) の真ん中のA_k には、対となる項が存在しない。
　しかし、n=2p とすると 真ん中の項は k=pとなり、2k=2p=n となり、対となる項を
　加える必要も無く⑩が成立する。

以上

複数（０個も含む）の５と７の和で表わせない最大の（０以上の）整数

掲題の問題が電車内に日能研の広告として載っていた。　2010年 城西川越中学校 【算数】の問題
らしいが、証明の解説が理解できなかった。おもしろい問題なので考えてみた。

１．まず、任意の０以上の整数ｎは整数ｍ，ａを使って　ｎ＝５ｍ＋ａ（ｍ≧０，ａ＝０，１，２，
　　３，４）　と表わされる。

２．このとき、ｎが複数の５と７の和で表わされる場合を考える。
　(1)ａ＝０のとき
　　　当然除外できる。
　(2)ａ＝１のとき
　　　ｎ＝５（ｍ－４）＋２０＋ａ＝５（ｍ－４）＋７・３　となるから、ｎ≧２０ならば「２」
　　　は満たされる。

　(3)ａ＝２のとき
　　　ｎ＝５（ｍ－１）＋５＋ａ＝５（ｍ－１）＋７　となるから、ｎ≧５ならば「２」は満た
　　　される。
　(4)ａ＝３のとき
　　　ｎ＝５（ｍ－５）＋２５＋ａ＝５（ｍ－５）＋７・４　となるから、ｎ≧２５ならば「２」
　　　は満たされる。

　(5)ａ＝４のとき
　　　ｎ＝５（ｍ－２）＋１０＋ａ＝５（ｍ－２）＋７・２　となるから、ｎ≧１０ならば「２」
　　　は満たされる。

３．まとめると、ｎが２５以上なら、「２」項はみたされるから、命題が成り立つとすれば２４以下
　　の数である。
　　まず、２４＝５・２＋７・２となって除外できる。２３が求める答えであることは４通りの計算
　　をすれば分かる。

追記(2011/3/20)
　この問題は、３と５の場合で、第10回日本数学オリンピック予選(2000年)に載っていた。証明方法は
　私には難しかった。