组合数学作业答案2016

组合数学作业第一章引言Page13,ex3,4,7,30ex3.想象一座有64个囚室组成的监狱，这些囚室被排列成88棋盘。所有相邻的囚室间都有门。某角落处意见囚室例的囚犯被告知，如果他能够经过其它每一个囚室正好一次之后，达到对角线上相对的另一间囚室，那么他就可以获释。他能获得自由吗？解：不能获得自由。方法一：对64个囚室用黑白两种颜色染色，使得横和竖方向相邻的囚室颜色不同。则对角线上两个囚室颜色为同黑或同白。总共偶数个囚室，若能遍历且不重复，则必然是黑出发白结束，矛盾。方法二：64个囚室，若要经过每个囚室正好一次，需要走63步，即奇数步。不妨假设该囚犯在第1行第1列，那么到第8行第8列，横着的方向需要走奇数步，竖着的方向需要走奇数步，即总共需要偶数步。所以不能恰好经过每个囚室一次到达对角线上的囚室。ex4.(a)设f(n)是用多米诺牌(2-牌)对2×n棋盘作完美覆盖的个数。估计一下f(1),f(2),f(3),f(4)和f(5).试寻找(或证明)这个计数函数f满足的简单关系。利用这个关系计算f(12)。(b)设g(n)是用多米诺牌(2-牌)对3×n棋盘作完美覆盖的个数。估计g(1),g(2),…,g(6).解：(a)f(1)=1,f(2)=2,f(3)=3,f(n+2)=f(n+1)+f(n)f(4)=f(3)+f(2)=5,f(5)=f(4)+f(3)=8f(6)=f(5)+f(4)=13f(7)=f(6)+f(5)=21f(8)=f(7)+f(6)=34f(9)=f(8)+f(7)=55f(10)=f(9)+f(8)=89f(11)=f(10)+f(9)=144f(12)=f(11)+f(10)=233(b)g(1)=0,g(2)=3,g(3)=0,g(4)=9+2=11,g(n+4)=4g(n+2)-g(n),g(5)=0,g(6)=41.ex7.设a和b是正整数，且a是b的因子。证明m×n棋盘有a×b的完美覆盖当且仅当a既是m又是n的因子，而b是m或n的因子。(提示:把a×b牌分割成a个1×b牌。)解：充分性。当a既是m又是n的因子，而b是m或n的因子，则m×n棋盘有a×b的平凡完美覆盖。必要性。假设m×n棋盘有a×b牌的完美覆盖。则m×n棋盘必有b牌的完美覆盖。根据书中的定理，b是m的因子或n的因子。下面证明a既是m的因子又是n的因子。方法一:因为a是b的因子，所以a×b牌可以分割成b/a个a×a牌。m×n棋盘有a×a的完美覆盖，则必然有a×a牌的完美覆盖。而a×a牌是正方形的，所以只有唯一的一种平凡覆盖方式。从而m是a的倍数，n也是a的倍数。方法二:因为a是b的因子，不妨设b=ka。由m×n棋盘有a×b牌的完美覆盖，可任取一个完美覆盖。设第一行的n个方格由p个a×b牌和q个b×a牌盖住，则有n=pb+qa=(pk+q)a，所以n是a的倍数。同理，m也是a的倍数。ex30.考虑堆的大小分别为10,20,30,40,50的5堆Nim游戏。这局游戏是平衡的吗？确定玩家I的第一次取子方案。解：将10,20,30,40,50用二进制表示目标取出个数10:0101010000×20:101001110110=630:1111010011010=2640:101000110010×50:1100101010001010=10平衡011010游戏是不平衡的。从上表可以得到，可从20个堆中取6个，从30个堆中取26个，从50个堆中取10个。第2章排列组合P37:ex5,11,27,32,51ex5.确定作为下列各数的因子的10的最大幂(等价于用通常的10进制表示时尾部0的个数)：(a)50!,(b)1000!解：(a)50/5=10,即1~50中有10个5的倍数。50/25=10/5=2，即1~50中有2个25的倍数。从而50!的因子的5的最大幂是10+2=12。因为2的最大幂比5大，所以5的因子个数决定10的最大幂。(b)同理，1000/5=200,200/5=40,40/5=8,8/5=1,1/5=0，所以1000!的因子的10的最大幂等于200+40+8+1=249.ex11.从数集{1,2,…,20}中形成3个数的集合，如果没有2个相连的数字在同一个集合中，那么能形成多少个3个数的集合。解法一：任选3个数有C(20,3)种方案。两数相邻另一个分离：1,2和19,20这两个相邻数对，各对应另一不相邻数有17种选择；2,3到18,19共17种相邻数对，各对应另一不相邻数有16种选择。三数相邻有18种选择。202171716188163.解法二：任选3个数有C(20,3)种方案。取两个相邻数有19种选择，另一个与已取出两数不同有18种选择。每三个相邻的数在前一步被计数了两次，需要补回一次。201918188163；解法三：先放17个0排成一排。再在18个空挡中放3个1，有C(18,3)种方法。在17个0和3个1形成的排列中，数1所在的位置abc，即得到3个不相邻的1到20中的数。解法四：令3个数从小到大排列为a,b,d，满足a+1b，b+1d。令B=b-1,D=d-1，则aBD为从1到18中的数，且无不相邻限制。188163ex27.5个没有区别的车放在88棋盘上，使得没有车能够攻击别的车并且第一行和第一列都不空的放置方式有多少?解：方法一:5个横坐标的选择方案有C(7,4)种，因为第1列必选；5个纵坐标的选择方案有C(7,4)种，因为第一行必选；横纵坐标的配合有5!种，因为横坐标固定，纵坐标全排列。所以总的方案数为C(7,4)C(7,4)5!=147000.方法二:分两种情况：一是选第一行第一列，其它4个在其它7行7列；有C(7,4)C(7,4)4!种方案。二是第一行2至8列中选一个，第一列2至8行中选一个，其它3个在其它6行6列；有77C(6,3)C(6,3)3!。总方案数为C(7,4)C(7,4)4!+77C(6,3)C(6,3)3!=C(7,4)C(7,4)5!=147000。ex32.确定下面的多重集合的11排列的数目：S={3a,4b,5c}。解：多重集S={3a,4b,5c}的11排列可分为3个部分：{2a,4b,5c}：11!69302!4!5!；{3a,3b,5c}：11!92403!3!5!；{3a,4b,4c}：11!115503!4!4!；共有6930+9240+11550=27720个排列。ex37.一家面包店销售6种不同类型的酥皮糕点。如果该店每种糕点至少有一打，那么可能配置成多少打不同类型的酥皮糕点？如果在一盒中每种糕点至少有一块，又能有多少打？解：(1)12个球与5个间隔的全排列有C(12+5,5)个，所以总共可以配成C(17,5)种12个一盒的酥皮蛋糕盒。(2)每种蛋糕至少一块，则盒中已有6块蛋糕。还需要放入6块蛋糕。等价于6个球与5个间隔全排列，有C(6+5,5)种方案。所以总共可以配成C(11,5)种12个一盒且每种蛋糕至少有一个的酥皮蛋糕盒。ex51.考虑大小为2n的多重集合{na,1,2,3,…,n}，确定它的n组合数。解：令S={na,1,2,3,…,n}.方法一：{1,2,…,n}中取k个有C(n,k)种方案，再取n-k个a得到S的n组合。所以方案数是C(n,0)+C(n,1)+…+C(n,n)=2n.方法二：{1,2,…,n}的全体组合有2n个，{1,2,…,n}的任何一个组合配上相应个数的a可以得到S的一个n组合。ex52.考虑大小为3n+1的多重集合{na,nb,1,2,3,…,n+1}，确定它的n组合数。解：在{1,2,…,n+1}中取k个有C(n+1,k)种方案，n个a和n个b中取n-k个组合有C(n-k+1,1)=n-k+1种方案。方法一:C(n+1,k)(n-k+1)=(n+1)C(n,k)，对k从1到n求和得到(n+1)2n种方案。方法二:因为(x+1)n+1=ΣC(n+1,k)xn-k+1，两边同时对x求导，得到(n+1)(x+1)n=ΣC(n+1,k)(n-k+1)xn-k。令x=1，便得到ΣC(n+1,k)(n-k+1)=(n+1)2n。第3章鸽巢原理P50:ex4,7,11,13,16ex4.证明：如果从集合{1,2,…,2n}中选择n+1个整数，那么总存在两个数它们之间相差1.证明：将2n个数分成n个集合：{1,2},{3,4},…,{2n-1,2n}。那么任取的n+1个数至少有两个在同一个集合中，它们之间相差1.ex7.证明：对任意给定的52个整数，存在两个整数，要么两者的和能被100整除，要么两者的差能被100整除。证明：构造51个鸽巢：模100余0的一个鸽巢；模100余1和余99的一个鸽巢；模100余2和余98的一个鸽巢；模100余3和余97的一个鸽巢；以此类推…；模100余49和余51的一个鸽巢；模100余50的一个鸽巢。52个数，至少有两个在同一个鸽巢。若这两个数模100同余，则两个数的差是100的倍数；若这两个数模100不同余，则这两个数的和是100的倍数。ex11.一个学生有37天来准备考试。根据以往经验，她知道她需要的学习时间不超过60小时。她还希望每天至少学习一个小时。证明，无论她怎么安排学习时间(每天学习的时间是整数小时)，都存在连续若干天，在此期间她恰好学习了13个小时。证明：设ai是这名学生从第1天到第i天学习的总小时数，那么0a1a2…a36a376013+a113+a2…13+a3613+a3773于是a1,a2,…,a36,a37和13+a1,13+a2,…,13+a36,13+a37共74个数取值在1到73之间。一定有两个数相同，且这两数一定是13+ai=aj。于是从第i+1天到第j天这名学生学习了13小时。ex13.设S是平面上6个点的集合，其中没有3个点共线。给由S的点所确定的15条线段着色，将它们或者着成红色，或者着成蓝色。证明：至少存在两个由S的点所确定的三角形或者是红色三角形或者是蓝色三角形。证法一：六个点ABCDEF至少形成一个同色三角形，设此三角形为ABC且为红色。(1)若DEF同色，则得到另一同色三角形。(2)否则DEF必有一条蓝色边，设为DE。考虑从D,E两点分别到A,B,C三点的连线。(2.1)若D或E有两条红色边连到A,B或C，将得到另一红色三角形。(2.2)否则D,E都至少有两条蓝色边连接到A,B和C上。D,E必各有一条蓝色边连到A,B和C三点的同一点(设为C)上，则DEC是蓝色三角形。证法二：任相邻两条边给一个数，若同色则给1，否则给0。(1)任何一个同色三角形对应数1,1,1；任何一个不同色三角形对应数1,0,0。六点共有C(6,3)=20个三角形。(2)从一个点出发的边有5条，共10对，至少有4对同色，对应数的和大于等于4，所有点对应数的和大于等于24。若没有同色三角形，则所有数的和是20；若只有一个同色三角形，则所有数的和是22.所以至少有两个同色三角形。ex16.证明：在一群n1个人中，存在两人，他们在这群人中有相同数目的熟人(假设自己不是自己的熟人)。证明：n个人，每人的熟人数记为ai，即a1,a2,…,an，取值于0到n-1之间。由于有人认识0个人和有人认识n-1个人不会同时出现。所以这n个数的取值只有n-1种，从而必有两人熟人数相同。第4章生成排列和组合ex6,7,23,24,33,52ex6.确定{1,2,…,8}的下列排列的逆序列。(a)35168274(b)83476215解：(a)24040010(b)65113210ex7.构造{1,2,…,8}的排列，使得其逆序列是(a)25502110(b)66142100解：a)48165723b)73658412ex23.确定下列9阶反射Gray码中9元组的直接后继(a)010100110(b)110001100(c)11