-
![]()
事項
部屋割り論法
※ 「 ・･････ が少なくとも1つ存在する」 ということを証明するのに,
「n室の部屋にn+1人を入れると、2人以上入っている部屋が
少なくとも1室はある。｣
という事実を利用する方法がある。 これを部屋割り論法または鳩の巣原理 という。
例
1から50までの整数の中から相異なる 26個の数をどのように選んでも,和が
51になる2つの数の組が必ず含まれていることを示せ。
指針▷数を 26個選ぶのだから、2つの数の組を25個作るのがポイントである。
解答が 51 になる2つの数の組は、次の25 組ある。
(1,50),(2,49),(3,48),
(25,26)
選んだ26個の数をこの25組に入れると, 2個入る組が少なくとも1つある。
つまり,和が51 になる2つの数の組が必ず含まれている。
例 異なる n +1個の自然数がある。 その中に、2つの自然数の差がnで割り切れ
るような組が少なくとも1組存在する。
指針 自然数をnで割った余りは, 0, 1,2,.. n-1のn通りで,これをn個の部屋と考え
る。 そして, 異なる n + 1個の自然数を n +1人と考えると, 2人以上入っている部屋が少
なくとも1室ある, すなわち, nで割ったときの余りが等しい自然数が少なくとも2個ある。
解答 自然数をnで割った余りは, 0, 1,2,…,n-1のn通りある。
異なる n +1個の自然数の中には,nで割ったときの余りが等しい2つの自然数の
組が少なくとも1組存在する。 余りが等しい2つの自然数を α, b とし, 等しい余
りを
a=np+r, b=ngtr (p, g は整数)
すると
辺々引いて
a-b=n(p-g)
b-g は整数であるから, a-bはnの倍数である。よって、2つの自然数の差がn
で割り切れるような組(α, b) が少なくとも1組存在する。
※部屋割り論法は,次の形でも用いられる。
「人をn個の部屋に入れるとき, 相部屋がなければ,
どの部屋にも1人ずつ人が入っている。｣
この考え方は、 前ページの [ (*) のの証明] の中で利用している。
そこでは, apを6で割った余りをrp (1≦p≦b)とすると
b個の部屋
1,2,, ......, % はすべて互いに異なる。
p は 0 1 2, ......, 6-1のいずれかである。
6人の人
として, 「6人を6個の部屋に入れると, 相部屋がない (すべて異なるから)」と考えると
「どの部屋にも1人ずつ人が入っている」 わけだから, rp (1≦p≦b) は, 0, 1,2,3,
6-1の値の中からそれぞれの値を1つずつとる, ことがいえる。
5
