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

组合数学引论课后答案习题一1.1 任何一组人中都有两个人，它们在该组内认识的人数相等。证明 设组内共有n个人，每个人所认识的人数为0,1,…山-1。假设不存在这样两个人，他们所认识的人数相等，那么这几

组合数学引论课后答案 习题一 1.1 任何一组人中都有两个人，它们在该组内认识的人数相等。 证明设组内共有个人，每个人所认识的人数为 n0,1, 2, …山-。假设不存在这样两个人，他们所认识的人数相等，那 1 么这几个人所认识的人数均互异，他们中的每一个人所认识的人数只取且仅取一次 中的一个数，从而他们中必有一人认识的人数是也必有一人认识的人数是 0,1,-10,n- 这是一个矛盾，因此假设不成立。 1, 1.211io 任取个整数，求证其中至少有两个数，它们的差是的倍数 证明设这个数为引，，…，创,它们被除之后其余 11110 数为之间的整数。由鸽巢原理可知，必有两个S设为血和 0~9 丐,它们二者的余数相等，从而偽-丐==为一个整数），即务 10p（p 1.3n+ln 任取个整数，求证其中至少有两个数，它们的差是的倍数 证明设这个数为引卫…，则可以将它们写成 n+12, W=npi+ri i=12…a+1 ， a£i 式中，是5被除之后的商，几是余数，且几€，几-将…』 Pin{0,1,…1|°=1,+1） 当作“鸽子”，将丄…，一当作“鸽巢”,则由鸽巢原理可知，必有两个其余数 01a, 相等,设其为血和勺・,则 a*—dj pj)n ；5一 二 即它们的差是的倍数。 n 1.4114k（k=l,2,21） 在节例中证明存在连续的一些天，棋手恰好下了盘棋•问是 ・ 22 否可能存在连续的一些天，棋手恰好下了盘棋