《集合论与图论》课堂练习2 (2006年4月12日13:30-15:10复旦大学计算机系05级) 学号 姓名 注意:有关计数的答案可用P(,M),C(m,r),nk,k,及数字等表示 、填空题(55分) 1.s(s≥1)个元素分成t个组,那么必存在一个组至少含有「s1个元素 *鸽笼原理/定理102* 2.20000到70000间的偶数中由不同数字组成的5位数的个数共有3×4×P(8 3)+2x5×P(83)=4032+33607392 /设所求的数为 abcde这5位数,其中2≤a≤6,e∈{0,2,4,6,8}; 若a∈{2,4,6},e有4种选择,bed有P(8,3)种选择,根据乘法法则,则有3×4xP(8, 3)种可能 若a∈{3,5},e有5种选择,bcd有P(8,3)种选择,根据乘法法则,则有2×5×P(8, 3)种可能 根据加法法则,共有3×4×P(8,3)+2×5×P(8,3)=4032+3360=7392种可能。* 3.5对夫妻出席一宴会,围一圆桌坐下。有1010或9 种不同的方 案。若要求夫妻相邻,有_25×4(=768 种不同的方案。 件环排列 夫妻相邻,5个元素的环排列:5!/5=4!;一对夫妻可以交换位置:25;根据乘法 法则,有25×4!(=768)种不同的方案。* 4.从1到300间任取3个不同的数,使得这3个数的和正好被3除尽,有3XC0O 3)+100(=148510种方案 5.(x+y+z)0有C0+3-110)项。 6.(2x+y+的展开式中的xjyz4系数是_23×8/3114 /根据二项式定理,C(n,ka-kb,23×C(8,3)×C(5,1=23×8/3!14)*+/ 7.排列字母 ILLINOIS可以得到8/3|2) 个不同的字符串;如 果要求某个I排在某个L之前,可以得到_8/(32)8×7×6 个不同的 字符串。 先计算所有的L都在任一I之前的字符串,再用字符串总数减去这样的字符
《集合论与图论》课堂练习 2 （2006 年 4 月 12 日 13:30-15:10 复旦大学计算机系 05 级） 学号 姓名 注意：有关计数的答案可用 P(n,k),C(n,r),nk ,k!,及数字等表示 一、 填空题（55 分） 1． s（s1）个元素分成 t 个组，那么必存在一个组至少含有 s/t 个元素。 /*鸽笼原理/定理 10.2*/ 2． 20000 到 70000 间的偶数中由不同数字组成的 5 位数的个数共有 34P(8, 3)+25P(8, 3)=4032+3360=7392 。 /*设所求的数为 abcde 这 5 位数，其中 2a6，e{0，2，4，6，8}； 若 a{2，4，6}，e 有 4 种选择，bcd 有 P(8, 3)种选择，根据乘法法则，则有 34P(8, 3)种可能； 若 a{3，5}，e 有 5 种选择，bcd 有 P(8, 3)种选择，根据乘法法则，则有 25P(8, 3)种可能； 根据加法法则，共有 34P(8, 3)+25P(8, 3)=4032+3360=7392 种可能。*/ 3．5 对夫妻出席一宴会，围一圆桌坐下。有 10!/10 或 9! 种不同的方 案。若要求夫妻相邻，有 2 54!(=768) 种不同的方案。 /*环排列； 夫妻相邻，5 个元素的环排列：5!/5=4!；一对夫妻可以交换位置：2 5；根据乘法 法则，有 2 54!(=768)种不同的方案。*/ 4．从 1 到 300 间任取 3 个不同的数，使得这 3 个数的和正好被 3 除尽，有 3C (100, 3)+1003 (=1485100) 种方案。 5．(x+y+z)10 有_C(10+3-1, 10)__项。 6．(2x+y+z)8 的展开式中的 x 3yz4 系数是 2 38!/(3!1!4!) 。 /*根据二项式定理，C(n, k)an-kb k , 23C(8, 3)C(5, 1)= 238!/(3!1!4!)*/ 7．排列字母 ILLINOIS 可以得到 8!/(3!2!) 个不同的字符串；如 果要求某个 I 排在某个 L 之前，可以得到 8!/(3!2!)-876 个不同的 字符串。 /*先计算所有的 L 都在任一 I 之前的字符串，再用字符串总数减去这样的字符串
的个数即可; 构造一个所有的L都在任一I之前的字符串分两步:首先选择N、O和S的位置, 再将I和L插入。为N、O和S选定位置有8×7×6种方法,当N、O和S选定位 置后,I和L只有一种插入方法。字母 ILLINOIS组成的字符串共有8(32)个, 所以可得8/(3!2!)8×7×6个不同的字符串。* 8.利用二项式定理展开(s-)4。③)/=C40)s4+C4s3()+C42s2(r)2 C(43/)2+C44/r)4=s4-4s+6s2r2-4sr3+r。 9.整除510510的正奇数有 64 个 510510=2*3*5*7*11*13*17,所以整除510510的正奇数个数等于3*5*7*11*13*17 的正约数个数,为(1+1)=26=64 、综合题(45分,5×9分=45分) 1.证明:在任意给出的n+1(n≥2)个正整数中必有两个数,它们的差能被n整 除 证明:设所给的n+1个正整数a,a2,,ax+1,A={a,a,,a+},AF=n+1。对任 个不大于n的正整数i,令A产{a|a∈A且a除以n所得余数为i1},则AcA(i=1 2,…,n)且AA2U.∪An=A。由鸽笼原理,必有正整数k(1≤k≤n),使得A≥2 设a,a是Ak中的两个元,则它们除以n所得的余数均为k-1,于是a-a能被n 整除。 2.矩形被分为3×7=21个正方形,每个正方形用红色或黑色着色。证明存在非 简单子矩形(非1×k或kx1),4个角的正方形颜色相同 解:设共有3行,7列牌。将同一列的两个同色的牌称为“同色对”。根据鸽笼 原理,每一列至少有一个同色对,所以整个矩形含有7个同色对,每列一个。再 根据鸽笼原理,至少有4个同色对的颜色完全相同,不妨设有4个红色的同色对 同色对在一列中有3种可能,再次根据鸽笼原理,这4个同色对至少有两个在列 中具有相同的位置。这两个同色对的4个牌确定的矩阵满足条件。 3.证明杨辉三角形定理:对于任意的1≤ksn,则Cmn+1,k=Cm,k)+Cm,k-1 /*见课件* 4.某学生在37天里共做了60道数学题。已知他每天至少做1道题。求证:必 存在连续的若干天,在这些天里该学生恰做了13道数学题。 证明参见教材219页例10.4,类似方法。 5.设A含有n个元素的集合{x,x,……,x},证明|P(A)|=2。 X1X2Xn
的个数即可； 构造一个所有的 L 都在任一 I 之前的字符串分两步：首先选择 N、O 和 S 的位置， 再将 I 和 L 插入。为 N、O 和 S 选定位置有 876 种方法，当 N、O 和 S 选定位 置后，I 和 L 只有一种插入方法。字母 ILLINOIS 组成的字符串共有 8!/(3!2!)个， 所以可得 8!/(3!2!)- 876 个不同的字符串。*/ 8. 利 用 二 项 式 定 理 展 开 (s-r)4 。 (s-r)4=C(4,0)s4+C(4,1)s3 (-r)+C(4,2)s2 (-r)2+ C(4,3)s(-r)3+C(4,4)(-r)4 =s4 -4s3 r+6s2 r 2 -4sr3+r4。 9．整除 510510 的正奇数有 64 个。 510510=2*3*5*7*11*13*17，所以整除 510510 的正奇数个数等于 3*5*7*11*13*17 的正约数个数，为(1+1)6=26=64 二、综合题（45 分，59 分=45 分） 1．证明：在任意给出的 n+1（n2）个正整数中必有两个数，它们的差能被 n 整 除。 证明：设所给的 n+1 个正整数 a1, a2, …,an+1, A={ a1, a2, …,an+1}, |A|=n+1。对任一 个不大于 n 的正整数 i，令 Ai={a | aA 且 a 除以 n 所得余数为 i-1}，则 AiA(i=1, 2, …, n)且 A1A2…An=A。由鸽笼原理，必有正整数 k(1kn)，使得|Ak|2。 设 ai, aj 是 Ak 中的两个元，则它们除以 n 所得的余数均为 k-1，于是 ai-aj 能被 n 整除。 2．矩形被分为 37=21 个正方形，每个正方形用红色或黑色着色。证明存在非 简单子矩形（非 1k 或 k1），4 个角的正方形颜色相同。 解：设共有 3 行，7 列牌。将同一列的两个同色的牌称为“同色对”。根据鸽笼 原理，每一列至少有一个同色对，所以整个矩形含有 7 个同色对，每列一个。再 根据鸽笼原理，至少有 4 个同色对的颜色完全相同，不妨设有 4 个红色的同色对。 同色对在一列中有 3 种可能，再次根据鸽笼原理，这 4 个同色对至少有两个在列 中具有相同的位置。这两个同色对的 4 个牌确定的矩阵满足条件。 3．证明杨辉三角形定理: 对于任意的 1 k n，则 C(n+1, k)=C(n, k)+C(n, k-1)。 /*见课件*/ 4． 某学生在 37 天里共做了 60 道数学题。已知他每天至少做 1 道题。求证：必 存在连续的若干天，在这些天里该学生恰做了 13 道数学题。 证明参见教材 219 页例 10.4，类似方法。 5．设 A 含有 n 个元素的集合{x1, x2, ……, xn}，证明|P(A)|=2n。 x1x2xn