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

离散数学习题二参考答案
第二节 容斥原理和抽屉原理
1.从1到500中,有多少数能被3或5整除？只能被3或5整除的数又有多少个
解：设A=“3的倍数”；B=“5的倍数”，则能被3或5整除的个数
N；
只能被3或5整除的数：
M
2.(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=2×3×331，设A=“1986内2的倍数”；B=“1986内3的倍数”；C=
“1986内331的倍数”，则
|A∪B∪C|=|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，一定有一个数大于或等于1998÷36=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个不同的正整数，证明若N≥2n，则在这序列中存在着连续的一段，其中个数的乘积是一个完全平方数。例如在含3，7，5的序列3，7，5，3，7，3，5，7中，7，5，3，7，3，5一段中，7×5×3×7×3×5=（7×3×5）2。
解：设A为n个给定的不同正整数所成的集合，即A=，任取一个有N个数的序列 π：，其中表示A中任一个元素，再令
是N个序列，
C=，|C|=N，（相当与N个苹果）
再设一集合B=，所以|B|=（相当于个抽屉）
建立一个从C到B的一个对应：中如有奇数个，则取1，否则取2，同样中如有奇数个，则取1，否则取2，…，（相当于把C中元素（苹果）放到B的元素（抽屉）中），由于|C|=N，由抽屉原理一定存在两个，，（i＜j）
它们对应的是一样的，这说明这两个序列对于A中元素的个数的奇偶性是一致的，把序列减去的序列得到的序列一定是π序列的一部分，这部分序列中的数都属于A中元素，并每个A中元素的个数都是偶数个，即它们的积一定是一个完全平方数。