《组合数学作业1-8.doc》由会员分享，可在线阅读，更多相关《组合数学作业1-8.doc（16页珍藏版）》请在金锄头文库上搜索。
1、11） 在边长为1的等边三角形内任意放10个点，证明一定存在 两个点，其距离不大于1/3。证：如图所示：在三角形的边上加两个点等分每条边，把大三角形分别9个边长为1/3的小三角形。由鸽巣原理：10个点中一定存在两个点落于同一个小三角形，其距离不大于1/3。2）在边长为1的三角形内放个点，则把三角形分割成n-1个小三角形。由鸽巣原理可知：个点必有两点落于同一个小三角形内，则其距离不大于1/n.2证： m个数，i=1,2.m.设 0m-1当=0时，存在一个整数可以被m整除。当从1.m-1这m-1个中取值，那么m个中只有m-1种可能，则鸽巣原理可知：必存在j和k，使得,jk,即有3.证：有理数可由整
2、数和分数组成。当为整数时，存在以0为循环的循环小数。当为分数时，若分数是有限的循环小数，则存在以0为循环的循环小数。若分数是无限循环的循环小数，则肯定存在某一位后以某一位为循环的循环小数。4证：设全部由7组成的N+1个数，7，77，777，,7777。77（N+1个7）存在整数N，由7组成的数除以N，以代表N+1中的数。即=Nq+ 0 N-1则存在0.N-1这n个数，则鸽巣原理可知：必定存在两个数使得 是N 的倍数 组合数学第2次作业25 证明在任意选取的n+1个正整数中存在着两个正整数，其差能被n整除。解：设任意n+1正整数，任意取两个整数的差为=,ij.差除以n的余数为。 0n-1 如果存
3、在i，使得=0.则可以被n整除，对所有i，i=1,2 。n都有0则这n个i中只能取1,2.。n-1。这n-1种情况。由鸽巢原理可知，必存在i和j使得，ij，则有= 可以被n整除。证明在任意选取的n+2个正整数中存在着两个正整数，其差能被2n整除或者其和能被2n整除。解：设任意n+2正整数，任意取两个整数的差为=,ij. 差除以2n的余数为。 02n-1 如果存在i，使得=0.则可以被n整除，对所有i，i=1,2 。2n都有0则这2n个i中只能取1,2.。n-1。这2n-1种情况。由鸽巢原理可知，必存在i和j使得，ij，则有= 可以被2n整除。2.6某学生有37天的时间准备时间考试，根据她过去的
4、经验至多需要复习60个小时，但每天至少要复习1小时。证明无论怎样安排都存在连续的若干天，使得她在这些天里恰好复习了13小时。 设是从第1天到第i天复习的总小时，i=1,2，。37.至多复习60个小时。1。60。做序列： 这个序列也是严格单调上升的，且有+1360+13。考察下面的序列： 该序列有84个数，每个数都是小于等于73的正整数，由鸽巢原理可知，必存在i和j使得 (ij）.令n=i-j,该学生在第j+1,j+2,.j+n=i 的连续n 天中复习了13个小时。(P34)3.7把q个负号和p个正号排在一条直线上，使得没有两个负号相邻，证明不同的排法有C（p+1，q）种。证：先把p个正号排在一
5、条直线上，那么就有p+1个间隔，那就可以把q个负号插进这p+1个位置，则就知道其不同的排法有C（p+1，q）种。3.8（1）从整数1,2，、，100中选出两个数，使得他们的差正好是7，有多少种不同的选法。解：从整数1,2，、，100中选出两个数，使得他们的差正好是7的两个数有1和8, 2和9, 3和10, 4和11，、93和100，则一共有93种选法。 （2）如果选出的两个数之差小于等于7，又有多少种选法？解：如果选一个数为1的话，那另一个数就可以是2,3,4,5,6,7,8有7种如果选一个数为2的话，那另一个数就可以是3,4,5,6,7,8,9有7种、如果选一个数是93的话，有94,95,9
6、6,97,98,99,100，也是7种选94，那就有95,96,97,98,99,100 6种选95，那就有96,97,98,99,100 5种选96，那就有97,98,99,100 4种选97，那就有98,99,100 3种选98，那就有99,100 2种选99，那就有100 1种那把上面所有的选法加起来得：937+6+5+4+3+2+1=672则从整数1,2，、，100中选出的两个数之差小于等于7有672种选法。3.20从整数1,2、，1000中选取三个数使得它们的和正好被4整除，问有多少种选法。解：将1,2、1000都除以4，A、余数为0的有4,8,12,16，、1000， 250个B、
7、余数为1的有1，5,9,13，、997， 250个C、余数为2的有2,6,10,14，、998， 250个D、余数为3的有3,7,11,15，、9999， 250个然后再从A,B,C,D中选取三个数可被4整除：在A中取三个数，则有C（250，3）在A,B,D中各取一个数，则有【C（250,1）】3在A中取一个，在C中取两个；在B中取两个和在C中取一个；在C中取一个，再在D中取两个,则有3C(250，2)C(250，1)所以总选法是C（250,3）+【C（250,1）】3+3C（250,2）C（250,1）3.32设S=n1a1，n2a2，nkak，问S的大小不同的各种组合的总数是多少？解：当K
8、=1时，S1=n1a1，S1的组合为，a1，2a1，n1a1，有n1+1个. 当k=2时，S2=n1a1，n2a2，显然S1的组合都是S2的组合，如果对S1的组合加入a2，就可以构成S2的含a2的组合。S1的组合有n1+1个，对其中的每一个组合加入a2的方法有n2种，由乘法法则，S2中含a2的组合有（n1+1）n2个。所以S2的组合有（n1+1）+（n1+1）n2=（n1+1）（n2+1）个。 由归纳法不难证明S=n1a1，n2a2，nkak的各种组合的总数是 （n1+1）（n2+1）（nk+1）.P624.3解：（1）、 要取的系数，则k=13. 的系数为： （2）要取的系数，且 则只能取k
9、=10,取的系数为：4.4 解：由二项式定理得： （1）、 （2）、对任意的实数r求和解：用任意的实数r求和 实数r的和=4.7方法一： = = 又 =0方法二：= = 由两边同时微分得：令x=1时：左边=0，右边=而又=0 可证！4.16由二项式定理得： =两边同时积分得：= 令x=-1时：左边= ， 右边= = 可证！4.22 用多项式定理展开 解：= ， 的取法有：004的3种，112的3种，220的3种和130的6种。当为004时：有=当为112时：有 +=经计算得： =+6+45.1在1和10000之间不能被4，5，6整除的数有多少个？解：令P1, P2, P3, 分别表示一个整数能
10、被4,5,6整除的性质. 设 S=x|x是整数1x10000 Ai =x|xSx具有性质Pi , i=1,2,3. 则：|A1|=【10000 / 4】=2500 |A2|=【10000 / 5】=2000 |A3|=【10000 / 6】=1666 |A1A2|=【10000 / （4，5）】=【10000 / 20】=500 |A1A3|=【10000 / （4，6）】=【10000 / 12】=833 |A2A3|=【10000 / （5，6）】=【10000 / 30】=333 |A1A2A3|=【10000 / （4，5，6）】=【10000 / 60】=166 由定理得： |123
11、| =10000 -（2500+2000+1666）+（500+833+333）-166 =53345.4确定S= a, 3 b, 5 c, 7 d 的10 - 组合数.解：令T= a, b, c, d ，T的所有10- 组合构成集合W.则由定理3.7得 |W|=286 任取T的一个10- 组合， 如果其中b多于3个则称它具有性质P1， 如果其中c多于5个则称它具有性质P2， 如果其中d多于7个则称它具有性质P3.不难看出所求的10- 组合数就是W中不具性质P1，P2，P3的元素个数.令Ai=x|xWx具有性质Pi ，i=1,2,3. |A1|=84 |A2|=35 |A3|=10 |A1A2
12、|=1 |A1A3|=0 |A2A3|=0 |AbAcAd|=0 由定理得： |123|=286-(84+35+10)=158 5.5 1)确定方程X1+X2+X3=14的不超过8的非负整数解的个数. 解： 方程不超过8的非负整数解，则0x18, 0x28, 0x38. |S|=120 |A1|=21 |A2|=21 |A3|=21 |A1A2|=0 |A1A3|=0 |A2A3|=0 |A1A2A3|=0 由定理得： |123|=120 -21*3=572) 确定方程X1+X2+X3=14的不超过8的正整数解的个数. 解： 方程不超过8的正整数解，则1x18, 1x28, 1x38. 相当于取值为0x17, 0x27, 0x37， x1+x2+x3=11 |S|=78 |A1|=10 |A2|=10 |A3|=10 |A1A2|=0 |A1A3|=0 |A2A3|=0 |A1A2A3|=0 由定理得： |bcd|=
