组合数学作业1-8

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

两个点，其距离不大于1/3。 证：如图所示：

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

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

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

2．证：a1,a2……am m个数，i=1,2…..m. 设 ai?miq?ri 0≤ri≤m-1

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

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

a?ajk?m(q?q)

jk 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个数，则鸽巣原理可知：必定存在两个数

a,aik

使得aj?ak?N(qj?qk) 是N 的倍数

组合数学第2次作业

2．5

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

解：设任意n+1正整数差除以n的余数为

a,a,......a12n?2，任意取两个整数的差为

s=a?akij,i>j.

ri。 ∴0≤

ri≤n-1

可以被n整除，对所有i，i=1,2 。。。。n都有

如果存在i，使得

ri=0.则

a?aijri≠0

则这n个i中只能取1,2.。。。。n-1。这n-1种情况。由鸽巢原理可知，必存在i和j使得

rj?ri，

i＞j，则有

s=a?akij 可以被n整除。

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

解：设任意n+2正整数除以2n的余数为

a,a,......a12n?2，任意取两个整数的差为

s=a?akij,i>j. 差

ri。 ∴0≤

ri≤2n-1

可以被n整除，对所有i，i=1,2 。。。。2n都有

如果存在i，使得

ri=0.则

a?aijri≠0

则这2n个i中只能取1,2.。。。。n-1。这2n-1种情况。由鸽巢原理可知，必存在i和j使得

rj?ri，i＞j，则有sk=ai?aj 可以被2n整除。

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

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

ia?a112?。。。。?a37≤60。

?13,......a37?13

做序列：

a?13,a2这个序列也是严格单调上升的，且有

a37+13≤60+13。考察下面的序列：

a,a,.....a,a?13,a123712?13,......a37?13

该序列有84个数，每个数都是小于等于73的正整数，由鸽巢原理可知，必存在i和j使得

a?aij?13 (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)

3

所以总选法是C（250,3）+【C（250,1）】+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）.

个整数在它们的自然位置上（所谓自然位置就是整数i排在第i位上）

解：由题意可知，从n个数中取n-k个数后，再将n-k个数错位排列，则所求的排列数是：

??Dnn?kn?k??nn?k111n?k?(n?k)!(1?1!?2!???(?1)(n?k)!)

n!111n?k(1?????(?1)) =k!1!2!(n?k)!

5.8定义D0=1，用组合分析的方法证明 n！=

??D???D???Dn0nn11n22????nn?D

0证：n！是对｛1,2…….，n｝进行全排列，

?n0nnnD?D?D????n?1?1?2?2?n?D0

是对｛1,2…….n｝进行分类：

?n?当{1,2,……,n}中有0个数错位排列，则排法为??0??D0

???n?当{1,2,……,n}中有1个数错位排列，则排法为??1??D1

???n?当{1,2,……,n}中有2个数错位排列，则排法为??2??D2

??……..

?n?当{1,2,……,n}中有n个数错位排列，则排法为??n??Dn

??由于加法法则｛1,2……n｝的排法总数为

?n??n??n??n??n??n???0??D0???1??D1?.....???n??Dn???0??Dn???1??D1?......???n??D0 ?????????????n??n??n????n!??Dn??D1?......??D0??????所以： 01n??????5.9证明Dn为偶数当且仅当n为奇数. 证：（反证法）

“?”设n为偶数，则nDn(?1)为奇数，即 n?1为偶数，

Dn?nDn?1?(?1)“

n为奇数，与题设Dn为偶数矛盾，所

以假设不成立。即n为奇数。

?”已知n为奇数，则n-1是偶数，

Dn?(n?1)(Dn?2?Dn?1)为偶数。

综合上所述，Dn为偶数当且仅当n为奇数可证。5.1在1和

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

解：令P1, P2, P3, 分别表示一个整数能被4,5,6整除的性质. 设 S={x|x是整数?1≤x≤10000} Ai ={x|x∈S?x具有性质Pi }, i=1,2,3. 则：|A1|=【10000 / 4】=2500 |A2|=【10000 / 5】=2000 |A3|=【10000 / 6】=1666

|A1∩A2|=【10000 / （4，5）】=【10000 / 20】=500 |A1∩A3|=【10000 / （4，6）】=【10000 / 12】=833 |A2∩A3|=【10000 / （5，6）】=【10000 / 30】=333 |A1∩A2∩A3|=【10000 / （4，5，6）】=【10000 / 60】=166 由定理得： |A1∩A2∩A3|

=10000 -（2500+2000+1666）+（500+833+333）-166 =5334

6.1 計算 f (0)―f(1)＋f(2) ―??＋(?1)f(n) 当n为偶数时：

f (0)―f(1)＋f(2) ―??＋(?1)f(n)

= f (0)＋f(0)+f(2)＋ ??＋f(n―2) 由性质2得： =1+ f(n―2+1)= f(n―1)+1 当n为奇数时：

f (0)―f(1)＋f(2) ―??＋(?1)f(n)

= f (0)―f(1)＋f(2) ―??＋f(n-1)―f(n)+ f(n+1)―f(n+1) = f (0)＋f(0)+f(2)＋ ??＋f(n―1)―f(n+1) 由性质2得： =1+ f(n―1+1)―f(n+1) =1+ f(n)―f(n+1) = f(n―1)+1 6.2 证明下面的等式 ⑴f?n?1??f?n??f(2n)

22nnn∵f?n?1??f?n?1??f?n??f?n?2?? ∵f?n??f?n??f?n?1??f?n?1??

∴f?n?1??f?n??f?n?1??f?n??f?n?2??+f?n??f?n?1??f?n?1?? =f?n?f?n?1??f?n?1?f?n?2?

=f?n?1??f?n?1??f?n?2???f?n?1?f?n?2? =f?n?2??f?n?1??f?n?1???f?n?1?f?n?1? =f?n?2?f?n??f?n?1?f?n?1? 由性质6得：= f(2n)

方法二：直接由性质6得：令2n=(n-1)+(n+1)

∴ f[(n-1)+(n+1)]=f(n+1-1)f(n-1+1)+f(n+1-2)f(n-1)2 =f?n?1??f?n?

⑵f?n?f?n?1??f?n?1?f?n?2?=f(2n) (由第一小题已证出) ⑶f?n??f?n?1??f?n?1??f?3n?2? ∵f(3n+2)=f(2n+1)f(n+1)+f(2n)f(n) f(2n+1)= f(n)f(n+1)+f(n-1)f(n) f(2n)= f(n)f(n)+f(n-1)f(n-1) ∴f(3n+2)=f(2n+1)f(n+1)+f(2n)f(n)

=[f(n)f(n+1)+f(n-1)f(n)]f(n+1)+[f(n)f(n)+f(n-1)f(n-1) ]f(n) =f?n?1?f?n??f?n?1?f?n?f?n?1??f?n??f?n?1?f?n? =f?n?1??f?n?1??f?n?1???f?n?1?f?n?f?n?1??f?n??f?n?1?f?n? =f?n?1??f?n?1?f?n?1??f?n?1?f?n?f?n?1??f?n??f?n?1?f?n?

=f3?n?1??f?n?1??f?n??f?n?1??f?n?1??f?n?1?f?n?f?n?1?+

3232232232333222222 f?n??f?n?1?f?n?

=f?n?1??f?n?1?f?n?1??f?n??f?n?1?f?n? =f?n?1??f?n?1?[f?n?1??f?n?]?f?n? =f?n??f?n?1??f?n?1?

6.4定义级数H1?a,H2?b,且Hn?2?Hn?1?Hn求Hn 解：特征方程为：x2?x?1?0 ∴ x?1?52333323323232

?1?5??1?5?? ?+?∴H=c??2?c?2?????(n)1nn2∵H1?a,H2?b,

?1?5??1?5??1?5??1?5??=b ,c??=a ?+c??+c?∴c??2??2??2??2?????????122212解得：c1?35?55?5a?b 1010c2??35?55?5a?b 1010n35?55?5?1?H(n)=(10a?10b)??5??35?5?+(a?10??2?5?5?1?)b?10?5?? ?2??n

6.5 已知a0?0,a1?1,a2?4a3?12 满足递推关系

a?can1n?1?c2an?2?0

求c1,c2

解a3?c1a2?c2a1?0 a2?c1a1?c2a0?0 代入可求出：c1??4 c2?4

6.5已知a0?0,a1?1,a2?4,a3?12满足递推关系an?c1an?1?c2an?2?0，

求c1和c2. 解：由已知得：??12?4c1?c2?0?c??4，解得：?1.

4?c?0c?41??2

本文来源：https://www.bwwdw.com/article/yk8o.html