讨论:鸽巢原理
![]() |
鸽巢原理属于维基百科数学主题的基础条目第五级。请勇于更新页面以及改进条目。 本条目页属于下列维基专题范畴: |
||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
为什么必存在正整数满足“该数除以质数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)