数と論理

レベル:大学入試

皆さんお元気ですか。

今日は初等整数論でよく出てくる論法を扱ってみましょう。

日本語では部屋割り論法といわれていますが、英語圏ではpigeonhole principle と言われていますね。

n個の部屋がある時に、そこに(n+1)人を適当に入れる時に必ず2人以上が入る部屋がある。

さてはて、これは、原理なのか定理なのか?という問題も出てきますが、皆さんだったら、これをどう説明しますか?

 

大阪教育大学入試問題
  問題

(1) 自然数nに関する命題P(n)「n=2am (a は負ではない整数、mは奇数)と表せる」を考える。P(n)がkより小さいすべての自然数について成り立つならば、n=kについても成り立つということを示せ。

(2) Nを自然数とする。1から2Nまでの自然数の中からどのように(N+1)個の自然数を選んでも、その中に一方が他方をわりきるような二つの数の組が存在することを示せ。


 

【解説】

うーーーん、こういうものを証明させるというのが果たして良いことなのですかねえ?という気がしないでもありませんね。

 

自然数が素数の積に因数分解できるということを認めれば、(1)は明らかですからねえ。

皆さんすべての自然数が、素数の積に因数分解できること、そしてその分解の仕方が順序を除いて一意的であること、これを証明できますか?

まず自分でやってみてください。

まあ、とにかく数学的帰納法らしき論法でやってみましょう。

 

nが奇数なら、つまり2で割り切れないなら、n=20 n とかけnが奇数ですから、P(n)が成り立っていますね。

nが偶数なら、つまり2で割り切れるなら、n=2n’ と書けますね。ここで、 n’はnよりも小さい自然数です。(なぜだかわかりますか?)

ですから、n’については数学的帰納法の仮定が使えますね。

従って、 n’=2a n'' と書けて、n'' は奇数です。

すなわち、

n=2a+1 n'' , n'' は奇数。

これで数学的帰納法による証明が終わります。

まあ、あんまりすっきりしませんから、皆さん何か自分の好きな証明方法を考えてみるといいですね。

 

(2)をやってみましょう。

今取り出した(N+1)個の自然数を小さい順に並べます。

2a(1)m1、2a(2)m2、・・・・・、2a(N+1)mN+1

ここで、m1、m2、・・・・・mN+1は奇数で、1、2、・・・・・2N+1の因数になっていますから2Nより小さな奇数です。1から2Nまでの奇数を並べてみると

1、3、5、・・・・、(2N-1)

です。つまりN個あります。(なぜだかわかりますか?)

さて、m1、m2、・・・・・mN+1は(N+1)個ありますからどれか二つが必ず一致しますね。(上記の部屋割り論法で考えると分かりやすいですね。)

つまり、mi=mj(i<j)となるi、jがある。

このときa(i)<a(j)となりますね。

すなわち、2a(i)miで2a(j)mjは割り切れます。

 

どうですか、みなさん?

初等整数論ではこうしてなんとなく当たり前であるような、ないような、分かったようなわからないような論法が時々出てきますね。

 



数学TOPへ


ABOUT US

ルシディチュード―灯台教養学部へようこそ。このサイトは、一般教養を学べる無料オンラインサイトです。Luciditude ルシディチュード= Lucid (明晰な、明快な)+ -(i)tude(状態、性質)。“すべての人の灯台としての教養を”をコンセプトに、大人も子どもも、ご家族みんなで、わかりやすく幅広く学べる一般教養をご紹介します。同時に、キャリア形成に役立つ能力開発についても発信します。雑談知識のインプット、生涯学習としてご活用ください。数学と英語は受験問題と解説を掲載しています。受験生はもちろん、受験生でない皆さんもぜひチャレンジしてみてください。

>>read more