《运用抽屉原理求解较复杂的组合计算与证明问题》由会员分享，可在线阅读，更多相关《运用抽屉原理求解较复杂的组合计算与证明问题（8页珍藏版）》请在金锄头文库上搜索。
1、运用抽屉原理求解较复杂的组合计算与证明问题内容概述运用抽屉原理求解的较为复杂的组介计算与证明问题.这里不仅“抽屉”与“苹果”需 要恰当地设计与选取，而且有时还应构造出达到最佳状态的例子.典型问题1. 从1, 2, 3,1988, 1989这些自然数中，最多可以取出多少个数，使得其中每两个数的差不等于4?【分析与解】1, 2, 3, 4, 9, 10, 11, 12, 17, 18, 19, 20, 25,，这些数中任何两个数的差都不为4,这些数是每8个连续的数中选取前4个连续的数.有19894-8=2485,所以最多可以选248X4+4=996个数.评注：对于这类问题，一种方法是先尽可能的多选
2、择，然后再找出这些数的规律，再计 算出最多可以选出多少个.2. 从1至1993这1993个口然数中最多能取出多少个数，使得英中任意的两数都不连续且 差不等于4?【分析与解】1, 3, 6, 8, 11, 13, 16, 18, 21,这些数中任何两个数不连续且差不等丁 4,这些数是每5个连续的数中选择第1、3个 数.1993子5=3983.所以最多可以选398X2+2=798个数.评注：当然还可以是1, 4, 6, 9, 11, 14, 16, 19, 21,，这些数满足条件，是每5个连续的数中选择第1、4个数.但是此时最多只能选出398X2+1=797个数.3. 从1, 2, 3, 4, 5
3、, 6, 7, 8, 9, 10, 11, 12中最多能选出几个数，使得在选出的数中, 每一个数都不是另一个数的2倍？【分析与解】 方法一：直接从1开始选1, 3, 4, 5, 7, 9, 11, 12,这样可以选出8 个数；而从2开始选2, 3, 5, 7, 8, 9, 11, 12,这样也是可以选出8个数.3包含在组内，因此只用考虑这两种情况即可.所以，在满足题意情况下，最多可以选出8个数.方法二：我们知道选多少个奇数均满足，有1, 3, 5, 7, 9, 11均为奇数，并且有偶数 中4的倍数，但不是8的倍数的也满足，有4, 12是这样的数.所以，在满足题意情况下最多可以选出8个数.4.
4、从1, 3, 5, 7,，97, 99中最多可以选出多少个数，使得选出的数中，每一个数都不 是另一个数的倍数？【分析与解】 方法一：因为均是奇数，所以如果存在倍数关系，那么也一定是3、5、 7等奇数倍.3X33： 99,于是从35开始，199的奇数中没有一个是3599的奇数倍(不包括1倍)， 所以选出35, 37, 39,，99这些奇数即可.共可选出33个数，使得选出的数中，每一个数都不是另一个数的倍数.方法 ：利用3的若干次幕与质数的乘积对这50个奇数分组.(1, 3, 9, 27, 81), (5, 15, 45), (7, 21, 63), (11, 33), (13, 39), (17
5、, 51),(19, 57),(23, 69), (25, 75), (29, 87), (31, 93), (35), (37), (41), (43),，(97)共 33 组.前11组，每组内任意两个数都存在倍数关系，所以每组内最多只能选择一 个数.即绘多可以选出33个数，使得选出的数中，每一个数都不是另一个数的 倍数.评注：l2n个口然数中，任意取出n+1个数，則其中必定有两个数，它们一个是另一 个的整数倍；从2, 3.，2n+l中任取n+2个数，必有曲个数，它们一个是另一个的整数倍；从1，2, 3.3n中任取2n+l个数，则其中必有两个数，它们中一个是另一个的整 数倍，且至少是3倍：从
6、1，2, 3,，mn中任取(m-l)n+1个数，则其中必有两个数，它们中一个是另一 个的整数倍，且至少是m倍(m、n为止整数).5. 证明：任给12个不同的两位数，其中一定存在着这样的两个数，它们的差是个位与十位 数字相同的两位数.【分析,j解】 因为两个不同的两位数相减得到的差不可能为三位或三位以上的数.如 果这个差是11的倍数，那么一定有这个差的个位与十位数字相同.两个数的差除以11的余数有0、1、2、3、10这11种情况.将这11种情况视为 11个抽屉.将12个数视为12个苹果，那么必定有两个苹果在同一抽屉，也就是说有两个数除以 11的余数相同，那么它们的差一定是11的倍数.而两个曲位数
7、的差一定是一个两位数，如果这个差是11的倍数，那么就有个数与十位 数字相等.问题得证.评注：抽屉原理一：将n+1个元素放到n个抽屉中去，则无论怎么放，必定有一个抽屉 至少有两个元素.抽屉原理:：将nr+1个元素放到n个抽屉中去，则无论怎么放，必定有一个抽屉至少 有r+1个元素.抽屉原理三：将m个元素放到n个抽屉中去则无论怎么放，必定有一个抽屉至个元素.6. 从1, 2, 3,，49, 50这50个数中取出若干个数，使其中任意两个数的和都不能被7 整除，则绘多能取出多少个数？【分析与解】利用除以7的余数分类：余0：(7,14,21,28,35,42,49)：余1:(1,8.15,22,29.36
8、.43, 50)：余2：(2,9,16,23,30,37,44)；余3：(3,10,17,24,31,38,45)：余4：(4,11,18,25,32,39,46)：余5：(S,12,26,33.40.47)：余6：(6,13,20 27,34,41,48).第一组内的数最多只能取1个：如果取第二组，那么不能取第七组内任何一个数；取 第三组，不能取第六组内任何一个数：取第四组，不能取第五组内任意一个数.第二、三、四、五、六、七组分别有8、7、7、7、7、7个数，所以最多可以取1+8+7+7=23 个数.1.从 It 2, 3,，99,100这100个数中任意选出51个数证明:(1) 在这51个
9、数中，一定有两个数互质:(2) 在这51个数中，一定有两个数的差等于50；(3) 在这51个数中，一定存在9个数，它们的绘人公约数人于1【分析与解】(1)我们将1100分成(1, 2), (3, 4), (5, 6), (7, 8),，(99, 100)这50组，每组内的数相邻.而相邻的两个门然数互质.将这50组数作为50个抽屉，同一个抽屉内的两个数互质.而现在51个数，放进50个抽屉，则必定有两个数在同一抽屉，于是这两个数互质.问 题得证.(2) 我们将 1100 分成(1, 51), (2, 52), (3, 53),，(40, 90), (50, 100)这 50组，每组内的数相差50.
10、将这50组数视为抽屉，则现在有51个数放进50个抽屉内，则 必定有2个数在同一抽屉，那么这两个数的差为50.问题得证.(3) 我们将1一100按2的倍数、3的奇数倍、既不是2又不是3的倍数的情况分组，有(2. 4, 6, 8.，98, 100), (3, 9. 15, 21, 21.，93, 99), (5. 7, 11, 13, 17, 19. 23,，95, 97)这三组.第一、二、三组分别有50、17、33个元素.瑕不利的情况下，51个数中有33个元素在第三组，那么剩下的18个数分到第一、二 两组内，那么至少有9个数在同一组.所以这9个数的般大公约数为2或3或它们的倍数, 显然大于1问题
11、得证&求证：可以找到一个齐位数字都是4的自然数，它是1996的倍数.【分析与解】注意到1996=1X499； 对于1, IL Ub，111-1中必定有两个数关于499同余.V440 个于是 111 -1= 111 - l(mod 499) (mn).svVB个1IX个I有 111 1-111 1二111 二 1000二0 所以 4991111000二0 ,因为(499,、V、VV、V、V、Vm个1n个1m-n个1n个0m-n个1个01000 -0)=1,所以 499111 - 1；于是有(499X4)1( 111 14),即 19961 444- 4n个0hf个1am个1nm个4于是，就找到这
12、样的全部都是由4组成的数字，是1996的倍数.评注：111 -1. 3333、7777、999 9可整除不合2. 5因数的任何整数;5sVxy上个1r个3k7片个92222、4444、666-6. 8888整除不含因数5(因数2分别只能含1, 2, 2、 v N V V v V 上个2上个4上个6斤个83个)的任何整数：5555整除不含因数2(因数5只能含1个)的任何整数.i个59. 有49个小孩，每人胸前有一个号码，号码从1到49各不相同.现在请你挑选若干个小 孩，排成一个圆圈，使任何相邻两个小孩的号码数的乘积小f 100,那么你址多能挑选出多 少个孩子？【分析与解】 将1至49中相乘小于1
13、00的两个数，按被乘数分成9组，如下：(1X2)、(1X3)、(1X4)、(1X49)：(2X3)、(2X4)、(2X5)、(2X19)： (8X9)、(8X10)、(8 XII)、(8X12)：(9X10)、(9X11).因为每个数只能与左右两个数相乘，也就定每个数作为被乘数或乘数最多两次，所以 每一组中最多会有两对数出现在圆圈中，最多可以取出18个数对，共18 X2=36次，但是 每个数都出现两次，故出现了 18个数.例如：(10X9)、(9X11)、(1X8)、(8X12)、(12X7)、(7X13)、(13X6)、(6X14)、 (14X5)、(5X15)、(15X4)、(4X16)、
14、(16X3)、(3X17)、(17X2)、(2X18)、(18X1)、 (1X10).共出现118号，共18个孩子.若随意选収出19个孩子，那么共有19个号码，由于每个号码数要与旁边两数分别相 乘，则会形成19个相乘的数对.那么在9组中取出19个数时，有19=9X2+1,由抽屉原则知，必有三个数对落入同一 组中，这样某个数字会在数对中出现三次(或三次以上)，由分析知，这是不允许的.故最多 挑出18个孩子.10. 在边长为1的正方形内随意放进9个点，证明其中必有3个点构成的三角形的面积 不大于丄.8【分析与解】 如下图，把正方形分成四个形状相同、大小相等的正方形.9个点任 意放人这四个正方形中.
15、根据抽屉原理，多于2X4个点放入四个长方形中，至少有2+1个点(即3个点)落在 某一个正方形之内.现在，特别取出这个正方形来加以讨论.把落在这正方形中的三点组成的三角形记为ABC,其面枳不超过小正方形面积的 丄，所以其而积不超过丄.这样就得到了需要证明的结论.2 8评注：在边长为1的等边三角形中有H2 +1个点，这斥+1个点中一定有距离不大于丄H的两点：在边长为I的等边三角形内有沪+1个点，这沪+1个点中一定有距离小于丄的两点.n已知平行四边形中.其面积为I,现有2ir +1个点，则必定有三点组成的三角形.其 面积不大于-;2n2已知三角形中，其而积为1,现有2沪+1个点，则必定有三点组成的三角形，
