鴿籠原理

强

有谁了解鸽笼原理？(pigeon hole principal)

抽屉原理，把多于n个的物体放到n个抽屉里，则至少有一个抽屉里有2个或2个以上的物体。
　 ， 把多于mn个的物体放到n个抽屉里，则至少有一个抽屉里有m+1个或多于m+l个的物体。

强

Quantum 于 8-3-2004 05:10 PM  说 :
抽屉原理，把多于n个的物体放到n个抽屉里，则至少有一个抽屉里有2个或2个以上的物体。
　 ， 把多于mn个的物体放到n个抽屉里，则至少有一个抽屉里有m+1个或多于m+l个的物体。

这我了解，是希望能有一些比较抽象的例子

情~風

有n+1隻鴿
n個籠

最少有一籠裝多於一隻鴿

由此作引伸

斷羽鳥

第一次听说也！　解释下！！！！

narret

大概明白

=)

井底之蛙

举个例子：-
简单的：
你有七个封信，六个信箱，那么你可以得到一个结论：
一定有一个信箱有两封信。

较难的：
在六个人当中，一定有三个人互相认识或者三个人互相不认识。
这问题大家通常都会直接用graph theory 来证明，
但在某一次数学比赛的时候(我忘了是什么比赛），听说有人用这个原理来证明此题目，
不知大家懂吗？

我忘了具体的证明方法，现在我试试写下,请多多指教。
首先，你假设两个情况：
A. 第一个箱子，一个人认识三个人或多过；
B. 第二个箱子，一个人认识少过三个人。
然后把符合情况的人都丢进箱子里，我们就会得到以下的比例（A：B ）：
6-0，5-1，4-2，3-3，2-4 <- 这些比例很明显的都符合问题要求 - 三个人互相认识；
0-6 <- 这个比例很明显的也符合问题要求 - 三个人互相不认识；
1-5 <- 这个比例也符合问题要求 - 三个人互相认识或三个人互相不认识（还须进一步证明）。
1-5 => 现在你再分成3个情况：-
i.  第一个情况，一个人只认识两个人；
ii. 第二个情况，一个人只认识一个人。
iii.第三个情况，一个人都不认识。
结论：至少有一个情况是：
有两个人是 只认识两个人 或
           只认识一个人 或
           一个人都不认识
那么从这个结论在加以推论/说明（用graph theory)就可以完全证明题目的须求了。

[ Last edited by 井底之蛙 on 16-3-2004 at 12:16 AM ]

pipi

这让我想到一个事实：
世界上存在着两个拥有相同数量头发的人。

证明：
设一个人拥有头发的数量 ＜＝ a
世界上的人口 ＝ b

明显的：b ＞ a . （我想单单中国的人口就大于 a 了）

利用鸽笼原理，必定存在着两个拥有相同数量头发的人。

证毕。

强

那我就来出一题。。

在一个平面（plane)上，每一个点都是蓝色或红色。

试证明不论如何，一定会有两点，距离准准一米，他们的颜色是一样的！

情~風

一個平面上有一個正三角形,且邊長為1公尺
三角形三個頂點,卻只有兩種顏色,
根據鴿籠原理,3>2
必有兩個點顏色一樣
所以平面上必有兩個頂點距離為1公尺且顏色一樣

pipi

井底之蛙 于 16-3-2004 12:08 AM  说 :
在六个人当中，一定有三个人互相认识或者三个人互相不认识。

取于http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_07/page2.html

鴿籠原理

任取一人名之為 A，其他人，人數至少為 5，可分為二類。與 A 認識者為一類，與 A 不認識者為另一類，由鴿籠原理，必有一類人數大於等於 3。令此三人之名為 B、C、D。

若 B、C、D 皆與 A 認識且其中有二人彼此相識，則 A 及此二人為三知友，不然 B、C、D，兩兩不認識則 B、C、D 為三新鮮人；

若 B、C、D 皆與 A 不認識且其中有二人彼比不相識，則 A 與此二人為三新鮮人，不然 B、C、D 中兩兩互相認識則 B、C、D 為三知友。

無論有三知友或三新鮮人，結論都是對的。

梵谷

情~風 于 1-4-2004 01:37  说 :
一個平面上有一個正三角形,且邊長為1公尺
三角形三個頂點,卻只有兩種顏色,
根據鴿籠原理,3>2
必有兩個點顏色一樣
所以平面上必有兩個頂點距離為1公尺且顏色一樣

偶还是不明白
为何三角形边长为一公尺,而且又是正三角形??


[数学比赛加分(30分) - + 30分]

[ Last edited by 微中子 on 25-7-2004 at 06:26 PM ]