パズル万華鏡

面白いパズルの紹介と解説をします。

部屋割論法の理解・整数問題(2)・考察

 部屋割論法の理解・整数問題(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で割り切れることを意味する。

以上より、命題が証明された。

f:id:isemba:20190701164756j:plain