スポンサーリンク

【鳩の巣原理】(部屋割り論法)整数問題

数学(大学入試問題)

【問題①】

366 人の中には、誕生日が同じ 2 人が少なくとも 1 組以上存在することを証明せよ.

※うるう年は考えないものとする.

【問題②】

「 1 , 2 , 3 , ・・・ , 100 から 51 個の異なる自然数を選ぶと、互いに素な数が必ず存在する 」

ことを証明せよ.

【問題③】

「空間内に与えられた \(n\) 個の格子点の間を結ぶ線分を考える.このとき、これらの線分の中点の少なくとも 1 つは格子点である」

\(n\) として、どんな自然数を考えれば、上の命題は常に正しいか.適当な \(n\) を 1 つあげ、その理由を説明せよ.

ただし、格子点とは、\(x , y , z\) がすべて整数であるような点 \(( x , y , z )\) のことである.

はじめに

鳩の巣原理(部屋割り論法)という言葉を聞いたことがありますか?

原理や論法と聞くと難しく聞こえるかもしれませんが、すごく当たり前の簡単な考え方です。しかし、一度どこかでしっかりと扱っておかないと、いざ本番でこのような発想を持つことは非常に難しいです。

上の3題を使って、鳩の巣原理を理解しましょう。

 

鳩の巣原理(部屋割り論法)

\(m, n \) は自然数で、\(m<n\) を満たすとする.

\(n\) 個のものを、\(m\) 組に分けるとき、少なくとも 1 組は 2 個以上になる

簡単な例で言うと、

 5 匹の鳩に対して、巣が 4 つしかなかったら、どれかの巣には 2 匹以上の鳩が入っているってことです!

もちろん 5 匹の鳩すべてが同じ巣に入っっているかもしれませんし、 2 匹と 3 匹ずつに分かれているかもしれません。どのような状況になっているはわからないけど、鳩の巣原理で言いたいのは、絶対に、「少なくとも 1 つの巣に 2 匹以上の鳩がいると言うこと」です。

このことを踏まえて、問題を考えてみましょう!

 

【問題①】について

366 人の中には、誕生日が同じ 2 人が少なくとも 1 組以上存在することを証明せよ.

※うるう年は考えないものとする.

【問題①】については、鳩の巣原理を理解すれば当たり前なのがわかりますか?

・鳩 ⇒ 366 人

・巣 ⇒ 365 日

と考えると、誰か 2 人は誕生日が重なるよねって言う話です。

すごく当たり前のことだ!と思ってくれたらそれでOK!!

 

【問題②】

「 1 , 2 , 3 , ・・・ , 100 から 51 個の異なる自然数を選ぶと、互いに素な数が必ず存在する 」

ことを証明せよ.

【補題】連続する2つの自然数は互いに素である.

【証明】

連続する2つの自然数を \(n , n+1\) とし、その最大公約数を \(g\) とおく.

\begin{cases} n = ga ・・・①\\ n+1 = gb ・・・② \end{cases}

\(a , b\) は互いに素な自然数、\(a<b\) とおく.

② – ①より

\(g(b-a)=1\)

\(b-a>0\)、\(b-a\) は自然数より、\(g=1\)

よって連続する2つの自然数は互いに素となる

 

問題②の解答

・鳩 ⇒ 51 個の数

・巣 ⇒ { 1 , 2 } , { 3 , 4 } , { 5 , 6 } , ・・・ , { 99 , 100 } の 50 個の組

と考えると、
51 個の数を選ぶと必ず連続する 2 つの数のペアのどれかが存在する.
連続する 2 つの数は互いに素であるから、題意は示された.

【問題③】

「空間内に与えられた \(n\) 個の格子点の間を結ぶ線分を考える.このとき、これらの線分の中点の少なくとも 1 つは格子点である」

\(n\) として、どんな自然数を考えれば、上の命題は常に正しいか.適当な \(n\) を 1 つあげ、その理由を説明せよ.

ただし、格子点とは、\(x , y , z\) がすべて整数であるような点 \(( x , y , z )\) のことである

問題③の解答

それぞれの格子点の \(x , y , z\) 座標の偶奇に注目してグループ分けを以下の通りに行うと

  1. ( 偶数 ,偶数 ,偶数 )
  2. ( 偶数 ,偶数 ,奇数 )
  3. ( 偶数 ,奇数 ,偶数 )
  4. ( 偶数 ,奇数 ,奇数 )
  5. ( 奇数 ,偶数 ,偶数 )
  6. ( 奇数 ,偶数 ,奇数 )
  7. ( 奇数 ,奇数 ,偶数 )
  8. ( 奇数 ,奇数 ,奇数 )

の 8 タイプしかない.

したがって、 9 個以上の格子点を準備すれば、必ず同じタイプの格子点が 2 個以上存在し、その同じタイプの格子点の中点を考えれば、必ず格子点となる.

 

・鳩 ⇒ \(n=9\)

・巣 ⇒ 8 タイプの格子点

と考えたと言うことです!

 

最後に

「鳩」と「巣」が何に対応するかを考えるには少し工夫と慣れが必要になりますが、考え方自体は非常に単純なものです。大学入試において頻出ではありませんが、たまに出題れています。

全く知らない状態で、初見で解くことはさすがに難しいかと思いますので、考え方だけでもおさえておいてください。

コメント

タイトルとURLをコピーしました