组合数学引论课后答案(部分)

《组合数学引论课后答案(部分)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、组合数学引论课后答案习题一1.1任何一组人中都有两个人，它们在该组内认识的人数相等。证明设组内共有n个人，每个人所认识的人数为0,1,2,…山-1。假设不存在这样两个人，他们所认识的人数相等，那么这几个人所认识的人数均互异，他们中的每一个人所认识的人数只取且仅取一次0,1,-1中的一个数，从而他们中必有一人认识的人数是0,也必有一人认识的人数是n-1,这是一个矛盾，因此假设不成立。1.2任取11个整数，求证其中至少有两个数，它们的差是io的倍数证明设这11个数为引，，…，创1,它们被10除之后其余数为0~9之间的整数。由鸽巢原理

2、可知，必有两个S设为血和丐,它们二者的余数相等，从而偽-丐==10p（p为一个整数），即务1.3任取n+l个整数，求证其中至少有两个数，它们的差是n的倍数证明设这n+1个数为引卫2,…，则可以将它们写成W=npi+rii=12…，a+1式中，Pi是5被n除之后的商，几是余数，且几€{0,1,…，几-1

3、°将a£i=1,…』+1）当作“鸽子”，将0丄…，一1当作“鸽巢”,则由鸽巢原理可知，必有两个a,其余数相等,设其为血和勺・,则a*—dj二即它们的差是n的倍数。；5一pj)n1.4在1・1节例4中证明存在连续的一些天，棋手恰好下

4、了k盘棋（k=l,2,21）•问是否可能存在连续的一些天，棋手恰好下了22盘棋证明设们』2,77分别为这11周内他每天下棋的盘数,@2=6]+62。77=61++•八+b“由于力m1(1WiW77)和®+6屮+…+b*W12(1wiW71),所以1W5<幻<…<^7712x11=132考虑序列al,a2,-,sa77>a1+k,a2++k(*)它们的值都是1〜132+R之间的整数。由于kw21,所以132+kw153,而序列(*)的项数为154,由鸽巢原理可知，序列(*)中如心，…2刀与«1+k,a2+仁…，巧7+A之间必有2项

5、相等，即存在1WiVjW77,使即从第i+1天到第j天这连续j-i天中，他刚好下了k盘棋。当k=22时，只有两种情况:(1)引，。2,…，。77，©+22,3+22,…，a”+22这154项中有2项相等。此时由上面的讨论知结论成立，即他在连续若干天恰好下22盘棋。(2)322,…27721+22,3+22,…“77+22这154项中没有2项是相等的。此时它们恰好分别取1~154。由于23w如+22

6、.1节例5推广成从1,2,・・・，2n中任选n+1个数的问题证明设取岀的n+1个数为aHa2,-,知叙，将它们表示为Qi=2siXi=1,2,…,n+1式中，Si为非负整数；用心，巾,…作“鸽子S用1,3,…,2孔-1这“个奇数作“鸽巢”,则由鸽巢原理可知,必有2个厂取相同值，设其为几和》不妨设航v切则a；25xTj%_2'jXTi即幻可被血整除。1.6从1,2,…,200中任取100个整数，其中之一小于16,那么必有两个数，一个能被另一个整除假设命题成立•首先将1-200按照连续除以2,直到不能被2整除的结果分为100组，即：

7、L1*2,1*4…・3,3*2,3*4….・•••197199每一组中的数都能互相整除•所以如果想取100个不能互相整除的数，只能每个组取一个•设取的数为al=1*2%a3=3*2J3a5=5*275al99=199*27199设那个小于16的数为i>=i.则a3i=3i*2"k3ij于是k3i

8、a27i/2<81而a81i=61*(i*2')c81i)>^l故矛盾丿所以假设不成立•命题得证明・1.7从1,2,…,200中取100个整数，使得其中任意两个数之间互相不能整除1.8任意给定52个数，它们之中有两个数，其和或差是100的倍数证明设&为这52个整数的集合，IA1=52。记人={aIa6仏且a被100除之后余数是iIUlaIa€仏且。被100除之后余数是100-f(i=0,1,-,50)1,则仏仆…"so构成人的51个“鸽巢”，从而存在使IAk

9、>20设°』€加,则a和6除以100,其余数要么相同，要么其和为100

10、,即或者是a=100m+kb=lOOn+k或者是或者是a=100m+100—ka=100m+kb=lOOn+100-*b=lOOn+100-*无论是哪种情形2-b或者a+6可被100整除。1.9在坐标平面上任意给定13个整点(即两个坐标均为整数的点)，则必有一个