资源描述：
《组合数学与图论复习题及参考答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、组合数学与图论复习题及答案1．Showthatifn+1integersarechosenformtheset{1,2,…,2n},thentherearealwaystwowhichdifferbyatmost2.从{1,2,…,2n}中选出n+1个数，在这n+1个数中，一定存在两个数，其中一个整数能整除另外一个整数。任何一个数都可以写成2k*L，其中k是非负数，L是正奇数。现在从1到2n之间只有n个奇数。由于有n+1个数都能表示成2k*L，而L的取值只有n中，所以有鸽子洞原理知道，至少有两个数的
2、L是一样的，于是对应k小的那个就可以整除k大的另一个数。2．Showthatforanygiven52integersthereareexisttwoofthemwhosesum,orelsedifference,isdivisible100.设52个整数a1，a2，…，a52被100除的余数分别是r1,r2,…,r52，而任意一个数被100除余数为0，1，2，…，99，一共100个。他们可以分为51个类{0},{1,99},{2,98},…,{49,51},{50}。将这51个集合视为鸽笼，则将r
3、1,r2,…,r52放入51个笼子中，至少有两个属于同一个笼子，所以要么有ri＝rj，要么有ri＋rj＝100，也就是说ai－aj
4、100或者ai＋aj
5、100。3．从1，2，3，…，2n中任选n+1个数，证明在这n+1个数中至少有一对数互质。鸽子洞原理，必有两个数相邻，相邻的两个数互质4．ProvethatRamseynumberR(p,q)≤R(p,q-1)+R(p-1,q).令N＝R(p,q-1)+R(p-1,q)，从N个人中中随意选取一个a，F表示与a相识的人，S表示与a不相识的人。在剩下的
6、R(p,q-1)+R(p-1,q)－2＋1个人中，由鸽子洞原理有，或者F中有R(p,q-1)人，或者S中有R(p-1,q)人。如果F中有R(p,q-1)人，则与a相识的人为p个；如果S中有R(p-1,q)人，则与a不相识的人有p个。所以有R(p,q)≤R(p,q-1)+R(p-1,q)5．Thereare10people,eitherthereare3eachpairofwhomareacquainted,orthereare4eachpairofwhomareunacquainted。从10人中随
7、意选一个人p，F表示与p相识的人，S表示与p不相识的人若F中至少有4人，如果至少有4人不相识，则满足题设；如果有2人相识，则加上p有3人相识，也满足题设。若F中至多有3人，则S中至少有6人，6人中至少有3人相识，或者不相识。如果相识则满足题设，如果不相识加上p不相识的人就有4个，也满足题设。6．Inhowmanywayscansixmenandsixladiesbeseatedatroundtableifthemenandladiestositinalternateseats?6个男的先进行圆排列，
8、然后6个女的插入空位。7．Inhowmanywayscan15peoplebeseatedatroundtableifBrefusestositnexttoA?WhatifBonlyrefusestositonAright?A．15个人进行圆排列，减去ab组成一个元素的14人的圆排列，然后减去ba组成一个元素的14人的圆排列。B．15个人进行圆排列，减去ab组成一个元素的14人的圆排列。1．Determinethenumberof10-combinationsofthemultisetS={¥*a,
9、4.b,5*c,7*d}。(1+x+x2+x3+…)(1+x+x2+…+x4)(1+x+x2+…+x5)(1+x+x2+…+x7)展开2．把n个有编号的球放入m个有编号的盒子中，不允许有空盒子，有多少种放法。先假设，盒子没有编号，然后乘上组合与排列的关系：3．证明在n（n³2）个人中总有两个人，他们在这群人中所认识的人数目相同。当n＝2时，如果两个人相互认识，则每个人认识的人只有一个；如果不认识，则每个人认识的人为0个。当n>2时，设xi(x=1,2,…,n)表示，第i个人认识的人的数目。（每个人最
10、多只能认识n-1个人。）A．如果每个人都有熟人那么由鸽子洞原理知道至少有两个人i和j认识的人数相同即xi＝xjB．如果只有一个人没有认识的人那么对于剩下的n－1个人来说能认识的人对多只有n－2个，由鸽子洞原理知道，这n－1个人中至少有两个人i和j认识的人数一样即xi＝xjC．如果至少有两个人都没有熟人，则满足题设。4．一个剧团演出11周，为保证收入和不至于太累，规定每天至少演出一场，每周不超过12场。证明存在连续的若干天，恰好演出21场。设a1为第一天该剧团的演出的次
