CS70 Disc 0B

---

1. 完美平方

1.1 证明

(a) 如果 $ n^2 $ 是奇数，则 $ n $ 也必须是奇数。
证明方法：使用对立命题的证明。

• 对立命题为：“如果 $ n $ 是偶数，则 $ n^2 $ 也是偶数”。
  
• 假设 $ n $ 是偶数，可以表示为 $ n = 2k $（其中 $ k $ 是某个整数）。
  
• 计算得：
  $ n^2 = (2k)^2 = 4k^2 = 2(2k^2) $
  
• 因此，$ n^2 $ 是偶数，证明了对立命题成立。
  
• 由此可知，如果 $ n^2 $ 是奇数，则 $ n $ 必须是奇数。

(b) 如果 $ n^2 $ 是奇数，则 $ n^2 $ 可以写成 $ 8k + 1 $ 的形式，对于某个整数 $ k $。
证明方法：直接证明。

• 根据前面的证明，知道 $ n^2 $ 是奇数，所以 $ n $ 也是奇数，可以表示为 $ n = 2l + 1 $（其中 $ l $ 是某个整数）。
  
• 计算得：
  $ n^2 = (2l + 1)^2 = 4l^2 + 4l + 1 = 4l(l + 1) + 1 $
  
• 因为 $ l $ 和 $ l + 1 $ 中必有一个是偶数，所以 $ l(l + 1) $ 是 $ 2k $ 的形式（对于某个整数 $ k ）。
  
• 由此可得：
  $ n^2 = 8k + 1 $

---

2. 朋友数量

2.1 证明

定理：如果聚会中有 $ n $ 个人，则至少有 2 个人有相同数量的朋友。
证明方法：使用反证法。

• 假设所有人都有不同的朋友数量。
  
• 每个人的朋友数量范围从 0 到 $ n-1 \(，因此可以得出结论，\) {0, 1, , n-1} $ 中的每个数字都被正好一个人占有。
  
• 特别地，存在一个人有 $ n-1 $ 个朋友（与每个人都是朋友），以及一个人有 0 个朋友（与任何人都不是朋友）。
  
• 由于友谊是双向的，存在矛盾，因为不可能一个人和所有人都是朋友，同时另一个人没有朋友。

这里使用了鸽巢原理。假设每个人都有不同的朋友数量，会导致 $ n $ 个容器（朋友数量），但 $ 0 $ 和 $ n-1 $ 这两个容器不能同时被占用，因此至少有一个容器必须有多个物体，即至少有两个人有相同的朋友数量。

---

3. 石头问题

3.1 证明

定理：如果你有一个矩形数组的石头，每个石头是红色或蓝色的。假设在每种选择每列中的一个石头的方式中，选出的石头中总是存在红色石头。那么必须存在一列全是红色的石头。

证明方法：通过对立命题的证明。

• 对立命题为：“如果不存在一列全是红色的石头，则总存在一种选择每列中一个石头的方法，使得选出的石头中没有红色石头”。
  
• 假设不存在一列全是红色的石头。这意味着每一列中总能找到一个蓝色石头。
  
• 如果我们从每一列中选一个蓝色石头，那么就形成了一种选择方法，使得没有红色石头。这是对原假设的否定，因此得出结论。

也可以通过反证法来解决这个问题。逻辑几乎相同，从否定结论开始，得出最终的结论。

---