CS70Disc06B
CS70Disc 06B
1 Inclusion and Exclusion
问题描述
求解严格小于100的正整数中，与100互质的正整数总数。
解题思路
计算与100互质的正整数数量，可以通过先计算与100不互质的正整数数量，然后用总数减去这个数量来得到结果。
步骤详解
- 总数的计算：
- 严格小于100的正整数总数为99（即从1到99）。
- 与100不互质的正整数定义：
- 一个正整数如果不与100互质，意味着它是2或5的倍数。
- 计算各类倍数的数量：
- 计算2的倍数： $ = = 49 $
- 计算5的倍数： $ = = 19 $
- 计算同时是2和5的倍数（即10的倍数）： $ = = 9 $
- 应用包含-排除原理：
- 根据包含-排除原理，计算与100不互质的正整数数量： $ = () + () - () $ $ = 49 + 19 - 9 = 59 $
- 计算与100互质的正整数数量：
- 与100互质的正整数数量为： $ = 99 - 59 = 40 $
结论
因此，严格小于100的正整数中，与100互质的正整数总数为 40。
- 互质的定义：
- 两个正整数如果它们的最大公约数为1，则称这两个数互质。即，若 \(a\) 和 \(b\) 互质，$ (a, b) = 1$。
- 倍数的概念：
- 若正整数 \(m\) 能被正整数 \(n\) 整除，则称 \(m\) 为 \(n\) 的倍数。即 \(m = k \cdot n\)（其中 \(k\) 为正整数）。
- 总数的计算：
- 在给定范围内（如从1到99），我们可以通过简单的计数来确定正整数的总数。
- 包含-排除原理：
- 这是组合数学中的一个重要原则，用于计算集合的并集大小。具体来说，如果有两个集合 \(A\) 和 \(B\)，则其并集的大小为： $ |A B| = |A| + |B| - |A B| $
- 在这个问题中，用于计算不与100互质的正整数数量。
- 取整函数：
- 在计算倍数时，使用取整函数（向下取整），即 \(\left\lfloor x \right\rfloor\)，表示小于或等于 \(x\) 的最大整数。例如，\(\left\lfloor \frac{99}{2} \right\rfloor\) 计算得到49，表示小于100的2的倍数个数。
- 正整数的性质：
- 正整数是指大于零的整数。在该问题中，我们仅考虑正整数。
2 CS70: The Musical
知识点
- 组合选择：
- 组合是指从一组元素中选择子集的方式，常用符号 \(\binom{n}{k}\) 表示从 \(n\) 个元素中选择 \(k\) 个元素的不同组合数量。
- 排除法：
- 在解决组合问题时，可以通过排除不必要的情况来简化问题的复杂性。
- 分类计数：
- 当面临多种可能性时，将所有可能性进行分类，分别计算每个分类下的情况，然后将结果相加，以得到总数。
问题及解答
(a) 选择导演
问题：有 \(2n\) 名导演，选择2名导演。证明以下等式： $ = 2 + n $
答案与解释：
左侧 (LHS)：选择2名导演的总方式数为 \(\binom{2n}{2}\)。
右侧 (RHS)：将 \(2n\) 名导演分为两组（经验丰富和缺乏经验的导演），考虑以下三种情况：
- 两名导演均来自经验丰富的组：\(\binom{n}{2}\)
- 两名导演均来自缺乏经验的组：\(\binom{n}{2}\)
- 一名来自每组：\(\binom{n}{1} \cdot \binom{n}{1} = n^2\)
将这三种情况相加得到： $ = + + n^2 = 2 + n^2 $
(b) 选择剧组成员
问题：从 \(n\) 名成员中选择 \(k\) 名。证明以下等式（称为帕斯卡尔的身份）： $ = + $
答案与解释：
左侧 (LHS)：选择 \(k\) 名剧组成员的方式为 \(\binom{n}{k}\)。
右侧 (RHS)：考虑第一位成员是否被选择：
- 如果选择了这位成员，则需要从剩下的 \(n-1\) 名中选择 \(k-1\) 名：\(\binom{n-1}{k-1}\)。
- 如果没有选择这位成员，则从剩下的 \(n-1\) 名中选择全部 \(k\) 名：\(\binom{n-1}{k}\)。
合并这两种情况得： $ = + $
(c) 选择演员
问题：有 \(n\) 名演员，选择若干人并指定一名主角。证明以下等式： $ _{k=1}^{n} k = n ^{n-1} $
答案与解释：
左侧 (LHS)：选择 \(k\) 名演员并从中选择1名主角，表达式为 \(k \cdot \binom{n}{k}\)，因此对所有 \(k\) 的求和得出总数。
右侧 (RHS)：选择1名主角（\(n\)种选择），然后从剩余的 \(n-1\) 名演员中选择任意组合（包含可能不选择任何演员），因此有 \(2^{n-1}\) 种选择方式。结合得到： $ n ^{n-1} $
(d) 选择多名主角
问题：从 \(n\) 名演员中选择 \(k \geq j\) 名，并选择 \(j\) 名主角。证明以下等式： $ _{k=j}^{n} = 2^{n-j} $
答案与解释：
左侧 (LHS)：选择 \(k\) 名演员并从中选择 \(j\) 名主角。对所有有效的 \(k\) 进行求和。
右侧 (RHS)：选择 \(j\) 名主角（\(\binom{n}{j}\)种选择），然后从剩余的 \(n-j\) 名演员中选择任意组合（包含可能不选择任何演员），因此有 \(2^{n-j}\) 种选择方式。结合得到： $ _{k=j}^{n} = 2^{n-j} $
3 Farmer’s Market
知识点
- 球与箱子问题（Balls and Bins）：
- 这个问题通常用于组合计数，特别是分配相同类型的物品到不同类别中。我们可以使用“星与条”（Stars and Bars）的方法来解决。
- 星与条方法（Stars and Bars）：
- 这个方法通过将“星”表示为待分配的物品，将“条”表示为类别的分隔符，来构建组合计数。
问题及解答
(a) 有南瓜和苹果
问题：你想从市场上选择 \(k\) 个物品，市场上有南瓜和苹果。求有多少种选择方式。
答案与解释：
- 选择方式：可以选择 \(0\) 个南瓜和 \(k\) 个苹果，或者 \(1\) 个南瓜和 \(k-1\) 个苹果，等等，一直到 \(k\) 个南瓜和 \(0\) 个苹果。
- 用星与条方法表示：这可以看作是 \(k\) 个球（物品）和 \(2\) 个箱子（南瓜和苹果），我们可以用 \(k+1\) 个星来表示物品，\(1\) 个条来分隔两种类型的物品。
因此，选择的方式总数为： $ = = k+1 $
(b) 有南瓜、苹果、橙子和梨
问题：市场上有南瓜、苹果、橙子和梨。你仍然想从中选择 \(k\) 个物品。求有多少种选择方式。
答案与解释：
- 选择方式：这次有 \(4\) 种水果（南瓜、苹果、橙子、梨），我们可以将 \(k\) 个球放入 \(4\) 个箱子中。
- 用星与条方法表示：这可以看作是 \(k\) 个球和 \(3\) 个条（分隔符）来分隔 \(4\) 种水果。
因此，选择的方式总数为： $ $
(c) 有 \(n\) 种水果，至少选择两种不同类型
问题：市场上有 \(n\) 种水果，你希望选择 \(k\) 个物品，并且至少有两种不同类型的水果。求有多少种选择方式。
答案与解释：
总选择方式：首先，计算从 \(n\) 种水果中选择 \(k\) 个物品的总方式： $ $ 这是没有限制的情况下的选择方式（\(k\) 个球和 \(n\) 个箱子）。
排除单一类型的情况：从中减去只选择一种水果的情况。对于每种水果，选择 \(k\) 个该种水果的方式有 \(n\) 种（每种水果只选择一种）。
因此，最终选择的方式为： $ - n $
4 The Count
知识点
- 星与条（Stars and Bars）：
- 用于解决组合计数问题，特别是在需要将相同的物品分配到不同的类别中时。
- 组合（Combinations）：
- 用于从一组元素中选择特定数量的元素，顺序不重要。
- 分情况计数（Casework）：
- 将复杂问题分解为简单情况分别计数，然后求和。
问题及解答
(a) 非递增的7位电话号码
问题：The Count想选择一个新的7位电话号码，要求数字从左到右是非递增的。求选择多少种电话号码。
答案与解释：
分配问题：这里我们有7个位置来放置数字（0到9），并且有9个分隔符来区分不同数字（即从9到0）。因为数字必须是非递增的，所有的9（如果有的话）必须放在最前面，接着是所有的8，依此类推。
星与条方法：我们可以将7个数字和9个分隔符看作是总共16个对象，其中9个是分隔符。我们要选择9个分隔符的位置，剩下的位置则填充数字。
因此选择的方式总数为： $ $
(b) 严格递减的7位电话号码
问题：现在电话号码必须是严格递减的。求选择多少种电话号码。
答案与解释：
严格递减：对于任何选择的7个数字，只有一种可能的排列方式是严格递减的。因此，我们只需从0到9中选择7个不同的数字。
组合计算：选择7个不同的数字的方式是： $ $
(c) 包含至少五个连续0的10位密码
问题：The Count想创建一个长度为10的密码，只能包含数字0和1，并且需要包含至少五个连续的0。求有多少种可能的密码。
答案与解释：
- 计数方法：由于存在强烈的重复计数的可能性，因此不能简单选择5个连续位置为00000。我们需要进行分情况计数，考虑零的开始位置。
- 情况划分：
- 连续0的开始位置可以在第一到第六位之间（包含第一位和第六位），因此总共6种情况。
- 具体情况：
- 情况1：如果连续0的开始位置在第一位：
- 前五位都是0，剩下的5位可以任意选择（0或1），因此有 \(2^5 = 32\) 种选择。
- 情况2：如果连续0的开始位置在第二位：
- 第一位必须是1，接下来的4位可以任意选择，有 \(2^4 = 16\) 种选择。
- 情况3：如果连续0的开始位置在第三位：
- 前两位中第一位必须是1，第二位可以是0或1，剩下的3位可以任意选择，因此有 \(2^3 = 8\) 种选择。
- 情况4：如果连续0的开始位置在第四位：
- 前三位中第一位必须是1，第二位和第三位可以是0或1，剩下的2位可以任意选择，有 \(2^2 = 4\) 种选择。
- 情况5：如果连续0的开始位置在第五位：
- 前四位中第一位必须是1，其他三位可以是0或1，最后一位可以任意选择，有 \(2^1 = 2\) 种选择。
- 情况6：如果连续0的开始位置在第六位：
- 前五位中第一位必须是1，其他四位可以是0或1，密码的最后一位为0，有 \(2^0 = 1\) 种选择。
- 情况1：如果连续0的开始位置在第一位：
- 汇总：
- 将所有情况的选择方式相加： $ 32 + 5 = 32 + 80 = 112 $
