討論:鴿巢原理

為什麼必存在正整數滿足「該數除以質數p_1,p_2,p_3.....,p_n，分別餘r_1,r_2,r_3....,.r_n」？

為什麼在$\operatorname {lcm} (p_{1},p_{2},p_{3}\cdots ,p_{n})$以下的正整數中，必存在一數滿足「該數除以質數$p_{1},p_{2},p_{3}\cdots ,p_{n}$，分別餘$r_{1},r_{2},r_{3}\cdots ,r_{n}$，其中$0\leq r_{i}\leq p_{i}-1,i=1,2,3\cdots ,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)

你的證明很正確，也更簡潔。我沒有想到。我的證明是構造性的，寫的太形式化了。$\forall$和$\exists$是兩個量詞的記號，分別表示全稱量化和存在量化，或「對於任意」和「存在」。總之只是個形式啦。如果內容看不明白一定告訴我，我再解釋啦。持節雲中（留言） 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)

證明有循環論證嫌疑

鴿籠原理是關於有限集的一個非常基本的命題，它說的是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個籠子，設各個籠子分別關有a₁、a₂、a₃、a₄隻鴿子，且沒有任何一個籠子關了2隻以上的鴿子，則：

$a_{1}+a_{2}+a_{3}+a_{4}=5$且

$a_{1}\leq 1$

$a_{2}\leq 1$

$a_{3}\leq 1$

$a_{4}\leq 1$

則$a_{1}+a_{2}+a_{3}+a_{4}\leq 1+1+1+1$

即$5\leq 4$

矛盾，所以原假設不成立，得證。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)

滿射表述為：有一函數$f:A\to B$。若$f$為滿射，則$|A|\geqslant |B|$。該命題的換質換位為：若$|A|<|B|$，則函數$f:A\to B$不是滿射。即：若籠子多於鴿子，則存在沒有鴿子的籠子。

單射表述為：有一函數$g:B\to A$。若$g$為單射，則$|B|\leqslant |A|$。該命題的換質換位為：若$|B|>|A|$，則函數$g:B\to A$不是單射。即：若鴿子多於籠子，則存在兩個處於同一個籠子中的鴿子。

這兩個命題互為對偶：如果存在一滿射函數$f:A\to B$，則$A$中元素不少於$B$種元素。如果$A$中元素不少於$B$，則存在一單射函數$g:B\to A$。-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)