测试2 您的名学： 计算器在考试中是不允许使用的。 您可以使用一张在两侧都由您自己写的笔记的8.5×11”的纸，自是不能有其他的信 息源。 您可以假设所有的结果米自讲座、笔记，问题集以及复习练习， 在提供的空格处写出您的解蓉。如果香要更多的空同，写在包括阿墨的纸的背面。 保持整洁和写作清晰.您不仅会根据您的答案给分，也根据您表达它门的清嘴程度给分· 考试在下午90结束 祝您好运： 思 分值 得分 评分者 1 10 2 10 3 15 4 15 5 20 6 15 7 15 总分 100 PF文件使用"pdfFactory Pro”试用版本创建ww.fineprint,n
测试 2 您的名字：__________________________ l 计算器在考试中是不允许使用的。 l 您可以使用一张在两侧都由您自己写的笔记的 8.5 × 11’’ 的纸，但是不能有其他的信 息源。 l 您可以假设所有的结果来自讲座、笔记、问题集以及复习练习。 l 在提供的空格处写出您的解答。如果需要更多的空间，写在包括问题的纸的背面。 l 保持整洁和写作清晰。您不仅会根据您的答案给分，也根据您表达它们的清晰程度给分。 l 考试在下午 9:30 结束 l 祝您好运！ 问题 分值 得分 评分者 1 10 2 10 3 15 4 15 5 20 6 15 7 15 总分 100 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
注释，这次考试中，一个“闭形是一个没有求和符号、乘积符号成者.符号的数学表达式。 阶乘和二项式系数可以出现在闭形中。知下面显示的例子。 闭形 非闭形 42 ∑R k= (E+1) i(+) n!+ 3 PF文件使用"pdfFactory Pro”试用版本创建w.finsprint,n
注释：这次考试中，一个“闭形”是一个没有求和符号、乘积符号或者…符号的数学表达式。 阶乘和二项式系数可以出现在闭形中。如下面显示的例子。 闭形 非闭形 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
问题1[10分]令s包括所有的设有大于3质因子的正整数，然后定义： X=】 因此，前面的几个和的项是： 1111,1,11,1 X=i+2+3+4+6+8+g+ ()在方格中写出一个闭形表达式，使符以下等式为真， x-22 j=0k=0 解：每个没有质因数大于3的正整数有形式2，对于某些非负整数万和k。因此，表达式 1 235 使得等式为真。 ()写一个阔形表达式到方格中使得等式为真： X= 解：我们对无限几何和应用公式两次。 PDF文件使用“pdfFactory Pro”试用版本创建，fineprint,cn
问题 1 [10 分] 令 S 包括所有的没有大于 3 质因子的正整数，然后定义： 因此，前面的几个和的项是： (a) 在方格中写出一个闭形表达式，使得以下等式为真。 解：每个没有质因数大于 3 的正整数有形式 2 j 3 k，对于某些非负整数 j 和 k。因此，表达式 使得等式为真。 (b) 写一个闭形表达式到方格中使得等式为真： 解：我们对无限几何和应用公式两次。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
=0 (丽 = =()三 =()(2） PF文件使用"pdfFactory Pro”试用版本创建w.fineprint,cn
PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
问题210分]推导在和 2n 1 一lnk 上的紧匹配上下界的积分式。这里·≥3：。使用图证明您的答案。不要求积分。题的答案 应该是设没有求值的积分。 )在下面空自白处面出您的图。（为了获得完整分数，图必须请楚地说明为什么您的积分界 限是正确的，) 解： 彩= 衫=m+可 1 nn+可 河可 n-1 0 2n 1 Jn-1n(x+1) dx )在这里写出您的积分下界 阳品d血 (©)在这里写出您的基木上界 P诉文件使用"pdfFactory Pro”试用版本创建.fineprint,cn
问题 2 [10 分] 推导在和 上的紧匹配上下界的积分式，这里 n ≥ 3。使用图证明您的答案。不要求积分。您的答案 应该是没有求值的积分。 (a) 在下面空白处画出您的图。（为了获得完整分数，图必须清楚地说明为什么您的积分界 限是正确的。） 解： (b) 在这里写出您的积分下界 (c) 在这里写出您的基本上界 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
问题3：[15分]求解以下莎及到渐近符号的如下问题。这里H是第口个调和数：因此， H=12+12+.+1m ()在右边的能在同行的方格中恰当出璞的符号上真圈。（可能超过一个！） n2 logn Vn+ 2 3-n3) Θ 2 2Hn (In n) ((Inn)1) 0 (1)2(2)O,0(3)Θ，0,2(4)2(5)2. 假设)-sn.在下面的每个陈述如果为真，那么在“e”上画圈.剩余的陈述在“lx“ 上画圈。 f(n)2g(n)2 true false f(n)=O(g(n)】 true false f(n)=o(g(n)】 true false 2fm）=日(29m） true false 解：(a)Tneb)Tre(e)对于所有的6g为f(d)false。令)=n,飘)=+logn PDF文件使用“pdfFactory Pro”试用版本创建，fineprint,cn
问题 3： [15 分] 求解以下涉及到渐近符号的如下问题。这里 Hn是第 n 个调和数；因此， Hn = 1/2 + 1/2 ＋ … + 1/n。 (a) 在右边的能在同行的方格中恰当出现的符号上画圈。（可能超过一个！） 解： 假设 f(n) ~ g(n)。在下面的每个陈述如果为真，那么在“true”上画圈。剩余的陈述在“false” 上画圈。 解：(a) True. (b) True (c) 对于所有的 f，g 为 false (d) false。 令 f(n) = n，g(n) = n + logn。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
问题4[15分别一个误导的MT学生设计了一个自我复制的6270的机器人。这个学生每天 都构造了这样的机器人，从天0开始。在机器人构建之后的天，它建造两个它自己的复制 (在所有的后续天中，机器人忙于被索乒民球一一有620机器人，华竟)。这是前面儿天 发生的事情： 第0天： 学生构造机器人R1, 第1天， 学生构造机器人R:。机器人R:构造机器人R,和R4 第2天， 学生构造机器人R机器人R2构建R和R,:机器人R构造R,和R,且 机器人R构建R和R:机器人R搜索乒乓球。 第3天. 学生构建R2机器人R,-,R:构建机器人R,R机器人R, R,R和R,被索乒乓球， 令T.是在n天结束的时候存在的机器人的个数。因此T。=1,T=4,Tl,T26: ()在天1的时候有多少新的机器人按构建？根据变量T·T,和假设n子2表 示您的答案。 解：在天n1和天n2存在的数字的差，也就是T:一T (b)用递推方程表示丁和充分基例。不要求解递推方程。 解：在天的机器的数量等于在1天机器人的数量，加上两倍昨天构造的机墨人的数 量T-T小，加上1个学生构造的机器人的数量。因此，我们有： T6=1 T1=4 Tn =3Tn-1-2Tn-2+1 (for n 22) (心)一个更被误知道的620学生设计了另一个自我复制的机暑人来捕捉和破坏第一种 机器人。在天结束的时候的这种类型的机器人的数量是P,这里： Po=0 P=1 Pn =5Pn-1-6Pn-2+1 (for n 2) 为P找到一个闭形表达式。清楚地说明您的工作米获得部分分数。 解：特征方程是x25x+6-0。右边的因子是(x2x-3),因此根是2和3。对于特解， 让我们首先猜测P。=©，替换这个递推方程给出e=5c-6e+1,这按暗示c=12,因此， 解的一般形式是： Pm=A.2”+B.3"+1/2 带入=0和P,=1给出方程 F文件使用"pdfFactory Pro”试用版本创建，fineprint,cn
问题 4 [15 分] 一个误导的 MIT 学生设计了一个自我复制的 6.270 的机器人。这个学生每天 都构造了这样的机器人，从天 0 开始。在机器人构建之后的天，它建造两个它自己的复制。 （在所有的后续天中，机器人忙于搜索乒乓球――有 6.270 机器人，毕竟）。这是前面几天 发生的事情： 第 0 天： 学生构造机器人 R1。 第1天． 学生构造机器人 R2。机器人 R1构造机器人 R3和 R4. 第2天． 学生构造机器人 R5。机器人 R2构建 R6和 R7，机器人 R3构造 R8和 R9，且 机器人 R4构建 R10和 R11。机器人 R1搜索乒乓球。 第3天． 学生构建 R12。机器人 R5，...，R11构建机器人 R13，…，R26。机器人 R1， R2，R3，和 R4搜索乒乓球。 令 Tn是在 n 天结束的时候存在的机器人的个数。因此 T0＝1，T1＝4，T2=11，T3=26。 (a) 在天 n-1 的时候有多少新的机器人被构建？根据变量 Tn-1，Tn-2，…和假设 n≥2 表 示您的答案。 解：在天 n-1 和天 n-2 存在的数字的差，也就是 Tn-1 － Tn-1 (b) 用递推方程表示 Tn和充分基例。不要求解递推方程。 解：在天 n 的机器的数量等于在 n-1 天机器人的数量，加上两倍昨天构造的机器人的数 量(Tn-1 – Tn-2)，加上 1 个学生构造的机器人的数量。因此，我们有： (c ) 一个更被误知道的 6.270 学生设计了另一个自我复制的机器人来捕捉和破坏第一种 机器人。在天 n 结束的时候的这种类型的机器人的数量是 Pn，这里： 为 Pn找到一个闭形表达式。清楚地说明您的工作来获得部分分数。 解：特征方程是 x 2 -5x +6 = 0。右边的因子是(x-2)(x-3)，因此根是 2 和 3。对于特解， 让我们首先猜测 Pn = c。替换这个递推方程给出 c = 5c – 6c + 1，这按暗示 c = 1/2。因此， 解的一般形式是： 带入 P0 = 0 和 P1 = 1 给出方程： PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
0=A+B+1/2 1=2A+3B+1/2 其解这个系统给出A-2且B一32。因此，解是： 3 P=-22”+23”+1/2 PF文件使用"pdfFactory Pro”试用版本创建w.finsprint,cn
其解这个系统给出 A = -2 且 B ＝ 3/2。因此，解是： PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
间题5②0分]求解以下计数问题。您的答案匹须是形的，但是不需委化简。特别的，您 可以在您的问答中自下阶乘和二项式系数，为了符合部分分数，您必观解释您是如何得到您 的答案的。 a四个棒玩家Alke,Beb,Caod和Dav)是从一刚52张牌中分发7张肉一把，这能有多 少种不司的方法来完成？ 解：有52个包括7个A,7个B和7个C,7个D,24个X(表示在桌子上剩余的扑克)的符 号序列。由Bookkeep线则得，因此分发牌的方法有： 51l 71424 (b)Sink内y Peterson决定在他的床下面开设一个虫子农场，也打算从4个基本物种选择100 个虫子问界：crpy,crawly,.fy和slimey:假设能想要每种至少选I0个，有多少 种不同的可能的分布呢？（例如，一种可能的是20个cr野，20个crawly,10个 和50个slimey。） 解：首先，他在他的床上每种放0个样本，然后他必领从4种虫子中透择剩会的60个虫子， 在这种遮择和63比特的恰好有3个1的序列有一个双射，因此通过B0k心p规则得到分 布的数目是： 631 63 60!3别 60 (c)在比赛中有n个跑步运动员。在比赛前，每个选手分配一个1到n的数学。选手在n 之一中的任何顺序完成比赛。在多少这纯顺序是第一个完成者不是華，第二个完成者 不是#2，第三个完成者不是#3？ 解：令几是在选手k是第k个完成者的完成顺序的集合。在这些项中，解是： n!-|RUPUP=-(乃+lP+B -RORI-ROBI-IRORI +RORORl) =n!-3(n-1)1+3(n-2)1-(n-3川 (@存在多少种方法米停放4个相同的SUV和10个相同的汽车在有20个停放空间的一行 中，如果SUV是太宽以致于不能挨着停放？例如这里是一个可能的停放： U U U U 解：首先，让我们停放SUV。完成这件事情的方法等于从书架上选择0木数，使得相邻的 17 书不被选择一一一个你以前见到的问题。答案是《4)。现在，10量车能在16个剩余的空 PDF文件使用“pdfFactory Pro”试用版本创建，fineprint,cn
问题 5 [20 分] 求解以下计数问题。您的答案必须是闭形的，但是不需要化简。特别的，您 可以在您的回答中留下阶乘和二项式系数。为了符合部分分数，您必须解释您是如何得到您 的答案的。 (a) 四个牌玩家(Alice，Bob，Carol 和 Dave)是从一副 52 张牌中分发 7 张牌一把。这能有多 少种不同的方法来完成？ 解：有 52 个包括 7 个 A，7 个 B 和 7 个 C，7 个 D，24 个 X(表示在桌子上剩余的扑克)的符 号序列。由 Bookkeeper 规则得，因此分发牌的方法有： (b) Stinky Peterson 决定在他的床下面开设一个虫子农场。他打算从 4 个基本物种选择 100 个虫子饲养：creepy， crawly， fuzzy 和 slimey。假设他想要每种至少选 10 个，有多少 种不同的可能的分布呢？(例如，一种可能的是 20 个 creepy，20 个 crawly，10 个 fuzzy 和 50 个 slimey。) 解：首先，他在他的床上每种放 10 个样本。然后他必须从 4 种虫子中选择剩余的 60 个虫子。 在这种选择和 63 比特的恰好有 3 个 1 的序列有一个双射，因此通过 Bookkeeper 规则得到分 布的数目是： (c) 在比赛中有 n 个跑步运动员。在比赛前，每个选手分配一个 1 到 n 的数字。选手在 n! 之一中的任何顺序完成比赛。在多少这些顺序是第一个完成者不是＃1，第二个完成者 不是#2，第三个完成者不是#3? 解：令 Pk是在选手#k 是第 k 个完成者的完成顺序的集合。在这些项中，解是： (d) 存在多少种方法来停放 4 个相同的 SUV 和 10 个相同的汽车在有 20 个停放空间的一行 中，如果 SUV 是太宽以致于不能挨着停放？例如这里是一个可能的停放： 解：首先，让我们停放 SUV。完成这件事情的方法等于从书架上选择 20 本数，使得相邻的 书不被选择―― 一个你以前见到的问题。答案是 。现在，10 量车能在 16 个剩余的空 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
16 间以10)方式停放。因此总的停放的可能数是： (( (©)一个可移动物悬柱结构从7个横着放着的杆（用实线表示），7个垂直的绳子（用点线表 示》，和8个玩具（用字厚AH表示）。 A B C D E H 许多不同的玩具安排能通过扭曲绳子来得到。例如。扭由标号一>箭头的绳子能交换玩具A 和B。扭曲标记←的绳子能颜转玩具E,F,G和H.令一方面没有损由交换玩具B和C 的组合。两个移动物是不同的。如果一个能通过扭由绳子获得另一个，有多少个不月的可能 的移动物： 解：有8！种不阿序列的万绝。每种移动物能技配置2不月的方式。通过扭转或者不扭转7 个上面的绳子。因此，存在2到1的从序列到移动物的映射。通过除法规则，不洞的移动 物的数量是812一3引5。 PF文件使用"pdfFactory Pro”试用版本创建ww.fineprint,n
间以 方式停放。因此总的停放的可能数是： (e) 一个可移动物悬挂结构从 7 个横着放着的杆（用实线表示），7 个垂直的绳子（用点线表 示），和 8 个玩具（用字母 A-H 表示）。 许多不同的玩具安排能通过扭曲绳子来得到。例如，扭曲标号－>箭头的绳子能交换玩具 A 和 B。扭曲标记 ß-的绳子能翻转玩具 E，F，G 和 H。令一方面没有扭曲交换玩具 B 和 C 的组合。两个移动物是不同的，如果一个能通过扭曲绳子获得另一个。有多少个不同的可能 的移动物？ 解：有 8！种不同序列的万绝。每种移动物能被配置 2 7不同的方式，通过扭转或者不扭转 7 个上面的绳子。因此，存在 2 7 到 1 的从序列到移动物的映射。通过除法规则，不同的移动 物的数量是 8!/27 = 315。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn