2020最新中科大组合数学引论课后答案整理全.pdf-资料库

4105a546-fa82-4ea4-8061-f94aaeccd306.pdf-第1页.png

第1页 / 共29页

4105a546-fa82-4ea4-8061-f94aaeccd306.pdf-第2页.png

第2页 / 共29页

4105a546-fa82-4ea4-8061-f94aaeccd306.pdf-第3页.png

第3页 / 共29页

4105a546-fa82-4ea4-8061-f94aaeccd306.pdf-第4页.png

第4页 / 共29页

4105a546-fa82-4ea4-8061-f94aaeccd306.pdf-第5页.png

第5页 / 共29页

4105a546-fa82-4ea4-8061-f94aaeccd306.pdf-第6页.png

第6页 / 共29页

4105a546-fa82-4ea4-8061-f94aaeccd306.pdf-第7页.png

第7页 / 共29页

4105a546-fa82-4ea4-8061-f94aaeccd306.pdf-第8页.png

第8页 / 共29页

3. 任意一个整数除以 n 的余数最多只可能有 n 种情况：0，1，2…n - 1。所以 n + 1 个整数除以 n，必有至少两个数的余数相同，那么它们的差是 n 的倍数。 4. (1)令 b1，b2，…，b77 分别为这 11 周期间他每天下棋的次数，并作部分和 =, =+, ⋯, =++⋯+. 依题意， ≥1(1≤≤77)，且+ +⋯+ ≤12(1≤≤71)，故有1≤ ≤≤⋯≤≤12×11=132。当1≤≤21时，考虑数列,,⋯,,+,+,⋯,+，它们都在 1 与132+(133≤132+≤153)之间，共有 154 项。由鸽巢原理，其中必有两项相等。由于,,⋯,这 77 项互不相等，所以+,+,⋯,+这 77 项也互不相等，所以一定存在1≤<≤77，使得=+。所以=− 。即存在连续的一些天，棋手恰好下了(=1,2,⋯21)盘棋。 (2)考虑数列,,⋯,,+22,+22,⋯,+22， (i)如果这 154 项中有两项相等，则存在1≤<≤77，使得=+22， (ii)如果这 154 项中任意两项都不相等，则数列,,⋯,,+22,+ 22,⋯,+22是 1 到 154 的一个全排列。然而这种全排列其实是不存在的，数列中最小的数为，所以=1，+22=23；除去，最小的数为，所以 =2，+22=24等等，具体结果如下： =1,=2,⋯,=22, +22=23,+22=24,⋯,+22=44, =45,=46,⋯,=66, +22=67,+22=68,⋯,+22=88, =89,=90,⋯,=110, +22=111,+22=112,⋯,+22=132, 此时最小，=133，而+22=155，所以这种全排列是不存在的。 6. 任意一个整数可以表示为2⋅，为非负整数,为奇数，按照将 1 到综上所述，这 154 项中存在连续的一些天，棋手恰好下了 22 盘棋。则从第 i 天到第 j 天棋手恰好下了 22 盘棋。 200 这 200 个数划分成 100 个集合： ={2⋅1,2⋅1,…,2⋅1}; ={2⋅3,2⋅3,…,2⋅3}; …

={2⋅,2⋅,…}; … ={2⋅199}. =2⋅1 =2⋅3 … =2⋅199 每个集合内的任意两个元素，一个都可以被另一个整除，因此取 100 个数时要分别从这 100 个集合里各取一个，设取的 100 个数为：因为存在< 16，则 =2⋅< 16。因为=2⋅3，则 =3⋅2。因为存在与互不整除，所以<，所以≤−1。所以， = 2⋅3≤2⋅3=3/2，因为<16，所以<24,< 36,⋯,<81，又因为=2⋅81≥81，矛盾！所以，原命题得证！ 7. 取出 101 到 200 即可。 10. 根据横坐标对 3 取余将这 9 个整点分成 3 类： ={(,)|=0( 3)}; ={(,)|=1( 3)}; ={(,)|=2( 3)}. ={(,)|=0( 3)}; ={(,)|=1( 3)}; ={(,)|=2( 3)}. (,) (,) (,) (,) (,) (,2) (,) (,) (,) 同理，根据纵坐标对 3 取余也可以将这 9 个整点分成 3 类：所以，可以将这 9 个整点分成 9 类： (1)若存在某一类的元素个数不小于 3，则从该类中选取 3 个点就满足要求； (2)若所有类的元素个数均小于 3，则这 9 个整点至少分成 5 类，这 5 类至少满足以下一个条件： (i)某一行的三类元素个数均非零，此时从这三类中个取一个元素就满足要求； (ii)某一列的三类元素个数均非零，此时从这三类中个取一个元素就满足要求； (iii)某一对角线（包括(,),(,),(,)这种）的三类元素均非零，此时从这三类中个取一个元素就满足要求。假设 9 个整点分成的 5 类上述三个条件均不满足，则每行最多有两类不空且每行至少有一类不空，不妨设第一行和第二行各有两类不空，则第三行无论是哪类不空均满足上述三个条件之一，矛盾。故这与 5 类必满足上述三个条件之一。

个元素是某两个元素之差，则满足题目要求，否则，令 =−,=−,⋯,=−. 综上所述，这 9 个整点中必有 3 个整点满足要求。 11. 有理数的分子跟分母都是整数，并且分母不等于零，十进制数展开式相当于一个整数除以另外一个整数 n，所得余数所有可能值有−1个，也就是说最多除−1次余数就会有重复，当余数重复时，就会产生循环。 15. 1,2,⋯,2中至多有 n 个整数互不相邻，有鸽巢原理知，从这 2n 个整数中任选+1个整数，至少有 2 个整数相邻，则这 2 个整数的最大公因子为 1. 20. 由鸽巢原理知，,,,中至少有一个有=17个整数，不妨设为，并设这 17 个元素<<⋯<，令={,,⋯,}，若 A 中存在一令={,,⋯,}，显然1≤≤67，根据前面的假定，,,⋯,中无一属于，否则与假设 A 中不存在一个元素是某两个元素之差相矛盾，所以 B 中元素属于,,。由鸽巢原理知，,,中至少有一个至少包含,,⋯,中的=6个整数，不妨设为，且<<⋯<,1≤<<⋯<≤16。令= ,,⋯,，⊆。根据假定，中没有一个元素是某两个元素之差。令显然∉,∉,=1,2,3,4,5。令={,,⋯,}，所以 C 中元素属于,。由鸽巢原理知，,中至少有一个至少包含,,⋯,中的=3个整数，不妨设为，且<<,1≤<<≤5。令=,,，⊆。根据假定，中没有一个元素是某两个元素之差。令 =−,=−. 显然∉,∉,∉,=1,2。令={,}，所以 D 中元素属于。而 1≤<<67，由假定有−∉,,,，这和将 1 到 67 之间的整数 =−,=−,⋯,=−. 分成四部分的前提矛盾，故原命题成立。 22. 把每个三角形的最短边染成红色，剩下的所有边染成白色，则由 Ramsey 定理可知，必出现同色三角形。又每个三角形都有最短边，即每个三角形都有红色边。于是上述同色三角形是红色的，则它的最长边也是红色的，所以原命题得证。

2. (1)千位数字为 5，安排方法。然后将剩下的那个人插入到十一个人之间，其中有 2 个位置不能安 1. 求 50!的尾部有多少个零，即求 50!中有 2 × 5 的因子个数。由于 2 的因子个数比 5 多，所以问题转换为求 5 的因子个数。其中 5，10，15，20，30，35， 40，45 各含有 1 个 5 的因子，共 8 个；25，50 各含有 2 个 5 的因子，共 4 个。所以共有 12 个 5 的因子，即 50!的尾部有 12 个零。（注：50! = 30414093201713378043612608166064768844377641568960512000000000000） (i)百位数字为 4，满足要求的整数有6×5=30个； (ii)百位数字大于 4，满足要求的整数有3×6×5=90个； (2)千位数字大于 5，满足要求的整数有3×7×6×5=630个；综上所述，满足要求的整数有30+90+630=750个。 3. 将不相邻的两人其中一人与其他十个人先进行圆排列，有11!11⁄ =10!种排，所以有 9 个位置，共有9×10!种安排方法。 4. (1)有(4,4)=24种信号。 (2)使用一盏灯，有 4 种信号；使用两盏灯，有(4,2)=12种信号；使用三盏灯，有(4,4)=24种信号；使用四盏灯，有(4,4)=24种信号；共有4+12+24+ 24=64种信号。 (3)使用一、二、三、四盏灯，各有、、、种信号，共有 15 5. (1) . (2) 1−/. (3) /. 7. 选取 8 行，每行放一个，有种取法；每行取一列放棋子，有 P(8,8)种 !!⋅!种放法。综上所述，有⋅(8,8)⋅ !!⋅!种放法。放在 12×12 的棋盘上，有⋅(12,8)⋅ !!⋅!种放法。 8. (或). 10. 记=−，则原问题转化为求方程++⋯+=4的非负整数解取法；把 5 个红和 3 个蓝棋子放在这 8 个位置上，有种信号。

(2)集合 B：n 个 0，n 个 1 组成的序列，且在某个时刻，0 的数量大于 1 的数的个数，共 =330个。 13. 将向右走记为 1，向上走记为 0，则(0, 0)到(n, n)的非降路径数为一个 01 序列，将满足条件的序列分为两类： (1)任何时刻，1 的数量 ≥ 0 的数量（一直在对角线的下方走）； (2)任何时刻，0 的数量 ≥ 1 的数量（一直在对角线的上方走）。两类序列的数量相等，下面仅求第一类序列的数量。定义三个集合：下面证明集合 B 和集合 C 大小相等。任取 B 中的一个元素，将第一次出现 0 的数量大于 1 的数量的位置及以前的素都可以唯一的映射到 C 中。反过来，C 中元素必然存在某一时刻 0 的数量大于 1 的数量，将第一次出现 0 的数量大于 1 的数量的位置之后的 0 和 1 进行反转，得到的序列必然属于 B，所以 C 中元素都可以唯一映射到 B 中。所以集合 B 和集合 C 的大小相等。 (1)集合 A：n 个 0，n 个 1 组成的序列，集合大小为；量，||−||即为第一类序列的数量； (3)集合 C：+1个 0，−1个 1 组成的序列，集合大小为。序列保持不变，后面的序列 0 和 1 进行反转。例如 B 中的元素=1010001⋯011，第五位及以前的序列保持不变，后面的序列 0 和 1 反转，变为序列= 1010010⋯100。可以证明变换后的序列中有+1个 0，−1个 1，所以 B 中元所以第一类路径的数量为||−||=2−2−1=2/ (+1)，总的着对角线对折，集合 C 表示从(0,0)到( − 1, + 1)的非降路径数。组里的最大数，即只要取出(=+,≤)个数，按从大到小的顺序排列， −1种，所以总的方案数为 =−=2−2+1 (−1) . 物理含义：第一次出现 0 的数量 > 1 的数量，表示从对角线下方走的时候第一次穿过对角线，将后面的 0 和 1 反转，表示将第一次穿过对角线后面的路径沿 2⋅(||−||)=2⋅2/(+1). 路径数量为 14. 设第一组数有 a 个，第二组数有 b 个，要求第一组里的最小数大于第二把前 a 个作为第一组，剩下 b 个作为第二组。对于给定的 m，第一组的取法有

算了一次，故把所有的对角线分成每组对角线交点关联的段数为 4，每个顶点关联的段数为 7，这样每段重复计 16. 每四个顶点构成一个凸四边形，一个凸四边形的一组对角线有一个交点， (210×4+10×7)=455段。且任意 3 条对角线不共点，所以该凸 10 边形的对角线交于=210个点。 20. (1)因为最大元素是，所以其他元素是从比小的−1个元素中选取，这 −1个元素每个都有被选取和不被选取两种情况，故最大元素恰好是的子集数为2。 (2)等式左边表示最大元素1,2,⋯,+1的子集数之和，等式右边表示集合 1,2,⋯,+1的非空子集数，显然两边相等。 23. 确定 5 封信的传送顺序有5!=120种，将 15 个空格插入到 4 个间隔中， +++=15 (≥3，=1,2,3,4) =20，综上所述，共有 2400 种方法。的非负整数解的个数间不能被 3 整除的数有 67 个，故所求有序对的数量为(67,2)。 1 (+1)(+2) = 1 ! !(−)! (+1)(+2) = (+2)! 1 (+2)!(−)! (+1)(+2) = (+1)(+2)+2 1 +2 (+1)(+2)2−+20 −+21 = 2−−3 1 = (+1)(+2) 25. 因为 x 与 y 的乘积不能被 3 整除，则 x 和 y 均不能被 3 整除。1 到 100 之即方程 28. (2)

3. (2)等式左边 2. 的系数是⋅35⋅(−2)13=−⋅35⋅213. 的系数是⋅38⋅(−2)10=⋅38⋅210. = 1+1(+1)0++12 1++13 2+⋯++1 +1 = 1+1+11 ++12 ++13 +⋯++1 +1 = (2−1). 4. 等式右边相当于从(0,0)到(,−++1)点的非降路径数，可以将这些路径分为如下+1类：第(=1,2,⋯,)类路径是从(0,0)点到(−,−) 点，然后到(−,−+1) 点，最后到(,−++1) 点，路径数为。由加法原则，得等式成立。 8. ++ =6(−1)(−2)+2(−1)+ =6+−2 +3−2+ ∴6=1， −2 =0，3−2+=0. ∴=6，=6，=1. 1+2+⋯+ =613+⋯+3+612+⋯+2+11+⋯+1 =6+14 +6+13 ++12 =6+24 ++12 =(+1) 4 9. 表示+元集合 A 的 n 组合数。将集合 A 分成两个集合 A1 和 A2，使得||=,||=。则 A 的 n 元子集可以分成如下+1类：从 A1 中选取(=0,1,⋯,)个元素，从 A2 选取−个元素合并到一起构成 A 的第 k

(1)知，该等式成立。 (2)等式左边可以理解为长度为 n 字符串中，0 出现偶数次的字符串总和，由类 n 元子集，而第 k 类子集的个数为。由加法原则，原等式得证。 10. (1)设 0 出现偶数次的字符串有()个，出现奇数次的字符串有()个，则(1)=2，对()，可以分成以下两种情况： (i)最后一位为 0，则()=(−1)； (ii)最后一位为 1 或 2，则()=(−1)；所以()=(−1)+2(−1)，而()=3−()，则 ()=3−(−1)+2(−1)=3+(−1). 所以 ()=3+3+⋯+3+(1)=32(3−1)+2=3+12 . 11. 等式右边=2+1表示 2n 元集合 A 的+1组合数。将集合 A 分成两个集合 A1 和 A2，使得||=,||=。则 A 的+1元子集可以分成如下 n 类：从 A1 中选取(=1,2,⋯,)个元素，从 A2 选取+1−个元素合并到一起构成 A 的第 k 类+1元子集，而第 k 类子集的个数为 = 。由 15. − =−1 −1+−1 −−3 =−1 −1+−2 −1+−2 −−3 =−1 −1+−2 −1+−3 −1+−3 −−3 −1+−3 =−1 −1+−2 −1 = 16. −− ,, ,, =++ = + − ,, 加法原则，原等式得证。

资料库

2020最新中科大组合数学引论课后答案整理全.pdf

相关推荐

课程资源

热门标签

最新资料