知识焦点
先建立概念地图
- 数论
- 鸽巢原理
- 奇偶性
- 反证法
- 逆否命题
- 集合运算
- 函数像
- 原像
CS70 · 讨论课 00b
本次讨论课包含两个问题：完全平方数的奇偶性与模8性质，以及鸽巢原理在朋友数量问题中的应用。
知识焦点
建议顺序
先完整作答，再按需展开提示；最后才展开官方参考解答并逐步核对证明与计算。
本地来源
题面与解答均由本地一手资料整理：discussion/dis00b.pdf、solutions/discussion/dis00b-sol.pdf
本地一手资料完整提取 · 讨论课
本节按本地一手资料完整整理，共 4 道大题。本地官方解答已完整收录并默认折叠；建议先独立完成，再逐题核对推导。
discussion/dis00b.pdf、solutions/discussion/dis00b-sol.pdfNote 2
(a) 证明：若 \(n^2\) 是奇数，则 \(n\) 也必须是奇数。
(b) 证明：若 \(n^2\) 是奇数，则 \(n^2\) 可以写成 \(8k + 1\) 的形式，其中 \(k\) 为某个整数。
对于 (a)，考虑使用逆否命题：证明"若 \(n\) 为偶数，则 \(n^2\) 为偶数"。
对于 (b)，利用 (a) 的结论将 \(n\) 写成 \(2l+1\) 的形式，展开后注意连续整数乘积的奇偶性。
(a) 我们使用逆否命题来证明。原命题的逆否命题为"若 \(n\) 为偶数，则 \(n^2\) 也为偶数"。由于 \(n\) 是偶数，可设 \(n = 2k\)，其中 \(k\) 为整数。于是 \(n^2 = (2k)^2 = 4k^2 = 2(2k^2)\)，这显然是偶数。由逆否命题可知，若 \(n^2\) 为奇数，则 \(n\) 必为奇数。
(b) 我们使用直接证明。由 (a) 可知，若 \(n^2\) 为奇数，则 \(n\) 也为奇数，即存在整数 \(l\) 使得 \(n = 2l + 1\)。于是 \[ n^2 = 4l^2 + 4l + 1 = 4l(l + 1) + 1. \] 由于 \(l\) 与 \(l+1\) 中必有一个为偶数，因此 \(l(l+1)\) 可写成 \(2k\) 的形式，其中 \(k\) 为整数。代入得 \(n^2 = 8k + 1\)。
解答来源：solutions/discussion/dis00b-sol.pdf · 1 · confidence: high
题面来源：discussion/dis00b.pdf · 1 · confidence: high
Note 2 证明：若聚会上有 \(n \ge 2\) 个人，则其中至少有两个人在聚会上拥有相同数量的朋友。假设友谊总是相互的：即如果 Alice 是 Bob 的朋友，那么 Bob 也是 Alice 的朋友。
（提示：鸽巢原理（Pigeonhole Principle）指出，若将 \(n\) 个物品放入 \(m\) 个容器中，且 \(n > m\)，则至少有一个容器包含多于一个物品。你可以直接使用该原理而无需证明。）
每个人的朋友数取值范围是 \(0\) 到 \(n-1\)。思考极端情况：若存在一个人与所有其他 \(n-1\) 个人都是朋友，那么是否可能同时存在一个没有任何朋友的人？利用这一点进行反证，或考虑实际可用的不同朋友数值的个数是否少于人数。
我们使用反证法证明。假设相反的情况成立，即每个人的朋友数都不同。由于每个人的朋友数取值范围是 \(0\) 到 \(n-1\)，因此对于每个 \(i \in \{0, 1, \ldots, n-1\}\)，恰好有一个人拥有 \(i\) 个朋友。特别地，存在一个人拥有 \(n-1\) 个朋友（即与所有人都是朋友），同时存在另一个拥有 \(0\) 个朋友的人（即与任何人都不是朋友）。这是矛盾的，因为友谊是相互的。
这里我们使用了鸽巢原理：假设每个人的朋友数都不同，会产生 \(n\) 个可能的容器，分别标记为 \(0, 1, \ldots, n-1\)。但容器 \(0\) 和容器 \(n-1\) 不能同时被占用（否则会出现一个人与所有人都是朋友，同时又有人没有朋友的矛盾）。因此我们实际上是将 \(n\) 个人分配到至多 \(n-1\) 个容器中，由鸽巢原理，至少有一个容器包含两个或更多人，即至少有两个人的朋友数相同。
解答来源：solutions/discussion/dis00b-sol.pdf · 1 · confidence: high
题面来源：discussion/dis00b.pdf · 1 · confidence: high
假设有一个鹅卵石的矩形阵列，每块鹅卵石要么是红色，要么是蓝色。假设对于从每一列中各取一块鹅卵石的每一种取法，所取鹅卵石中至少存在一块红色鹅卵石。证明：必然存在一列全为红色鹅卵石。
考虑原命题的逆否命题：如果没有任何一列是全红色的，那么每一列中都能找到什么颜色的鹅卵石？
我们用逆否命题来证明；逆否命题是「如果不存在全红列，那么就存在一种从每一列各取一块鹅卵石的方式，使得所取鹅卵石中没有红色鹅卵石」。
假设不存在全红列。这意味着我们总能在每一列中找到一块蓝色鹅卵石。因此，如果从每一列各取一块蓝色鹅卵石，我们就得到了一种从每一列各取一块鹅卵石且不含任何红色鹅卵石的方式。这是对原假设的否定，因此命题得证。
我们也可以用反证法来处理这个问题；逻辑几乎完全相同，我们从结论的否定出发：即不存在全红列。同样的推理可以让我们得出：总存在一种从每一列各取一块鹅卵石的方式，使得所有鹅卵石都是蓝色的（即没有红色鹅卵石）。
解答来源：solutions/discussion/dis00b-sol.pdf · 2 · confidence: high
题面来源：discussion/dis00b.pdf · 2 · confidence: high
关联课程笔记：Note 0、Note 2。
对于函数 \(f\)，定义集合 \(X\) 的像（image）为集合 \(f(X) = \{y \mid y = f(x) \text{ 对某个 } x \in X\}\)。定义集合 \(Y\) 的逆像（inverse image）或原像（preimage）为集合 \(f^{-1}(Y) = \{x \mid f(x) \in Y\}\)。证明以下命题，其中 \(A\) 和 \(B\) 是集合。
回顾：对于集合 \(X\) 和 \(Y\)，\(X = Y\) 当且仅当 \(X \subseteq Y\) 且 \(Y \subseteq X\)。要证明 \(X \subseteq Y\)，只需证明 \((\forall x)((x \in X) \Rightarrow (x \in Y))\)。
(a) \(f^{-1}(A \cup B) = f^{-1}(A) \cup f^{-1}(B)\)。
(b) \(f(A \cup B) = f(A) \cup f(B)\)。
证明集合相等需分别验证两个包含关系。注意在 (b) 中应从 \(A \cup B\) 中取元素 \(x\) 出发，而不是从 \(f(A \cup B)\) 中取 \(y\) 出发，因为 \(f^{-1}(y)\) 未必是单个元素。
为了证明等式 \(A = B\)，我们需要证明 \(A\) 是 \(B\) 的子集 \(A \subseteq B\)，以及 \(B\) 是 \(A\) 的子集 \(B \subseteq A\)。为了证明左边是右边的子集，我们需要证明如果一个元素是左边的成员，那么它也是右边的成员。
(a) 假设 \(x \in f^{-1}(A \cup B)\)，这意味着 \(f(x) \in A \cup B\)。那么要么 \(f(x) \in A\)，此时 \(x \in f^{-1}(A)\)；要么 \(f(x) \in B\)，此时 \(x \in f^{-1}(B)\)。因此在任何情况下都有 \(x \in f^{-1}(A) \cup f^{-1}(B)\)。这证明了 \(f^{-1}(A \cup B) \subseteq f^{-1}(A) \cup f^{-1}(B)\)。
现在，假设 \(x \in f^{-1}(A) \cup f^{-1}(B)\)。不妨设 \(x \in f^{-1}(A)\)（另一种情况同理）。那么 \(f(x) \in A\)，所以 \(f(x) \in A \cup B\)，因此 \(x \in f^{-1}(A \cup B)\)。对于 \(x \in f^{-1}(B)\) 的情况论证相同。因此，\(f^{-1}(A) \cup f^{-1}(B) \subseteq f^{-1}(A \cup B)\)。
(b) 假设 \(x \in A \cup B\)。那么要么 \(x \in A\)，此时 \(f(x) \in f(A)\)；要么 \(x \in B\)，此时 \(f(x) \in f(B)\)。在任何情况下，\(f(x) \in f(A) \cup f(B)\)，所以 \(f(A \cup B) \subseteq f(A) \cup f(B)\)。
现在，假设 \(y \in f(A) \cup f(B)\)。那么要么 \(y \in f(A)\)，要么 \(y \in f(B)\)。在第一种情况下，存在元素 \(x \in A\) 使得 \(f(x) = y\)；在第二种情况下，存在元素 \(x \in B\) 使得 \(f(x) = y\)。在任何情况下，都存在元素 \(x \in A \cup B\) 使得 \(f(x) = y\)，这意味着 \(y \in f(A \cup B)\)。所以 \(f(A) \cup f(B) \subseteq f(A \cup B)\)。
一个常见的错误是从元素 \(y \in f(A \cup B)\) 出发，然后取 \(f^{-1}(y) \in A \cup B\)。这里的问题在于 \(f^{-1}(y)\) 不一定是单个元素；它可以是一组元素，因此更精确的说法是 \(f^{-1}(\{y\}) \subseteq A \cup B\)。在这里，我们不能直接得出 \(f^{-1}(\{y\}) \subseteq A\) 或 \(f^{-1}(\{y\}) \subseteq B\)，因为 \(f^{-1}(\{y\})\) 可能包含一些在 \(A\) 中的元素和一些在 \(B\) 中的元素。这需要更仔细的考虑；在这种情况下，从元素 \(x \in A \cup B\) 出发会更容易。
这道题的目的是培养精确命名的能力。我们特别命名了左边集合中的一个元素（或左边的原像），然后论证该元素或其像是否属于右边。通过明确地命名一个可以是集合中任意元素的通用元素，我们可以论证它的成员关系及其像或原像。在这些不同概念同时出现的情况下，在论证中保持清晰是有帮助的。
解答来源：solutions/discussion/dis00b-sol.pdf · 2 · confidence: high
题面来源：discussion/dis00b.pdf · 2 · confidence: high
discussion/dis00b.pdfsolutions/discussion/dis00b-sol.pdf