NTU-Exam 板


LINE

课程名称︰离散数学 课程性质︰资工系大一选修 课程教师︰吕育道 开课学院: 开课系所︰ 考试日期(年月日)︰ 考试时限(分钟):180 mins 试题 : 1. Consider a binary string x_1x_2...x_n. The (Hamming) weight of x_1x_2...x_n is defined as \sum_i x_i. Two strings have Hamming distance d if they differ i n d positions. Among the strings, how many have an even weight? Ans: \sum_{i = 0}^{\floor(n/2)} C(n, 2 * i) This is because 1 occurs in 2i positions. Then apply a corollary of binomial theorem to add up to 2^{n - 1} 2. How many non-negative integer solutions can satisfy the inequality x_1 + x_2 + x_3 + x_4 + x_5 <= 20, where x_1 >= 1, x_2 >= 2, x_3 >= 3, x_4 >= 4, x_5 >= 5 ? Ans: 252 3. Let f : A → B be invertible. Then there is a unique function g : B → A such that g \circ f = 1_A and f \circ g = 1 \circ B. Prove that f is invertible if and only if it is bijective. Ans: See p. 329 of the lecture notes. 4. Suppose that candidate A receives m votes and candidate B receives n votes with m > n. Assume each vote counting sequence is equally likely. Prove that the probability that A will be strictly ahead of B throughout the vote count is (m - n) / (m + n). (Hint: The reflection principle says for k, a, b > 0, the number of paths on the lattice from (0, k) to (a, b) which touch the origin is equal to the number of paths from (0, -k) to (a, b).) Ans: Consider the number of ways candidate A is always in the lead. A must get the first vote. So A has m 1 additional votes to be counted and B has n. Thin k of a vote for A as +1 and a vote for B as -1. We need to count the number of vote counting sequences and subtract from it the number of vote counting sequ ences where A’s vote count is even with B’s at least once. The former is cle arly C(m + n - 1, m - 1). The latter equals the number of lattice paths from ( 1, 1) to (m + n, m - n) which touch the x-axis. By the reflection principle, i t equals the number of lattice paths from (1,-1) to (m + n,m - n). This is equ ivalent to A getting m votes and B getting n - 1 votes. So the desired count i s C(m + n - 1, m - 1) - C(m + n - 1, m) = (m - n)/(m + n) * C(m + n, n). As th e total number of voting sequences is C(m + n, n), the probability that candid ate A is always in the lead is (m - n) / (m + n). 5. Use induction to prove that F_{n+1}F_{n-1} - (F_n)^2 = (-1)^n where F_n is a Fibonacci number and n∈Z+ with F_0 = 0 and F_1 = 1. Ans: 略 6. Let A = {1, 2, 3} and B = {1, 2, 3, 4, 5}. Determine the number of relation s from A to B and the number of functions from A to B. Ans: There are 2^15 relations from A to B and 5^3 of these are functions from A to B. 7. Let (A, R) be a poset and x ∈ A be the greatest element. Argue that x must be the only maximal element of A. Ans: By contradiction, assume that x′ is another maximal element of A. T x) ∈/ R and (x, x′) ∈/ R violet antisymmetricity. 8. R is antisymmetric if (x, y) ∈ R Λ (y, x) ∈ R \rightarrow x = y for all x,y ∈ A. Let A have n members. How many relations are there that are both antisymmetric and symmetric? Ans: 1 9. Let A = {1, 2, 3, 4, 5}. Determine the number of bijective functions f : A → A which satisfy f(1) ≠ 1, f(2) ≠ 2 and f(3) ≠ 3. Ans: 5! - C(3, 1) ? 4! + C(3, 2) ? 3! - C(3, 3) ? 2! = 64 10. Let S = {1,2,3,...,200} and T be a subset of S with size 101. Prove that there are two integers in T such that one is a multiple of the other. Ans: For each x \in S, we may write x = 2^k*y with some integer k and odd integer y. There are at most 100 such y in T. Since 101 integers are selected from S, by the pigeonhole principle there are two distinct integers a = 2my and b = 2ny for some y ∈ T. If m < n, then a|b; otherwise, b|a. --



※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.37.182.241 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/NTU-Exam/M.1655308812.A.33D.html ※ 编辑: sN0w374625cS (114.37.182.241 台湾), 06/16/2022 00:19:06
1F:推 rod24574575 : 收录资讯系! 06/16 00:19
※ 编辑: sN0w374625cS (114.37.182.241 台湾), 06/16/2022 00:54:45







like.gif 您可能会有兴趣的文章
icon.png[问题/行为] 猫晚上进房间会不会有憋尿问题
icon.pngRe: [闲聊] 选了错误的女孩成为魔法少女 XDDDDDDDDDD
icon.png[正妹] 瑞典 一张
icon.png[心得] EMS高领长版毛衣.墨小楼MC1002
icon.png[分享] 丹龙隔热纸GE55+33+22
icon.png[问题] 清洗洗衣机
icon.png[寻物] 窗台下的空间
icon.png[闲聊] 双极の女神1 木魔爵
icon.png[售车] 新竹 1997 march 1297cc 白色 四门
icon.png[讨论] 能从照片感受到摄影者心情吗
icon.png[狂贺] 贺贺贺贺 贺!岛村卯月!总选举NO.1
icon.png[难过] 羡慕白皮肤的女生
icon.png阅读文章
icon.png[黑特]
icon.png[问题] SBK S1安装於安全帽位置
icon.png[分享] 旧woo100绝版开箱!!
icon.pngRe: [无言] 关於小包卫生纸
icon.png[开箱] E5-2683V3 RX480Strix 快睿C1 简单测试
icon.png[心得] 苍の海贼龙 地狱 执行者16PT
icon.png[售车] 1999年Virage iO 1.8EXi
icon.png[心得] 挑战33 LV10 狮子座pt solo
icon.png[闲聊] 手把手教你不被桶之新手主购教学
icon.png[分享] Civic Type R 量产版官方照无预警流出
icon.png[售车] Golf 4 2.0 银色 自排
icon.png[出售] Graco提篮汽座(有底座)2000元诚可议
icon.png[问题] 请问补牙材质掉了还能再补吗?(台中半年内
icon.png[问题] 44th 单曲 生写竟然都给重复的啊啊!
icon.png[心得] 华南红卡/icash 核卡
icon.png[问题] 拔牙矫正这样正常吗
icon.png[赠送] 老莫高业 初业 102年版
icon.png[情报] 三大行动支付 本季掀战火
icon.png[宝宝] 博客来Amos水蜡笔5/1特价五折
icon.pngRe: [心得] 新鲜人一些面试分享
icon.png[心得] 苍の海贼龙 地狱 麒麟25PT
icon.pngRe: [闲聊] (君の名は。雷慎入) 君名二创漫画翻译
icon.pngRe: [闲聊] OGN中场影片:失踪人口局 (英文字幕)
icon.png[问题] 台湾大哥大4G讯号差
icon.png[出售] [全国]全新千寻侘草LED灯, 水草

请输入看板名称,例如:Tech_Job站内搜寻

TOP