Talk:鴿巢原理
![]() |
鴿巢原理属于维基百科數學主题的基礎條目第五級。请勇于更新页面以及改進條目。 本条目页属于下列维基专题范畴: |
||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
為什麼必存在正整數滿足「該數除以質數p_1,p_2,p_3.....,p_n,分別餘r_1,r_2,r_3....,.r_n」?
[编辑]為什麼在以下的正整數中,必存在一數滿足「該數除以質數,分別餘,其中」?
例如「整數除以3,5,7,分別餘2,3,1」,雖然未經計算還不知道這個數是什麼,但知道必存在這樣的整數。-游蛇脫殼/克勞棣 2017年4月2日 (日) 06:34 (UTC)
- 我用的是鴿籠原理。為避免代數太多,看得眼花撩亂(以及我也不明白上下顛倒的A、左右顛倒的E是什麼意思),就用以上的實例來說明:
- 整數除以3,餘數可能是0,1,2;整數除以5,餘數可能是0,1,2,3,4;整數除以7,餘數可能是0,1,2,3,4,5,6;所以餘數的組合共有3x5x7=105種。
- 假設在1到105這105個數中不存在「除以3,5,7,分別餘2,3,1」者,則餘數的組合只剩104種;105隻鴿子關進104個籠子,則至少有一個籠子關了2隻以上的鴿子,即1到105至少有兩個相異數分別除以3,5,7,所得的餘數組合完全相同,但這是不可能的:
- 設此兩數為x,y,則|x-y|是3的倍數,且|x-y|是5的倍數,且|x-y|是7的倍數,即|x-y|是3,5,7的公倍數,x若不等於y,則兩數相差至少105,超過了1到105的範圍。由反證法,得證。
- 這意味著1,2,3,4.....,105每個數恰好對應一個餘數組合(不會2個以上,也不會沒有餘數組合),且每個餘數組合恰好對應一個數(不會2個數以上,也不會沒有數)。
- @Iamapighhh:及諸位:不知這個方法可以嗎?-游蛇脫殼/克勞棣 2017年4月2日 (日) 06:34 (UTC)
你的证明很正确,也更简洁。我没有想到。我的证明是构造性的,写的太形式化了。和是两个量词的记号,分别表示全称量化和存在量化,或“对于任意”和“存在”。总之只是个形式啦。如果内容看不明白一定告诉我,我再解释啦。持节云中(留言) 2017年4月2日 (日) 18:00 (UTC)
- 就是Any 和Exist首字母倒过来写嘛。--Antigng(留言) 2017年4月6日 (四) 05:16 (UTC)
- @Antigng:不是All嗎?-游蛇脫殼/克勞棣 2017年4月6日 (四) 10:24 (UTC)
- For any === for all === for each. Bluedeck 2017年4月6日 (四) 17:58 (UTC)
- @Antigng:不是All嗎?-游蛇脫殼/克勞棣 2017年4月6日 (四) 10:24 (UTC)
- 就是Any 和Exist首字母倒过来写嘛。--Antigng(留言) 2017年4月6日 (四) 05:16 (UTC)
证明有循环论证嫌疑
[编辑]鸽笼原理是关于有限集的一个非常基本的命题,它说的是n元集到n-1元集不存在单射。以下命题看上去trivial但跟抽屉原理难度是相近的:m元集与n元集等势推出m=n (即是说,有限集的势是良定义的); n元集的真子集一定是有限集,而且其势m小于n。
从皮亚诺公理出发证明鸽笼原理必须通过数学归纳:首先1元集到空集不存在任何映射;然后如果找到了一个n元集A到n-1元集B的单射,假设它把元素a射到元素b, 那么我们得到一个A-a到B-b的单射。由于A-a的势是n-1, B-b的势是n-2, 由归纳假设得矛盾。注意A-a的势是n-1也是要证明的,见https://proofwiki.org/wiki/Cardinality_Less_One
原页面给的假设了势的良定义性,属于循环论证;因为势的良定性可以trivially推出抽屉原理,给这样的证明在逻辑链上没有贡献。67.194.233.86(留言) 2017年6月14日 (三) 07:19 (UTC)
- 雖然我的數學知識沒有高深到看懂您在寫什麼,不過我不覺得這是循環論證,這只有用到很基本的不等式的相加而已:
- 有5隻鴿子,全部關在4個籠子,設各個籠子分別關有a1、a2、a3、a4隻鴿子,且沒有任何一個籠子關了2隻以上的鴿子,則:
- 且
- 則
- 即
- 矛盾,所以原假設不成立,得證。n+1隻鴿子,n個籠子的情況是一樣的。
- 不等式的相加的論證過程有用到鴿籠原理嗎?-游蛇脫殼/克勞棣 2017年6月14日 (三) 08:10 (UTC)
「若有n+1個籠子和n隻鴿子,所有的鴿子都被關在鴿籠裡,則至少有一個籠子沒有鴿子。」算不算是鴿籠原理?
[编辑]在下所見過的鴿籠原理的原始表述大多為「若有n個籠子和n+1隻鴿子,所有的鴿子都被關在鴿籠裡,則至少有一個籠子有至少2隻鴿子。」;但其實若把數目交換,也可以有斷言,即「若有n+1個籠子和n隻鴿子,所有的鴿子都被關在鴿籠裡,則至少有一個籠子沒有鴿子。」,請問這算不算也是鴿籠原理呢?
因為條目中的例子「某男性先後有過4位妻子,合共生有2子3女,則至少有2位子女有同一位母親,且至少1位妻子沒有女兒,至少2位妻子沒有兒子。」的證明,似乎兩種表述都會用到?謝謝回答!
註:擴充的表述分別為「若有n個籠子和kn+1隻鴿子,所有的鴿子都被關在鴿籠裡,則至少有一個籠子有至少k+1隻鴿子。(n為正整數,k為非負整數)」以及「若有n+k個籠子和n隻鴿子,所有的鴿子都被關在鴿籠裡,則至少有k個籠子沒有鴿子。(n,k為非負整數,但n,k不同時為0)」。-游蛇脫殼/克勞棣 2018年12月24日 (一) 10:44 (UTC)
- 「若有n+1個籠子和n隻鴿子,所有的鴿子都被關在鴿籠裡,則至少有一個籠子沒有鴿子。」本身不是鴿籠原理的直接表述,但可以利用鴿籠原理證明。如果要把n+1個籠子對應n隻鴿子內,那麼就一定有一隻鴿子有多於一個籠子(這是傳統鴿籠原理表述的變體)。如果規定在有多個籠子對應一隻鴿子的時候,除一個籠子以外其他籠子都是空的,那麼我們就證明了,至少有一個籠子是空的。鋼琴小子 2018年12月24日 (一) 15:14 (UTC)
- 我的意思是鴿籠原理是否一定是「鴿子數比籠子數多的時候所下的斷言」?還是「籠子數比鴿子數多的時候所下的斷言」也是鴿籠原理的一種?而不是問「若有n+k個籠子和n隻鴿子,所有的鴿子都被關在鴿籠裡,則至少有k個籠子沒有鴿子。」如何證明。「鴿子數比籠子數多的時候所下的斷言」能證明「某男性先後有過4位妻子,合共生有2子3女,則至少有2位妻子沒有兒子。」嗎?我個人認為是不能的,因為這已經是另一個命題了。「鴿子比籠子多」與「籠子比鴿子多」根本是不同的兩件事啊!一個籠子可以關2隻以上的鴿子,但一隻鴿子可以關在2個以上的籠子裡嗎?(請不要告訴我把鴿子關在小籠子裡,再把小籠子裝在大籠子裡這種腦筋急轉彎式的敘述喔!)
- 這就好比我問內角72°-72°-36°的三角形是黃金三角形,那麼內角36°-36°-108°的三角形是否也是黃金三角形的一種呢?不論是或不是,這兩種三角形都不是相似形哪!
- 所以我的問題就是(再說一遍)「籠子數比鴿子數多的時候所下的斷言」是否也是鴿籠原理的一種?謝謝!-游蛇脫殼/克勞棣 2018年12月24日 (一) 17:09 (UTC)
- 抽屉原理推广后为有A、B两集合,当且仅当B到A存在单射关系时,A到B存在满射关系。笼子少于鸽子是该定理的满射表述,笼子多于鸽子都是该定理的单射表述。上述三者都是抽离原理的不同表示。-Mys_721tx(留言) 2018年12月24日 (一) 18:53 (UTC)
- 可是它們所得的斷言不同,一個是「至少有一個籠子有至少2隻鴿子。」,一個是「至少有一個籠子沒有鴿子」,請問這樣不同的斷言是合理的嗎?-游蛇脫殼/克勞棣 2018年12月25日 (二) 01:51 (UTC)
- 满射表述为:有一函数。若为满射,则。该命题的换质换位为:若,则函数不是满射。即:若笼子多于鸽子,则存在没有鸽子的笼子。
- 单射表述为:有一函数。若为单射,则。该命题的换质换位为:若,则函数不是单射。即:若鸽子多于笼子,则存在两个处于同一个笼子中的鸽子。
- 这两个命题互为对偶:如果存在一满射函数,则中元素不少于种元素。如果中元素不少于,则存在一单射函数。-Mys_721tx(留言) 2018年12月25日 (二) 06:03 (UTC)
- @Mys_721tx:君,所以你的意思是不論鴿子、籠子哪個比較多,兩種情況都是鴿籠原理的範疇嗎?順便問一句,「若有n+k個籠子和n隻鴿子,所有的鴿子都被關在鴿籠裡,則至少有k個籠子沒有鴿子。」這個擴充的表述是正確的嗎?謝謝!-游蛇脫殼/克勞棣 2018年12月25日 (二) 08:26 (UTC)
- 都属于,n+k没有问题。-Mys_721tx(留言) 2019年1月2日 (三) 02:29 (UTC)
- @Mys_721tx:君,所以你的意思是不論鴿子、籠子哪個比較多,兩種情況都是鴿籠原理的範疇嗎?順便問一句,「若有n+k個籠子和n隻鴿子,所有的鴿子都被關在鴿籠裡,則至少有k個籠子沒有鴿子。」這個擴充的表述是正確的嗎?謝謝!-游蛇脫殼/克勞棣 2018年12月25日 (二) 08:26 (UTC)
- 可是它們所得的斷言不同,一個是「至少有一個籠子有至少2隻鴿子。」,一個是「至少有一個籠子沒有鴿子」,請問這樣不同的斷言是合理的嗎?-游蛇脫殼/克勞棣 2018年12月25日 (二) 01:51 (UTC)