自然数シリーズ① ~鳩ノ巣論法の紹介~ | 東進ハイスクール柏校|千葉県

ブログ

2013年 8月 7日 自然数シリーズ① ~鳩ノ巣論法の紹介~

 こんにちは!柏校担任助手の松尾です。これから何回かに分けて、「自然数」について扱っていきます。文系の僕が書くのはいささか恐縮ですが(笑)

 

 早速ですが、これを読んでくれている皆さんに宿題です。答えはこのシリーズの最後で紹介します。

  (問)自然数を「数学的にキチンと」定義してください。

 「数学的にキチンと」というのは要するに“1,2,3,4…”みたいに“…”を使わないで、という意味です。それから漸化式もなしです。漸化式って結局は“…”と同じ意味なので。

 

 

 さてさて、本題に移りましょう。今回は自然数の性質から得られる論法として、数学的帰納法と同じくらい重要なのにあまりとりあげられない「鳩ノ巣論法」について紹介します。

  鳩ノ巣論法とは、「a個の巣にb羽の鳩が入るとき、a<bならば必ず複数羽の鳩が入る巣が存在する」というものです。一見当たり前のようですが、この考え方が重要なのです。いくつか例題を見てみましょう。

  

 (1)自然数m,nに対してm÷nを計算する時、割り切れなかったならばこの値は必ず循環小数として表示できる。なぜ?

 〈証明〉m÷nという割り算を実際に計算すると、余りは0,1,2,3…n-1のn通りある(これが鳩の巣)。したがって、割り算をn+1回行うと(筆算のイメージでどうぞ。ちなみにこれが鳩)、必ず同じ余りが出てくる。同じ余りからは同じ商が得られるから、そこから先は繰り返しで、循環する。 q.e.d.

 

  (2)任意に与えられた相異なる4つの自然数の中から適当に2つを選ぶとき、その差が3の倍数になるものが必ず存在することを証明せよ。

 〈証明〉4つの数をそれぞれ3で割った余りをp,q,r,sとする(これが鳩)。ところで、整数を3で割った余りは必ず0,1,2のいずれかなので(これが鳩の巣)、p,q,r,sの中には少なくとも2つ、同じものが存在する。その2つについて差をとれば、その差は3の倍数になる。 q.e.d

 

 ちなみにこの(2)の類題が昔早稲田大学で出題されています。今回は問題だけ紹介します。答えは次回のお楽しみです。

 

(問)相異なるn+1個の整数か適当に2つを選ぶと、その差が、nの倍数になるものがあることを証明せよ。

  

どうでしょうか。最初は「なんだこれ」と思った方もいたでしょうが、意外と応用の利く論法だと思いませんか?

 

次回は、早稲田大学の過去問を解説した後、この定理の原理を「集合論理」の視点から説明しようと思います。「集合論理」には全射とか単射という独特な言葉も出てくるので、その辺りも簡単に説明しようと思います。では、また次回!!