江苏龙网

  1. 主页 > 生活百科 > >

抽屉原理的诀窍 抽屉原理( 三 )


例3 '(六人会议)证明了在任何六人会议中 ， 要么三个人以前认识 ， 要么三个人以前不认识 。"
例3”:17位科学家中的每一位都与另外16个人通信 ， 并且在他们的通信中仅讨论了三个问题 ， 而任意两位科学家在他们的通信中讨论了相同的问题 。证据:至少有三位科学家在他们的通信中讨论同一个问题 。
解法:我们假设A是科学家 。他只和另外16个人讨论了三个问题 。根据鸽子笼原理 ， 他和其中至少6个人讨论了同一个问题 。设这六个科学家是B ， C ， D ， E ， F ， G来讨论A问题 。
如果这六个人中的两个人也讨论A问题 ， 结论有效 。否则他们六个只会讨论B和c的问题 ， 这样 ， 从鸽子笼原理我们知道B至少在和另外三个人讨论同一个问题 。假设这三个人是C ， D ， E ， 我们说的是b 。
如果C、D、E中的两个也讨论B的问题 ， 结论成立 。否则他们只会讨论问题C ， 这个结论成立 。
3.制作抽屉是应用这一原则的关键 。
1从15个偶数中选9个数 ， 如2 ， 4 ， 6 ， … ， 30 ， 证明两个数之和一定是34 。
分析与回答我们用题目中的15个偶数做8个抽屉:
所有有两个数字的抽屉都有一个共同点:这两个数字之和是34 。从题目中的15个偶数中选择9个数字 。从鸽笼原理(因为只有八个抽屉)来看 ， 同一个抽屉里一定有两个数字 。根据制造的抽屉的特征 ， 这两个数之和是34 。
比如你在20个自然数1 ， 2 ， 3 ， 4 ， … ， 19 ， 20中至少选择几个 ， 就可以保证这两个数一定包含在内 ， 它们的差是12 。
在这20个自然数中 ， 有8对相差12: {20 ， 8}、{19 ， 7}、{18 ， 6}、{17 ， 5}、{16 ， 4}、{15 ， 3}、{14 ， 2}和{13 ， 1} 。
还有另外四个不成对的数字{9}、{10}、{11}和{12} ， 共12个抽屉(每个括号视为一个抽屉) 。只要从同一个抽屉里取出两个数 ， 两个数之差就等于12 。根据鸽子洞原理 ， 至少可以选择13个数字(取12个数字:从12个抽屉中各取一个数字(例如取1)
例:从1到20 ， 如果选择11个数字 ， 一定有两个数字 ， 其中一个是另一个的倍数 。
分析和回答题目要求的问题 ， 要考虑根据同一抽屉中任意两个数有多重关系的原理来制作抽屉 。将这20个数字按奇数和倍数分成以下十组 ， 视为10个抽屉(显然 ， 它们具有上述性质):
{1,2,4,8,16},{3,6,12},{5,10,20},{7,14},{9,18},{11},{13},{15},{17},{19} 。
从这10个数组的20个数字中选择11个数字 。根据鸽子洞原理 ， 至少有两个数是从同一个抽屉里取出的 。因为同一个抽屉里的两个数有倍数关系 ， 所以这两个数中的一个一定是另一个的倍数 。
例4:某校校庆 ， N位校友前来握手问候 。请证明N个校友中至少有两个在任何情况下握手的次数一样多 。
分析答案中有n个校友 ， 每个人至少握手0次 ， 即此人从未和其他校友握手；最多有n-1次 ， 就是这个人和在场的每一个校友握手 。但如果一个校友握手0次 ， 握手次数最多不能超过n-2次；如果一个校友握手n-1次 ， 那么最少握手次数不得少于1次 。无论是前一种状态0 ， 1 ， 2 ， … ， n-2 ， 还是后一种状态1 ， 2 ， 3 ， … ， n-1 ， 握手的次数都只有n-1 。把这n-1种情况作为n-1个抽屉 ， 参加会议 。
有些问题中 ， “抽屉”和“物件”并不明显 ， 需要精心制作 。如何制作它们可能非常困难 。一方面需要认真分析题目中的条件和问题 ， 另一方面需要多做题积累经验 。
抽屉原理
把八个苹果随机放在七个抽屉里 。不管你怎么放 ， 至少一个抽屉里有两个或更多的苹果 。鸽笼原理(Pigeonhole principle) ， 有时被称为鸽笼原理 ， 是由德国数学家狄利克雷为了证明数论中的一些问题而首次明确提出的 。所以也叫狄利克雷原理 。这是组合数学中的一个重要原理 。延伸到一般情况有以下表现 。
形式一:证明:设n+1个元素分成n个集合a1 ， a2 ， … ， an ， 用A1 ， A2 ， … ， An表示这n个集合中对应元素的个数 。需要证明ai至少有一部分大于等于2(反证法) 。假设结论不成立 ， 即每个ai都有ai 。


推荐阅读


上一篇：新年红包灯笼制作 红包灯笼制作

下一篇：分钟的单位缩写数学 分钟的单位