当前位置：文档之家 › 组合数学作业1-8

组合数学作业1-8

  • 格式：doc
  • 大小：476.00 KB
  • 文档页数：16

1．1） 在边长为1的等边三角形内任意放10个点，证明一定存在

两个点，其距离不大于1/3。

证：如图所示：

在三角形的边上加两个点等分每条边，把大三角形分别9个边长为1/3的小三角形。由鸽巣原理：10个点中一定存在两个点落于同一个小三角形，其距离不大于1/3。

2）在边长为1的三角形内放mn个点，则把三角形分割成n-1个小三角形。

由鸽巣原理可知：mn个点必有两点落于同一个小三角形内，则其距离不大于1/n.

2．证：,1aa2……am m个数，i=1,2…..m.

设 rmaiiiq 0≤ri≤m-1

当ri=0时，存在一个整数可以被m整除。

当ri从1…..m-1这m-1个中取值，那么m个ri中只有m-1种可能，则鸽巣原理可知：必存在j和k，使得rrkj,j>k,即有)(qqaakjkjm

3.证：

∵有理数可由整数和分数组成。

∴当为整数时，存在以0为循环的循环小数。

∴当为分数时，若分数是有限的循环小数，则存在以0为循环的循环小数。

∴若分数是无限循环的循环小数，则肯定存在某一位后以某一位为循环的循环小数。

4．证：

设全部由7组成的N+1个数，7，77，777，……,7777。。。。77（N+1个7）

存在整数N，由7组成的数除以N，以ai代表N+1中的数。

即ai=Nq+ri 0≤ri≤ N-1

则存在0….N-1这n个数，则鸽巣原理可知：必定存在两个数aaki,

使得)(qqaakjkjN 是N 的倍数

组合数学第2次作业

2．5

⑴ 证明在任意选取的n+1个正整数中存在着两个正整数，其差能被n整除。

解：设任意n+1正整数aaan221,......,，任意取两个整数的差为sk=aaji,i>j.差除以n的余数为ri。 ∴0≤ri≤n-1

如果存在i，使得ri=0.则aaji可以被n整除，对所有i，i=1,2 。。。。n都有ri≠0

则这n个i中只能取1,2.。。。。n-1。这n-1种情况。由鸽巢原理可知，必存在i和j使得rrij，i＞j，则有sk=aaji 可以被n整除。

⑵证明在任意选取的n+2个正整数中存在着两个正整数，其差能被2n整除或者其和能被2n整除。

解：设任意n+2正整数aaan221,......,，任意取两个整数的差为sk=aaji,i>j. 差除以2n的余数为ri。 ∴0≤ri≤2n-1

如果存在i，使得ri=0.则aaji可以被n整除，对所有i，i=1,2 。。。。2n都有ri≠0

则这2n个i中只能取1,2.。。。。n-1。这2n-1种情况。由鸽巢原理可知，必存在i和j使得rrij，i＞j，则有sk=aaji 可以被2n整除。

2.6某学生有37天的时间准备时间考试，根据她过去的经验至多需要复习60个小时，但每天至少要复习1小时。证明无论怎样安排都存在连续的若干天，使得她在这些天里恰好复习了13小时。

设ai是从第1天到第i天复习的总小时，i=1,2，。。。37.至多复习60个小时。

∴1≤aa21。。。。a37≤60。

做序列：

13,......13,133721aaa

这个序列也是严格单调上升的，且有a37+13≤60+13。考察下面的序列：

,,.....,3721aaa13,......13,133721aaa

该序列有84个数，每个数都是小于等于73的正整数，由鸽巢原理可知，必存在i和j使得13aaji (i>j）.令n=i-j,该学生在第j+1,j+2,…..j+n=i 的连续n 天中复习了13个小时。

(P34)3.7把q个负号和p个正号排在一条直线上，使得没有两个负号相邻，证明不同的排法有C（p+1，q）种。

证：先把p个正号排在一条直线上，那么就有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,96,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种

那把上面所有的选法加起来得：93×7+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、余数为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={n1·a1，n2·a2，……，nk·ak}，问S的大小不同的各种组合的总数是多少？

解：当K=1时，S1={n1·a1}，S1的组合为∅，{a1}，{2·a1}，……，{n1·a1}，有n1+1个.

当k=2时，S2={n1·a1，n2·a2}，显然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={n1·a1，n2·a2，……，nk·ak}的各种组合的总数是 （n1+1）·（n2+1）·……·（nk+1）. P62

4.3

解：（1）、)2()3()23(181801818yxCyxkkkk

∵要取yx135的系数，则k=13.

∴yx135的系数为：)2(31351318C

（2）∵要取yx98的系数，且CCknknkn11

∴)2()3()23(11171801171818yxCyxkkkkk

则只能取k=10,取yx98的系数为：1018)2(398917C

4.4

解：由二项式定理得：

（1）、 2)21(30knkknnnC

（2）、对任意的实数r求和rCknkkn0

解：用任意的实数r求和rCknkkn0

实数r的和)1(rn=rCknkkn0

4.7

方法一：∵CCknknnk11 ∴CCCnnn32132……Cnnnn)1(1

=CCCnnnnnn211101……Cnnnn)1(1

=CCCnnnn211101[…… ])1(1Cnnn

又∵CCknnkn111 ∴CCCnnnn211101[……])1(1Cnnn

=0

方法二：∵)1(xn=)(0xCknkkn =xCkknkkn)1(0

由两边同时微分得：)1(1xnnxCkknkknk11)1(

令x=1时：左边=0，右边=)1(1knkknCk

而又∵CCCnnn32132……Cnnnn)1(1=)1(1knkknCk

∴CCCnnn32132……Cnnnn)1(1=0 可证！

4.16

由二项式定理得：

)1(xn=xCknkkn0

两边同时积分得：

)1(111xnn—11n=xCknkknk1011

令x=-1时：左边=112nn ，

右边=)1(1011knkknkC=111)1(11knkknkC

∴11n =111)1(11knkknkC

∴111n)1(1111knkknkC

=1nn 可证！ 4.22 用多项式定理展开)(3214xxx

解：)(3214xxx=)(321nnnnnxxnnn321321 ，nnnn321

∴nnn321,,的取法有：004的3种，112的3种，220的3种和130的6种。

当nnn321,,为004时：有x410044x420440x434040=xxx434241

当nnn321,,为112时：有

)21412321(xxx+)12413221(xxx+)11423221(xxx

=xxx232112xxx322112xxx322112

………经计算得：

)(3214xxx

=xxx434241+xxx2321(12+xxx3221+)3221xxx+6)(232122212322xxxxxx

+4)(323313312331321332xxxxxxxxxxxx

5.1在1和10000之间不能被4，5，6整除的数有多少个？

解：令P1, P2, P3, 分别表示一个整数能被4,5,6整除的性质.

合集下载

组合数学作业答案

组合数学作业答案

.

精品 第二章作业答案

7. 证明，对任意给定的52个整数，存在两个整数，要么两者的和能被100整除，要么两者的差能被100整除。

证明 用100分别除这52个整数，得到的余数必为0, 1,…, 99这100个数之一。将余数是0的数分为一组，余数是1和99的数分为一组，…，余数是49和51的数分为一组，将余数是50的数分为一组。这样，将这52个整数分成了51组。由鸽巢原理知道，存在两个整数分在了同一组，设它们是a和b。若a和b被100除余数相同，则ba能被100整除。若a和b被100除余数之和是100，则ba能被100整除。

11. 一个学生有37天用来准备考试。根据过去的经验，她知道她需要不超过60小时的学习时间。她还希望每天至少学习1小时。证明，无论她如何安排她的学习时间（不过，每天都是整数个小时），都存在连续的若干天，在此期间她恰好学习了13小时。

证明 设从第一天到第i天她共学习了ia小时。因为她每天至少学习1小时，所以3721,,,aaa和13,,13,133721aaa都是严格单调递增序列。因为总的学习时间不超过60小时，所以6037a，731337a。3721,,,aaa,

13,,13,133721aaa是1和73之间的74个整数，由鸽巢原理知道，它们中存在相同的整数，有ia和13ja使得13jiaa，13jiaa，从第1j天到第i天她恰好学习了13小时。

14. 一只袋子装了100个苹果、100个香蕉、100个桔子和100个梨。如果我每分钟从袋子里取出一个水果，那么需要多少时间我就能肯定至少已拿出了1打相同种类的水果？

解 由加强形式的鸽巢原理知道，如果从袋子中取出451)112(4个水果，则能肯定至少已拿出12个相同种类的水果。因此，需要45分钟。

17. 证明：在一群1n个人中，存在两个人，他们在这群人中有相同数目的熟人（假设没有人与他/她自己是熟人）。

组合数学 卢 习题答案

组合数学 卢 习题答案

组合数学 卢 习题答案

组合数学是数学的一个分支，研究的是离散的对象之间的组合方式和计数方法。它在解决实际问题中有着广泛的应用，例如密码学、图论、组织管理等领域。本文将为读者提供一些卢习题的答案，帮助读者更好地理解和掌握组合数学的知识。

1. 卢习题一：从一个有10个字母的字母表中选取3个字母，可以有多少种不同的选择方式？

解答：根据组合数学的知识，从n个不同元素中选取k个元素的组合数可以用C(n,k)表示。在这个问题中，n=10，k=3，所以答案为C(10,3) = 10! / (3! * (10-3)!) = 120 种不同的选择方式。

2. 卢习题二：一个班级有20名学生，其中10名男生和10名女生。如果要从这个班级中选取5名学生组成一个小组，其中至少有2名男生和2名女生，有多少种不同的选取方式？

解答：这个问题可以用组合数学中的排列组合原理来解决。首先，我们可以分两种情况来考虑：一种是选取3名男生和2名女生，另一种是选取2名男生和3名女生。

对于第一种情况，选取3名男生的方式有C(10,3) = 120种，选取2名女生的方式有C(10,2) = 45种，所以总共有120 * 45 = 5400种不同的选取方式。

对于第二种情况，选取2名男生的方式有C(10,2) = 45种，选取3名女生的方式有C(10,3) = 120种，所以总共有45 * 120 = 5400种不同的选取方式。

将两种情况的结果相加，总共有5400 + 5400 = 10800种不同的选取方式。

3. 卢习题三：有一个由0和1组成的8位二进制数，其中至少有3个1。问这样的二进制数有多少个？

解答：这个问题可以用组合数学中的排列组合原理来解决。首先，我们可以分两种情况来考虑：一种是有3个1，另一种是有4个1、5个1、6个1、7个1和8个1。

对于第一种情况，选取3个位置放置1的方式有C(8,3) = 56种。

对于第二种情况，选取4个位置放置1的方式有C(8,4) = 70种，选取5个位置放置1的方式有C(8,5) = 56种，选取6个位置放置1的方式有C(8,6) = 28种，选取7个位置放置1的方式有C(8,7) = 8种，选取8个位置放置1的方式有C(8,8) = 1种。

《组合数学》测试题含答案

《组合数学》测试题含答案

----完整版学习资料分享---- 测 试 题

——组合数学

一、选择题

1. 把101本书分给10名学生，则下列说法正确的是（）

A.有一名学生分得11本书 B.至少有一名学生分得11本书

C.至多有一名学生分得11本书 D.有一名学生分得至少11本书

2. 8人排队上车，其中A，B两人之间恰好有4人，则不同的排列方法是（）

A.!63 B.!64 C. !66 D. !68

3. 10名嘉宾和4名领导站成一排参加剪彩，其中领导不能相邻，则站位方法总数为（）

A.4,11!10P B. 4,9!10P

C. 4,10!10P D. !3!14

4. 把10个人分成两组，每组5人，共有多少种方法（）

A.510 B.510510

C.49 D.4949

5. 设x,y均为正整数且20yx，则这样的有序数对yx,共有（）个

6. 仅由数字1，2，3组成的七位数中，相邻数字均不相同的七位数的个数是（）

A.128 B

7. 百位数字不是1且各位数字互异的三位数的个数为（）

8. 设n为正整数，则nkkn02等于（）

A.n2 B. 12n C. nn2 D. 12nn

9. 设n为正整数，则kknkkn310的值是（）

A.n2 B. n2 C. n2

10. 设n为正整数，则当2n时，nkkk22=()

----完整版学习资料分享---- A.3n B. 21n C. 31n D. 22n

排列与组合练习题及解析

排列与组合练习题及解析

排列与组合练习题及解析

在数学中，排列和组合是组合数学中的基本概念。排列是指从给定的元素集合中选取一些元素并按照一定的顺序排列，而组合是指从给定的元素集合中选取一些元素并形成一个集合，不考虑顺序。在此，我们提供一些排列与组合的练习题，并给出详细的解析过程。

1. 排列问题：

(1) 从10个不同的球中，按照一定的顺序取出5个球，问共有多少种不同的结果？

解析：排列问题要考虑元素的顺序，因此可以使用排列公式进行计算。对于这个问题，可以使用10个不同的球中取出5个球的排列数公式：

P(10, 5) = 10! / (10-5)! = 10 * 9 * 8 * 7 * 6 = 30,240

因此，共有30,240种不同的结果。

(2) 一个由字母组成的字符串，字母顺序可以重复，共有8个字母。从中选取4个字母组成字符串，问共有多少种不同的结果？

解析：同样地，对于这个问题，我们可以使用排列公式进行计算。从8个字母中选取4个字母的排列数为：

P(8, 4) = 8! / (8-4)! = 8 * 7 * 6 * 5 = 1,680

因此，共有1,680种不同的结果。

2. 组合问题： (1) 从10个不同的球中，按照任意顺序取出5个球，问共有多少种不同的结果？

解析：与排列问题不同的是，组合问题不考虑元素的顺序。那么我们可以使用组合公式进行计算。对于这个问题，可以使用10个不同的球中取出5个球的组合数公式：

C(10, 5) = 10! / (5! * (10-5)!) = 10 * 9 * 8 * 7 * 6 / (5 * 4 * 3 * 2 * 1) =

252

因此，共有252种不同的结果。

(2) 一个由字母组成的字符串，字母顺序可以重复，共有8个字母。从中选取4个字母组成字符串，问共有多少种不同的结果？

解析：同样地，对于这个问题，我们可以使用组合公式进行计算。从8个字母中选取4个字母的组合数为：