FC2ブログ
2018年12月 / 11月≪ 12345678910111213141516171819202122232425262728293031≫01月

--.--.-- (--)

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
--:--  |  スポンサー広告  |  EDIT  |  Top↑

2008.05.22 (Thu)

鳩ノ巣原理

リンクは、頼まれたら拒みませんし、また人のブログからのリンクも拒むことはありません。
ただし、ご一報はくださいね。把握が困難になってしまうので。
リンクしてくれた、又はリンクさせていただいたみなさん、ありがとうございました。
これからも受付中です。
鳩ノ巣原理ですね。部屋割り論法とも言います。例の教科書ならcoffee breakに載っていたのですが。そこでは、分数を小数に直したときの値は、必ず有限小数又は循環小数であることを示していましたね。

早速問題です。解いてみてください。

「1から1999までの1000個の奇数がある。この奇数のうち、任意の501個の奇数を選んだとき、必ず異なる2数の和が2000になる奇数の組が存在することを示せ。」

簡単ですね。次のような証明です。

(証明)
1から1999までの1000個の奇数の中で、異なる2数の和が2000になる奇数の組(x,y)は、
(1,1999),(3,1997),(5,1995),・・・,(999,1001)の全部で500組存在する。
(定員2羽の鳩の巣が500個存在している。)
今、501個の奇数を選んだので、鳩の巣原理より、少なくとも一組は足して2000になる組が存在する。
(定員2羽の鳩の巣500個に501羽の鳩を割り振ると、少なくとも1つの鳩の巣には、鳩が2羽入っている。)
(Q.E.D.)

分かりますね?
次の問題です。

「xy平面上に任意にとった異なる5点の格子点が存在している。
この5点のうち、適当な2点の中点は、必ず格子点であることを示せ」

一応補足です。格子点とは、x座標、y座標ともに整数である点です。

(証明)
中点が格子点になるには、適当な2点のx座標の和と、y座標の和のそれぞれが偶数になればいい。
そのためには、適当な二点の座標がどちらも、(偶数,偶数),(奇数,奇数),(奇数,偶数),(偶数,奇数)であればよい。・・・※

ここで、格子点には、座標が(偶数,偶数),(奇数,奇数),(奇数,偶数),(偶数,奇数)の4種類しか存在しない。
(鳩の巣は4つしか存在しない。)
任意の異なる5点を取ったとき、鳩の巣原理より、必ずx座標、y座標の両方の偶奇が一致する点が少なくとも一組存在する。
(4つの鳩の巣に5羽の鳩を振り分ければ、少なくとも1つの鳩の巣には2羽の鳩が入っている。)

よって、※より、適当な2点の中点は、必ず格子点である。
(Q.E.D.)


実際に使えそうですか?鳩ノ巣原理。
何度も書きましたが、基本的な考え方はこうです。
「n個の鳩の巣に、n+1羽以上の鳩を振り分けたとき、必ず2羽以上入る鳩の巣が、少なくとも1つ存在する。」

分かりますね。この感覚は常識ですね。

それでは、最後の問題です。

「あるパーティーの参加者の知り合いの人数を調べたとき、必ず知り合いの人数が同じ人が一組以上存在することを示せ。ただし、AがBを知っているとき、必ずBもAを知っており、また、AがBを知らないとき、必ずBもAを知らないものとする。」

ちゃーんと理解していれば簡単な問題ですね。追記部分に答えです。
リンク募集中
オリンピックが終わるまでは当分これです。

【More・・・】

「あるパーティーの参加者の知り合いの人数を調べたとき、必ず知り合いの人数が同じ人が一組以上存在することを示せ。ただし、AがBを知っているとき、必ずBもAを知っており、また、AがBを知らないとき、必ずBもAを知らないものとする。」

(証明)
 あるパーティーの参加者の数をn人とする。

 すると、「知り合いである」と答える数で考えられるのは0人~n-1人のn通りである。
(∵自分自身は除く)
 
 しかし、もしも0人と答えた者がいるのならば、n-1人と答える者はおらず、また、n-1人と答えた者がいるのならば、0人と答える者はいない。
(∵「知り合いがn-1人」とは全員が知り合いである、「知り合いが0人」とは全員知らないということであり、条件より、ある人は、全員が知り合いならば、その他の誰もが少なくともその「ある人」を知っているので、知り合いが0人であることはないし、あるいは、そのある人は、全員のことが知らないのであれば、その他の誰もが少なくともその「ある人」のことを知らないので、知り合いがn-1人、つまり全員ということもない)

 よって、結局「知り合いである」と答える数で考えるのは0人~n-2人、又は、1人~n-1人の、どちらにせよn-1通りしか存在しない。

 パーティーの参加者はn人いるので、n通りの回答がある。

 よって、鳩ノ巣原理より、あるパーティーの参加者の知り合いの人数を調べたとき、必ず知り合いの人数が同じ人が一組以上存在する。


(Q.E.D.)
スポンサーサイト
18:15  |  論理学-math  |  TB(0)  |  CM(3)  |  EDIT  |  Top↑

*Comment

鳩の巣を思いっきり蜂の巣と呼んでしまった。。orz
ひなたぼっこ |  2008.05.22(木) 21:17 |  URL |  【コメント編集】

■No title

どうでもいいけど、1個目の証明でなんで(2,1998)が入ってるの??
奇数の和が2000になる組み合わせだから含まないのでは??

鳩ノ巣論法って正直どうでもいい。。
ってか、論理の証明ってセンスがないと無理だよね。。
おれさま |  2008.05.22(木) 21:26 |  URL |  【コメント編集】

■お詫びと訂正

おれさまさん、ご指摘ありがとうございます。
うっかりしていました。すみません。
問題の箇所、訂正させていただきました。
Pen. |  2008.05.22(木) 21:42 |  URL |  【コメント編集】

コメントを投稿する

URL
COMMENT
PASS  編集・削除するのに必要
SECRET  管理者だけにコメントを表示  (非公開コメント投稿可能)
 

▲PageTop

*Trackback

この記事のトラックバックURL

→http://penpenpensama.blog25.fc2.com/tb.php/32-c90004db

この記事にトラックバックする(FC2ブログユーザー)

この記事へのトラックバック

▲PageTop

 | BLOGTOP | 
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。