部屋割論法の理解・整数問題(2)・考察を示します。
考察
n個の自然数を一列に並べたとき、これらの中の連続して並んだ何個かの数の和の中に、nの倍数となるものが必ずあることを部屋割論法で示す。
n個の自然数をa(1),a(2),・・・,a(n)とする。
つぎのようなn+1個の和b(0),b(1),・・・,b(n)を考える。
b(0)=0,
b(1)=a(1),
b(2)=a(1)+a(2),
・・・
b(k)=a(1)+a(2)+・・・+a(k)
・・・
b(n)=a(1)+a(2)+・・・・・・+a(n)
すなわち、b(k)は、a(1)からa(k)までの和と定義する。これらをnで割った余りは、
0,1,・・・,n-1のいずれかとなる。
そうすると、部屋割論法(n個の余り0,1,・・・,n-1がn個の部屋に対応し、n+1個の数b(0),b(1),・・・,b(n)がn+1人の客に対応する)により、
n+1個の数b(0),b(1),・・・,b(n)のうち、少なくとも2つのb(i),b(j)
(b(i)<b(j))において、nで割った余りが等しくなる。
すなわち、b(j)-b(i)(=a(i+1)+・・・+a(j))がnで割り切れる ことになる。
これは、一列中の連続して並んだ何個かの数の和がnで割り切れることを意味する。
以上より、命題が証明された。