期末考试 您的名学： ·这是开卷考试。但是。计算题是不允许使用的 您可以假设所有的结果米自讲座、笔记，问题集以及复习练习， 在提供的空格处写出您的解容。如果需要更多的空间，包括问题写在的纸的肯面。 保持整洁和写作清晰，您不仅会根据您的答案给分，也根据能表达它门们的清晰程度给分， 考试在下午90结束 祝您好运！ 问思 分值 得分 评分者 1 15 2 10 3 10 4 10 15 10 6 15 7 10 8 10 9 10 总分 100 P诉文件使用”pdfFactory Pro”试用版本创建.fineprint,cn
期末考试 您的名字：______________________ l 这是开卷考试。但是，计算器是不允许使用的 l 您可以假设所有的结果来自讲座、笔记、问题集以及复习练习。 l 在提供的空格处写出您的解答。如果需要更多的空间，包括问题写在的纸的背面。 l 保持整洁和写作清晰。您不仅会根据您的答案给分，也根据您表达它们的清晰程度给分。 l 考试在下午 9:30 结束 l 祝您好运！ 问题 分值 得分 评分者 1 15 2 10 3 10 4 10 5 10 6 15 7 10 8 10 9 10 总分 100 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
间题110分]考虑以下谓词序列： Q1(x1)=r1 Q2(x1,x2)=xT1÷2 Q3(x1,x2,3)=(x1→2)→xg Q(1,x2,3,x4)=(x1→2)→x3)→x4 Q6(r1,x2,3,x4,5)=((x1→2)→x3)→4)→6 令T对于Q1X)为真的变量1，人是不同真/假设置的数字。例如。T2=3,因 为Qx1x小对于变量x和的三种不河设置. 1x2 Q2(x1,t2) TT T T F F FT T FF T (a)根据T。表示T+,假设n≥ 解：我门有： Qn+1(1,x2,,xm+1）=Qn(x1,r2,,xn)÷xn+1 如果无+1=1为真。那么对于所有变量x3…x的的2”设置Q为真。如果飞+：为假， 那么Q1对于所有的x1X…x的设置为真，除了丁，设置是的Q为真。因此，合起米我们 有： T+1=2+2-Tn=2n+1-Tn 侧使用自销法米证期T。=(2+十（一1)P）,对于n≥，多可以餐设 老对前没有证明的部分的容案。 解：通过归纳法来证明。令)是命题： Tn=(2n+1+(-1)) 基例：存在一个单鞋的设置使得Q()=为真，且T,=(2+《-1)3=1。因此， Ph0为真. 归纳步：对于n多0，我们假设川)和按组如下推理： PDF文件使用“pdfFactory Pro”试用版本创建fineprint.cn
问题 1 [10 分] 考虑以下谓词序列： 令 Tn 对于 Qn(x1,x2,…,xn)为真的变量 x1,x2,…,xn是不同真/假设置的数字。例如，T2 = 3，因 为 Q2(x1,x2)对于变量 x1和 x2的三种不同设置。 (a) 根据 Tn 表示 Tn＋1，假设 n ≥ 1. 解： 我们有： 如果 xn＋1＝1 为真，那么 对于所有变量 x1,x2,…,xn的的 2 n设置 Qn+1为真。如果 xn＋1为假， 那么 Qn+1对于所有的 x1,x2,…,xn的设置为真，除了 Tn设置是的 Qn为真。因此，合起来我们 有： (b) 使用归纳法来证明 ，对于 n ≥ 1。您可以假设 您对前没有证明的部分的答案。 解：通过归纳法来证明。令 P(n) 是命题： 。 基例：存在一个单独的设置 x1使得 Q1(x1) = x1为真，且 T1＝ （2 1+1 + (-1)1 )/3 = 1。因此， P(0)为真。 归纳步：对于 n ≥ 0，我们假设 P(n)和按照如下推理： PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
Tn+1 2+1-Tn =2n+1 3 2m+2+(-1)+1 3 第一步使用前面问题部分的结果，第二步使用归钠假设，第三步是化简。这个端涵口 十1)为真。通过归销原理的，对于所有的n≥1，用为真， PF文件使用"pdfFactory Pro”试用版本创建w.fineprint.cn
第一步使用前面问题部分的结果，第二步使用归纳假设 P(n)，第三步是化简。这个蕴涵 P(n ＋1)为真。通过归纳原理的，对于所有的 n ≥ 1 ，P(n)为真。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
问题210分]在我的厨房没有钟。然而， ■在我关闭求之后水龙头后每54秒满水一次。 ■在我加电后，土司机每隔87秒弹出一片面包 我向要使用恰好141秒来圆蛋。我的计划是同时给土可机如电和关周水龙头。我将开始胶蛋 当水龙头在D次滴水的时候，当土词机弹出第P次的时候停止藏蛋。D和P让这个计划工 作的值是什么？ D 提示：不允许使用计算器 解：粉碎机给出5·87-8·54=3。乘以47给出： 235.87-376.54=141 → 235.87=141+376.54 因此，我将开始在D=36滴水的后开始航蛋，在141秒后停止，在弹出P=87处。 P诉文件使用”pdfFactory Pro”试用版本创建，fineprint,cn
问题 2 [10 分] 在我的厨房没有钟。然而， n 在我关闭水之后水龙头后每 54 秒滴水一次。 n 在我加电后，土司机每隔 87 秒弹出一片面包。 我向要使用恰好 141 秒来煎蛋。我的计划是同时给土司机加电和关闭水龙头。我将开始煎蛋 当水龙头在 D 次滴水的时候，当土司机弹出第 P 次的时候停止煎蛋。D 和 P 让这个计划工 作的值是什么？ 提示：不允许使用计算器 解：粉碎机给出 5 ·87 – 8 ·54 = 3。乘以 47 给出： 因此，我将开始在 D ＝ 376 滴水的后开始煎蛋，在 141 秒后停止，在弹出 P=87 处。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
间题30分]在下面仅挨看腾述的真或假上画圈。假设图是没有自阁和多重边的无白 图。 1.对于所有的n≥3，有n个顶点的完全图有欧拉回路。 假 2。如果一个图包括奇数长度的圈，那么它是二部图。 公 3.每个非二部图包含一个周长为3的圈为子图， 假 4。每个有哈密顿圈的图也有一个欧拉回路。 假 5.存在一个有20个项点，10条边，和5个联通组件的图. 假 6。每个联通的图有一个树为子图。 真。 .在每个联通的平面图上的平面嵌入，顶点数加上面数大于边数。真 9.。如果每个女孩喜欢至少2个男孩，。那么每个女孩能匹配地喜政的男孩。假 10,存在一个有顶点度是0,1,2,3,4,5的6度图。 假 PDF文件使用“pdfFactory Pro”试用版本创建，fineprint,cn
问题 3 [10 分] 在下面仅挨着陈述的 真 或 假上画圈。假设图是没有自圈和多重边的无向 图。 1．对于所有的 n ≥ 3，有 n 个顶点的完全图有欧拉回路。 假 2．如果一个图包括奇数长度的圈，那么它是二部图。 真 3．每个非二部图包含一个周长为 3 的圈为子图。 假 4．每个有哈密顿圈的图也有一个欧拉回路。 假 5．存在一个有 20 个顶点，10 条边，和 5 个联通组件的图。 假 6．每个联通的图有一个树为子图。 真。 7．在每个联通的平面图上的平面嵌入，顶点数加上面数大于边数。真 9．如果每个女孩喜欢至少 2 个男孩，那么每个女孩能匹配她喜欢的男孩。假 10．存在一个有顶点度是 0，1，2，3，4，5 的 6 度图。 假 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
问题4[10分1在量界杯的是后一轮，16个队伍进行海法赛。 ·球只命名为ABC:P, ·停标赛包活一个轮的序列： ■在每轮，球飘分队比赛， ■ 失败的球队被淘汰，获胜者进入下一轮。 ■锦标赛结来的时候仅有一只球队留下， 例如，三只可能的淘法赛如下撕述： P 两个锦标赛是一样的，如果进行同样的比赛，并被同样的球队获鞋。例如，上面暴示的第一 个和第二个锦标赛是一样的。但是第三个不同。不同的锦标赛有多少？ 解：假设我们面停标赛，以便使得在每场比赛中获胜的缘队在失败的球队上面列出。票么， 在左边的球飘的顺序完全决定所有的比赛和获胜者。因此，有16！单淘汰赛。 另一种方法是使用在这门课早期的方法：堆放2n个人的方法数是(2m2。在单测法 锦标赛中，我们必须堆战6只球队，判定奈获胜8场比赛，然后堆积8个获胜的球队，判 定谁获胜4场比赛，等等。这个雀敲完成的方法的个数是： 161 8!28 28 8! 42·21 4 2122·22. 21 ·2=16 1121 最后的可用的方法是使用一般乘法法则。冠军能够以16种方法种达择，其他参加决赛 的球队，半决赛的比赛冠军的球决有14种方式，其他半决赛有13种方式。等等。急的来说， 这又给出16！锦标赛。 F文件使用"pdfFactory Pro”试用版本创建，fineprint,cn
问题 4 [10 分] 在世界杯的最后一轮，16 个队伍进行淘汰赛。 l 球队命名为 A,B,C,…,P。 l 锦标赛包括一个轮的序列。 n 在每轮，球队分队比赛。 n 失败的球队被淘汰，获胜者进入下一轮。 n 锦标赛结束的时候仅有一只球队留下。 例如，三只可能的淘汰赛如下描述： 两个锦标赛是一样的，如果进行同样的比赛，并被同样的球队获胜。例如，上面显示的第一 个和第二个锦标赛是一样的，但是第三个不同。不同的锦标赛有多少？ 解：假设我们画锦标赛，以便使得在每场比赛中获胜的球队在失败的球队上面列出。那么， 在左边的球队的顺序完全决定所有的比赛和获胜者。因此，有 16！单淘汰赛。 另一种方法是使用在这门课早期的方法：堆放 2n 个人的方法数是(2n)!/n!2n。在单淘汰 锦标赛中，我们必须堆放 16 只球队，判定谁获胜 8 场比赛，然后堆积 8 个获胜的球队，判 定谁获胜 4 场比赛，等等。这个能被完成的方法的个数是： 最后的可用的方法是使用一般乘法法则。冠军能够以 16 种方法种选择，其他参加决赛 的球队，半决赛的比赛冠军的球决有 14 种方式，其他半决赛有 13 种方式，等等。总的来说， 这又给出 16！锦标赛。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
问题5「10分]有3个不同年龄的孩子。至少有两个是男孩的概率是多少，给出至少两个最 年轻的孩子中的一个是男孩的概率是多少？ 假设每个孩子是男孩或女孩的概率是一样的，且他们的性测是相互独立的。只有正确的 答案是不够的。然面，为了由清晰面获得部分分数，您必须包括一个清楚标签的树图。 解：令M是由至少两个男孩的事件，令￥是至少两个最年轻的孩子是男孩的事作。 在树图中，所有的边的概率是12。 B 1/2 B 1/2 B B 1/2 1/2 B 1/2 B G 1/2 B 1/2 G 1/2 youngest oldest M Y Prob Pr(MnY) Pr(MY)= Pr(Y) 1/2 3/4 =2/3 P诉文件使用"pdfFactory Pro”试用版本创建，fineprint,cn
问题 5 [10 分] 有 3 个不同年龄的孩子。至少有两个是男孩的概率是多少，给出至少两个最 年轻的孩子中的一个是男孩的概率是多少？ 假设每个孩子是男孩或女孩的概率是一样的，且他们的性别是相互独立的。只有正确的 答案是不够的。然而，为了由清晰而获得部分分数，您必须包括一个清楚标签的树图。 解：令 M 是由至少两个男孩的事件，令 Y 是至少两个最年轻的孩子是男孩的事件。 在树图中，所有的边的概率是 1/2。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
间题6[15分]在天1的早晨，我在我的桌子上放置一个灰色的文件。这样创建一个高度是 1的栈： 在每个后续的早晨，我在随机均一选并的一个位置处往栈中插入一个白色的文档。例如，在 天5晚上的时候，梭可能开起来像这样的： 然后，在后续的早上，我将在以上折示的6个位置中的一个等概率地插入一个白色的文档。 令随机变量B是在天的时候，在灰色文档下放的白色文档的数。 a表示PmB=O)，根据PB,=0) Pr(Bn+1=0)= 解： Pr(B1-0)-Pr(B.=0) n+1 b)根据B=r1)表达B十1)。 PDF文件使用"pdfFactory Pro”试用版本创建匹fineprint.cn
问题 6 [15 分] 在天 1 的早晨，我在我的桌子上放置一个灰色的文件。这样创建一个高度是 1 的栈： 在每个后续的早晨，我在随机均一选择的一个位置处往栈中插入一个白色的文档。例如，在 天 5 晚上的时候，栈可能开起来像这样的： 然后，在后续的早上，我将在以上指示的 6 个位置中的一个等概率地插入一个白色的文档。 令随机变量 Bn 是在天 n 的时候，在灰色文档下放的白色文档的数。 (a) 表示 Pr(Bn+1 = 0) ，根据 Pr(Bn = 0). 解： (b) 根据 Pr(Bn = n-1) 表达 Pr( Bn＋1) 。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
Pr(Bn+1=n)= 解： Pr(Bn+1 =n)= Pr(Bn=n-1) n+1 (c)根据B.-k)和mB,-kI)假设0<k<n表达PB1-k Pr(D。-1-)- 解： Pm=刻=Pn=+na=- (d使用归销证明，在0,1,2，，广1上的均匀分布B。能可以假设您的前面的问题 答案部分，不用的证。 解：我们使用归销法。令P()是在集合0,12，，1上均匀分布B的命愿。 基例：随机变量B:总是相等的到0，因此它在O)上均匀分布。 归销步，假设，随机变量B在集合0,1,2，，一1均匀分布并且考虑随机变量B+1:有 三种情况： PriDa4:-0)--"Pr(D.-0) n+1 =为1 n I In 9 n11 P1(B1--,PBn-n-1) 4+1 为1 n十1n n+I P(B--月-np(&4-)+天，Pm(B+4-k-1 料十1 A11 -程kI,左1 4-1n+1州 9 1 一4+1 PF文件使用"pdfFactory Pro”试用版本创建w,fineprint,cn
解： (c) 根据 Pr(Bn = k)和 Pr(Bn= k-1)假设 0 < k < n 表达 Pr(Bn+1 = k)。 解： (d) 使用归纳证明，在 {0,1,2，…， n− 1}上的均匀分布 Bn。 您可以假设您的前面的问题 答案部分，不用验证。 解：我们使用归纳法。 令 P (n)是在集合{0,1,2，…， n− 1}上均匀分布 Bn的命题。 基例： 随机变量 B1总是相等的到 0，因此它在{0}上均匀分布。 归纳步： 假设，随机变量 Bn在集合{0,1,2，…， n− 1}均匀分布并且考虑随机变量 Bn+1。 有 三种情况： PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
在每种情况种，第一个等式来自在先的问题部分。我们使用在打星号行上的归纳假设。剩 余的步是化简。这个说明，B:是均匀分布，并且斯言由归纳法得到。 P诉文件使用"pdfFactory Pro”试用版本创建.finsprint,cn
在每种情况种，第一个等式来自在先的问题部分。 我们使用在打星号行上的归纳假设。 剩 余的步是化简。这个说明， Bn+1是均匀分布，并且断言由归纳法得到。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn