离散数学习题二参考答案.doc

离散数学习题二参考答案第二节 容斥原理和抽屉原理1.从1到500中,有多少数能被3或5整除？只能被3或5整除的数又有多少个解：设A=“3的倍数”；B=“5的倍数”，则能被3或5整除的个数N；只能被3或5整除的数：M2.(1)一个班级有50名学生，第一次考试有26名得A等，第二次考试有21名得A，若两次考试中都没有得A的有17名，那么两次都得A的有多少名？ (2)若50名在两次考试中得A的人数相同，两次中恰有一次得A的为40名，两次中都没得A的有4名，那么仅在第一次得A的有多少名。解：设A=“第一次考试得A等”，B=“第二次考试得A等”，则(1)|A|=26，|B|=21，由，所以两次都得A的人数：N=|AB|=50-26-21+17=14（人）(2)由题意得：，又，所以，即仅在第一次中得A的人数M=。3.在1到3000的整数中，不能被3，5，7中任何一个数整除的有多少个？又有多少个数能被3整除，但不能被5和7整除？解：设A=“3的倍数”；B=“5的倍数”，C=“7的倍数”，则不能被3，5，7中任何一个数整除的个数：N=(个能被3整除，但不能被5和7整除的个数M=4.分母是1986的最简真分数共有多少个？解：1986=23331，设A=“1986内2的倍数”；B=“1986内3的倍数”；C=“1986内331的倍数”，则|ABC|=|A|+|B|+|C|-|AB|-|AB|-|BC|+|ABC|=所以，分母是1986的最简真分数的个数N=1985-1325=660（个）。5.50名同学中，爱好美术的占总数的3/5，爱好音乐的比爱好美术的多3名，音乐和美术都不爱好的人数比两项都爱好的人数的1/3还多1名，问对两项都爱好的同学有多少名？解：设A=“爱好美术的人”；B=“爱好音乐的人”，则（人），|B|=|A|+3=33（人），又，所以，50-30-33+|AB|-1=|AB|/3，|AB|=21答：两项都爱好的同学有21名。6.证明：在任意m个相继的整数中，存在一个整数能被m整除。证明：任意m个相继的整数任取两个整数它们的差一定小于m,即差一定不是m的倍数.(反证)倘若这m个相继的整数中不存在一个整数是m的倍数,那么由抽屉原理一定存在两个整数它们对于除以m的余数相同,它们的差一定是m的倍数,与前的结论矛盾.7.证明对于任意的整数n，都存在着n的一个倍数Sn，Sn中只含数字0和7。证明：设，（1）若存在一个k,使是n的倍数，则命题成立，（2）若不存在这样的k，由抽屉原理在这n个数中，一定存在两个和，它们除以n的余数相同，那么-=一定是n的倍数。9.把一个圆周分为36段，将36个数字1，2，3，4，36，任意地标在每段上，使每一段恰有一个数字,证明一定在相邻的三段，它们的数字的和至少是56。证明：设表示第k段上的数字，k=1，2，3，36。并，再设，则显然36个数的和是1998，一定有一个数大于或等于199836=55.5，即一定在相邻的三段，它们的数字的和至少是56。10.证明：在任意选取n+1个整数中，存在两个整数，它们的差能被n整除。证明：这n+1个数除以n后的余数只有n种情况，有抽屉原理可知，一定有两个数除以n后的余数是相同的，这两书的差就一定是n的倍数，即它们的差能被n整除11.证明：一个有理数的十进位小数展开式，自某一位后变为周期的循环。证明：一个有理数一定可以写成分数形式任取一个数，除以n后的余数一定是唯一的，并只有n种，所以当m除以n时，余数在若干次数后一定重复，这是商也就重复了，即自某一位后变为周期的循环。12.一个人步行了十小时，共走了45公里，已知他第一小时走6公里，而最后一小时只走3公里，证明一定存在相邻的两小时内至少走了9公里。（提示：把相邻两小时走的总路程看成盒子）证明：设表示第k分钟走的路程，k=1,2,3,4,5,6,7,8,9，10. 并，所以，再设，则显然9个数的和是81，一定有一个数大于或等于9，即一定存在相邻的两小时内至少走了9公里。13.从整数1，2，3，200中，任意选取101个数，证明在这101个整数中，存在两个整数，使得一个能被另一个整除。（提示：把整数写成2n a的形式，其中a是奇数，把a看成盒子）证明：任取一个200以内的整数n一定能写成2n a的形式，其中a是奇数。如果两数的a相等，则两数一定成倍数关系。由于200以内只有100个奇数，所以任意取出101个整数，必有两个数有相同的a，即这两数一定成倍数关系。14.设有一个N个正整数序列，其中恰含n个不同的正整数，证明若N2n，则在这序列中存在着连续的一段，其中个数的乘积是一个完全平方数。例如在含3，7，5的序列3，7，5，3，7，3，5，7中，7，5，3，7，3，5一段中，753735=（735）2。解：设A为n个给定的不同正整数所成的集合，即A=，任取一个有N个数的序列 ：，其中表示A中任一个元素，再令是N个序列， C=，|C|=N，（相当与N个苹果）再设一集合B=，所以|B|=（相当于个抽屉）建立一个从C到B的一个对应：中如有奇数个，则取1，否则取2，同样中如有奇数个，则取1，否则取2，（相当于把C中元素（苹果）放到B的元素（抽屉）中），由于|C|=N，由抽屉原理一定存在