知识焦点
先建立概念地图
- calculus
- integration
- extrema
- double integral
- proof
- contrapositive
- counterexample
- rational and irrational
CS70 · 作业 01
CS 70 Spring 2023 第一次作业，涵盖微积分复习（积分、极值、二重积分）、命题证明与反例、有理数与无理数、孪生素数、机场问题的归纳证明、不等式归纳证明、AM-GM 不等式的非常规归纳证明，以及硬币分割游戏的恒常总分。
知识焦点
建议顺序
先完整作答，再按需展开提示；最后才展开官方参考解答并逐步核对证明与计算。
本地来源
题面与解答均由本地一手资料整理：homework/hw01.pdf、solutions/homework/hw01-sol.pdf
本地一手资料完整提取 · 作业
本节按本地一手资料完整整理，共 9 道大题。本地官方解答已收录 8/9 道并默认折叠；其余题目会明确标注无本地官方解答。
homework/hw01.pdf、solutions/homework/hw01-sol.pdf在开始撰写最终作业提交之前，请简要说明你是如何完成这份作业的。你还与谁一起完成？请列出姓名和电子邮件地址。（如果是在作业讨论会中协作，只需描述该小组即可。）
如实记录协作对象与协作方式；每位同学仍应独立组织并撰写自己的最终答案。
本地资料未提供这道题的官方解答；页面只保留题面与非答案式提示。
题面来源：homework/hw01.pdf · 1 · confidence: high
CS 70 离散数学与概率论 微积分复习部分。
(a) 计算下列积分：
\[ \int_{0}^{\infty} \sin(t) e^{-t} \, dt . \]
(b) 求函数
\[ f(x) = \int_{0}^{x^{2}} t \cos\bigl(\sqrt{t}\bigr) \, dt \]
在区间 \(x \in (-2, 2)\) 中对应局部极大值和局部极小值的 \(x\) 值。并对每个 \(x\) 分类，指出其对应的是局部极大值还是局部极小值。
(c) 计算二重积分
\[ \iint_{R} (2x + y) \, dA , \]
其中 \(R\) 是由直线 \(x = 1\)、\(y = 0\) 与 \(y = x\) 所围成的区域。
(a) 考虑连续两次分部积分（integration by parts），让 \(I\) 表示原积分，经过两次分部积分后会出现 \(-I\)，从而解出 \(I\)。注意在 \(0\) 与 \(\infty\) 处取极限。 (b) 先用微积分基本定理与链式法则求 \(f'(x)\)，再找出 \((-2,2)\) 内的全部驻点，最后通过导数符号变化判断极大/极小。注意 \(\cos(\sqrt{x^{2}}) = \cos(|x|)\) 在 \((-2,2)\) 内可化简为 \(\cos(x)\)。 (c) 把区域 \(R\) 表示为 \(0 \le x \le 1\)，\(0 \le y \le x\)，先对 \(y\) 积分再对 \(x\) 积分。
(a) 令 \(I = \int \sin(t) e^{-t} \, dt\)。取 \(u = \sin(t)\)，\(dv = e^{-t} \, dt\)，则 \(du = \cos(t) \, dt\)，\(v = -e^{-t}\)。于是
\[ I = -\sin(t) e^{-t} + \int e^{-t} \cos(t) \, dt . \]
对 \(\int e^{-t} \cos(t) \, dt\) 再分部积分一次，取 \(u = \cos(t)\)，\(dv = e^{-t} \, dt\)，则 \(du = -\sin(t) \, dt\)，\(v = -e^{-t}\)，得到
\[ \int e^{-t} \cos(t) \, dt = -\cos(t) e^{-t} - \int e^{-t} \sin(t) \, dt = -\cos(t) e^{-t} - I . \]
代回得
\[ I = -\sin(t) e^{-t} - \cos(t) e^{-t} - I \quad\Rightarrow\quad 2I = -\sin(t) e^{-t} - \cos(t) e^{-t} . \]
因此
\[ I = \frac{-\sin(t) e^{-t} - \cos(t) e^{-t}}{2} . \]
取上下限：
\[ \left. I \right|_{0}^{\infty} = \frac{0 - 0}{2} - \frac{0 - 1}{2} = \frac{1}{2} . \]
(b) 令 \(y = x^{2}\)，由链式法则与微积分基本定理
\[ \frac{df}{dx} = \frac{df}{dy} \cdot \frac{dy}{dx} = y \cos(\sqrt{y}) \cdot 2x = 2x^{3} \cos(|x|) = 2x^{3} \cos(x) . \]
令 \(f'(x) = 0\)，在 \((-2,2)\) 内得到驻点 \(x^{*} = 0\) 以及 \(\cos(x^{*}) = 0\) 的解 \(x^{*} = \pm \pi/2\)。
在 \(x = \pi/2\) 两侧：左侧导数为正，右侧导数为负；\(x = -\pi/2\) 同理。故 \(x = \pm \pi/2\) 为局部极大值点。
在 \(x = 0\) 两侧：左侧导数为负，右侧导数为正。故 \(x = 0\) 为局部极小值点。
(c) 将积分写成累次积分：
\[ \int_{0}^{1} \int_{0}^{x} (2x + y) \, dy \, dx . \]
先对 \(y\) 积分：
\[ \int_{0}^{x} (2x + y) \, dy = \left[ 2xy + \frac{y^{2}}{2} \right]_{y=0}^{y=x} = 2x^{2} + \frac{x^{2}}{2} = \frac{5x^{2}}{2} . \]
再对 \(x\) 积分：
\[ \int_{0}^{1} \frac{5x^{2}}{2} \, dx = \left[ \frac{5x^{3}}{6} \right]_{0}^{1} = \frac{5}{6} . \]
解答来源：solutions/homework/hw01-sol.pdf · 1-2 · confidence: high
题面来源：homework/hw01.pdf · 1 · confidence: high
注意 2：对下列每个命题，要么给出证明，要么通过举反例予以证伪。
(a) \((\forall n \in \mathbb{N})\) 若 \(n\) 为奇数，则 \(n^{2} + 4n\) 为奇数。
(b) \((\forall a, b \in \mathbb{R})\) 若 \(a + b \le 15\)，则 \(a \le 11\) 或 \(b \le 4\)。
(c) \((\forall r \in \mathbb{R})\) 若 \(r^{2}\) 为无理数（irrational），则 \(r\) 为无理数。
(d) \((\forall n \in \mathbb{Z}^{+})\; 5n^{3} > n!\)。（注：\(\mathbb{Z}^{+}\) 为正整数集）
(a) 可设 \(n = 2k+1\)，代入化简并提取因子 2；也可因式分解为 \(n(n+4)\) 并利用两个奇数之积仍为奇数。 (b) 考虑用逆否命题（contraposition）：假设 \(a > 11\) 且 \(b > 4\)，会推出什么？ (c) 同样考虑逆否：若 \(r\) 为有理数，则 \(r^{2}\) 为有理数。 (d) 先代入较小的正整数试值，寻找使命题不成立的 \(n\)。
(a) 答案：真。
证法一（直接证明）：设 \(n\) 为奇数，则存在 \(k \in \mathbb{N}\) 使得 \(n = 2k+1\)。代入得
\[ n^{2} + 4n = (2k+1)^{2} + 4(2k+1) = 4k^{2} + 4k + 1 + 8k + 4 = 4k^{2} + 12k + 5 = 2(2k^{2} + 6k + 2) + 1 . \]
由于 \(2k^{2} + 6k + 2 \in \mathbb{N}\)，故 \(n^{2} + 4n\) 为奇数。
证法二（因式分解）：\(n^{2} + 4n = n(n+4)\)。若 \(n\) 为奇数，则 \(n+4\) 也为奇数，两个奇数之积仍为奇数。
(b) 答案：真。
逆否证明：假设 \(a > 11\) 且 \(b > 4\)（这等价于 \(\neg(a \le 11 \vee b \le 4)\)）。则 \(a + b > 15\)（等价于 \(\neg(a+b \le 15)\)）。因此逆否命题成立，原命题成立。
(c) 答案：真。
逆否证明：设 \(r\) 为有理数，则存在整数 \(a, b\) 且 \(b \neq 0\)，使得 \(r = a/b\)。于是 \(r^{2} = a^{2}/b^{2}\)，其中 \(a^{2}, b^{2}\) 为整数且 \(b^{2} \neq 0\)，故 \(r^{2}\) 为有理数。由逆否可知，若 \(r^{2}\) 为无理数，则 \(r\) 为无理数。
(d) 答案：假。
反例：取 \(n = 7\)，则 \(5n^{3} = 5 \cdot 7^{3} = 5 \cdot 343 = 1715\)，而 \(7! = 5040\)。由于 \(5n^{3} < n!\)，命题不成立。
解答来源：solutions/homework/hw01-sol.pdf · 3 · confidence: high
题面来源：homework/hw01.pdf · 1 · confidence: high
注意 2：证明一个非零有理数与一个无理数的乘积为无理数。
考虑用反证法：设非零有理数 \(a\) 与无理数 \(b\) 的乘积 \(ab = c\) 为有理数，利用 \(a \neq 0\) 可把 \(b\) 写成两个有理数之商，从而推出 \(b\) 为有理数，引出矛盾。注意 \(0\) 是有理数，因此 \(a \neq 0\) 保证了 \(c\) 与 \(a\) 均可逆。
反证法。设 \(ab = c\)，其中 \(a \neq 0\) 为有理数，\(b\) 为无理数，并假设 \(c\) 为有理数。由于 \(0\) 是有理数，\(b\) 为无理数蕴含 \(c \neq 0\)，且 \(a \neq 0\)。于是可写 \(a = p/q\)，\(c = r/s\)，其中 \(p, q, r, s\) 均为非零整数。则
\[ b = \frac{c}{a} = \frac{rq}{ps} , \]
这是两个非零整数之商，故 \(b\) 为有理数，与假设矛盾。因此，非零有理数与无理数的乘积必为无理数。
解答来源：solutions/homework/hw01-sol.pdf · 3 · confidence: high
题面来源：homework/hw01.pdf · 1 · confidence: high
注意 2：
(a) 设 \(p > 3\) 为素数。证明：存在某个整数 \(k\)，使得 \(p\) 具有 \(3k+1\) 或 \(3k-1\) 的形式。
(b) 孪生素数（twin primes）是指差为 \(2\) 的一对素数 \(p\) 与 \(q\)。利用 (a) 证明：\(5\) 是唯一一个属于两个不同孪生素数对的素数。
(a) 任一整数必为 \(3k\)、\(3k+1\)、\(3k+2\) 三者之一；注意 \(3k+2 = 3(k+1)-1\)。考虑其逆否：形如 \(3k\) 且大于 \(3\) 的整数必为合数。 (b) 先验证不超过 \(5\) 的素数，再对任意素数 \(m > 5\) 用 (a) 分两种情形讨论 \(m+2\) 与 \(m-2\) 的素性。
(a) 任一整数必可写成 \(3k\)、\(3k+1\) 或 \(3k+2\) 三者之一。注意到 \(3k+2 = 3(k+1)-1\)，因此后两种形式可统一视为 \(3k+1\) 或 \(3k-1\)。考虑逆否命题：若整数 \(m > 3\) 具有 \(3k\) 的形式，则 \(m\) 被 \(3\) 整除，必为合数。故逆否成立，原命题成立：素数 \(p > 3\) 必为 \(3k+1\) 或 \(3k-1\) 的形式。
(b) 先检查不超过 \(5\) 的素数，其中仅 \(5\) 属于两对孪生素数：\((3,5)\) 与 \((5,7)\)。下设素数 \(m > 5\)，检验 \(m+2\) 与 \(m-2\) 是否均为素数。由于 \(m > 5\)，有 \(m+2 > 3\) 且 \(m-2 > 3\)，可对 \(m\) 应用 (a) 分情形讨论。
情形 1：\(m = 3k+1\)。则 \(m+2 = 3k+3 = 3(k+1)\)，被 \(3\) 整除，故 \(m+2\) 不是素数。
情形 2：\(m = 3k-1\)。则 \(m-2 = 3k-3 = 3(k-1)\)，被 \(3\) 整除，故 \(m-2\) 不是素数。
因此在两种情形中，\(m+2\) 与 \(m-2\) 至少有一个不是素数，\(m\) 不可能同时属于两对孪生素数。故 \(5\) 是唯一属于两个不同孪生素数对的素数。
解答来源：solutions/homework/hw01-sol.pdf · 3-4 · confidence: high
题面来源：homework/hw01.pdf · 2 · confidence: high
注意 3：设有 \(2n+1\) 个机场，其中 \(n\) 为正整数。任意两个机场之间的距离互不相同。对每个机场，恰好有一架飞机从该机场起飞，并飞往距它最近的机场。用归纳法证明：存在一个机场，没有任何飞机以它为目的地。
顶点：A, B, C。有向边：B→C, C→B, A→B（或 A→C）。约束：|BC| 为三者距离中最小。
来源：homework/hw01.pdf · 2
对 \(n\) 进行归纳。基础情形 \(n=1\) 时共 \(3\) 个机场，利用"距离互异"可确定最近机场对。归纳步骤中，考虑距离最近的一对机场，它们必然互飞；移除这两个机场后对剩下的 \(2k+1\) 个机场应用归纳假设，再考察把这两个机场加回后是否会有飞机改飞它们。关键观察：加回这两个机场后，原本没有入港的机场 \(Z\) 仍不会有飞机以它为目的地。
对 \(n\) 进行归纳。
基础情形 \(n=1\)：设三个机场为 \(A, B, C\)，距离分别为 \(|AB|, |AC|, |BC|\)。不妨设 \(B, C\) 是距离最近的一对（由距离互异，最近对唯一）。则从 \(B\) 与 \(C\) 起飞的飞机彼此对飞。从 \(A\) 起飞的飞机必然飞向 \(B\) 或 \(C\)，因此机场 \(A\) 没有任何飞机以它为目的地。
归纳假设：设当 \(n=k\)（即 \(2k+1\) 个机场）时命题成立。
归纳步骤 \(n=k+1\)：设有 \(2k+3\) 个机场。取距离最近的一对机场，它们起飞的飞机必然对飞。移除这两个机场，问题化为 \(2k+1\) 个机场的情形。由归纳假设，在剩下的 \(2k+1\) 个机场中存在一个机场 \(Z\) 没有任何飞机以它为目的地。
把被移除的两个机场加回后，飞机的航线可能改变：某些飞机可能改飞向这两个新加入的机场（因为它们可能比原来的目的地更近），但不会有飞机改以 \(Z\) 为目的地。此外，被加回的两个机场彼此对飞，也不会以 \(Z\) 为目的地。因此 \(Z\) 在加回两个机场后仍没有任何飞机以它为目的地，命题对 \(n=k+1\) 成立。
由归纳法，命题对所有 \(n \ge 1\) 成立。
解答来源：solutions/homework/hw01-sol.pdf · 4 · confidence: high
题面来源：homework/hw01.pdf · 2 · confidence: high
注意 3：对所有正整数 \(n \ge 1\)，证明
[ \frac{1}{3^{1}} + \frac{1}{3^{2}} + \dots + \frac{1}{3^{n}} < \frac{1}{2} .
（注：虽然可利用无穷等比级数公式证明，但本题要求使用归纳法。若在归纳步骤中遇到困难，尝试加强归纳假设。能否改为证明一个等式而非不等式？）
先计算前几项，观察规律：\(1/3 = 1/2 - 1/6\)，\(1/3 + 1/9 = 1/2 - 1/18\)，\(1/3 + 1/9 + 1/27 = 1/2 - 1/54\)。猜测加强命题：\(\sum_{i=1}^{n} 1/3^{i} = 1/2 - 1/(2 \cdot 3^{n})\)，并用归纳法证明该等式，原不等式即为其推论。
先尝试直接归纳发现难以推进。计算前几项寻找更强的归纳假设：
\(1/3 = 1/2 - 1/6\)；
\(1/3 + 1/9 = 1/2 - 1/18\)；
\(1/3 + 1/9 + 1/27 = 1/2 - 1/54\)。
猜测加强命题：
\[ \frac{1}{3^{1}} + \frac{1}{3^{2}} + \dots + \frac{1}{3^{n}} = \frac{1}{2} - \frac{1}{2 \cdot 3^{n}} . \]
基础情形 \(n=1\)：\(1/3 = 1/2 - 1/6\)，成立。
归纳假设：设命题对某个 \(n \ge 1\) 成立。
归纳步骤：
\[ \sum_{i=1}^{n+1} \frac{1}{3^{i}} = \left(\frac{1}{2} - \frac{1}{2 \cdot 3^{n}}\right) + \frac{1}{3^{n+1}} = \frac{1}{2} - \frac{3}{2 \cdot 3^{n+1}} + \frac{2}{2 \cdot 3^{n+1}} = \frac{1}{2} - \frac{1}{2 \cdot 3^{n+1}} . \]
故加强命题对 \(n+1\) 成立。于是原不等式
\[ \sum_{i=1}^{n} \frac{1}{3^{i}} = \frac{1}{2} - \frac{1}{2 \cdot 3^{n}} < \frac{1}{2} \]
成立。
解答来源：solutions/homework/hw01-sol.pdf · 5 · confidence: high
题面来源：homework/hw01.pdf · 2 · confidence: high
注意 3：对非负实数 \(a_{1}, \dots, a_{n}\)，算术平均（arithmetic mean）定义为
[ \frac{a_{1} + \dots + a_{n}}{n} ,
几何平均（geometric mean）定义为
[ \sqrt[n]{a_{1} \cdots a_{n}} .
本题将证明"AM-GM"不等式：对所有正整数 \(n \ge 2\) 及任意非负实数 \(a_{1}, \dots, a_{n}\)，
[ \frac{a_{1} + \dots + a_{n}}{n} \ge \sqrt[n]{a_{1} \cdots a_{n}} .
我们将对 \(n\) 以一种不寻常的方式进行归纳。
(a) 证明不等式对 \(n = 2\) 成立，即对非负实数 \(a_{1}, a_{2}\) 证明
[ \frac{a_{1} + a_{2}}{2} \ge \sqrt{a_{1} a_{2}} .
（以下恒等式可能有用：\((\sqrt{a} - \sqrt{b})^{2} = a - 2\sqrt{ab} + b\)。）
(b) 设对某个正整数 \(k\)，AM-GM 不等式对 \(n = 2^{k}\) 成立。证明 AM-GM 不等式对 \(n = 2^{k+1}\) 成立。（提示：考虑如何利用 \(n = 2\) 的 AM-GM 不等式。）
(c) 设对某个正整数 \(k \ge 2\)，AM-GM 不等式对 \(n = k\) 成立。证明 AM-GM 不等式对 \(n = k-1\) 成立。（提示：在 \(n = k\) 的 AM-GM 表达式中，考虑代入 \(a_{k} = \frac{a_{1} + \dots + a_{k-1}}{k-1}\)。）
(d) 论证为何 (a)–(c) 蕴含 AM-GM 不等式对所有正整数 \(n \ge 2\) 成立。
(a) 从 \((\sqrt{a_{1}} - \sqrt{a_{2}})^{2} \ge 0\) 出发，双向变形至目标不等式。注意每一步都是双向的，因此推理成立。 (b) 把 \(2^{k+1}\) 个数分成两组各 \(2^{k}\) 个，分别对每组应用 \(n = 2^{k}\) 的 AM-GM，得到两个算术平均 \(l_{1}, l_{2}\) 与两个几何平均 \(r_{1}, r_{2}\)；再对 \(l_{1}, l_{2}\) 用 \(n = 2\) 的 AM-GM。 (c) 令 \(a_{k} = \frac{a_{1} + \dots + a_{k-1}}{k-1}\)，代入 \(n = k\) 的 AM-GM，化简后两边同取 \(k\) 次幂、再同除以 \(\frac{a_{1} + \dots + a_{k-1}}{k-1}\)，最后取 \((k-1)\) 次根。 (d) 对任意 \(k\)，取满足 \(2^{\ell} \ge k\) 的幂次，由 (a) 与 (b) 得 \(n = 2^{\ell}\) 成立，再由 (c) 向下归纳到 \(n = k\)。
(a) 由于 \(a_{1}, a_{2}\) 为非负实数，\((\sqrt{a_{1}} - \sqrt{a_{2}})^{2} \ge 0\)。双向变形：
[ (\sqrt{a_{1}} - \sqrt{a_{2}})^{2} \ge 0 \;\Leftrightarrow\; a_{1} - 2\sqrt{a_{1}a_{2}} + a_{2} \ge 0 \;\Leftrightarrow\; a_{1} + a_{2} \ge 2\sqrt{a_{1}a_{2}} \;\Leftrightarrow\; \frac{a_{1} + a_{2}}{2} \ge \sqrt{a_{1}a_{2}} .
故 \(n = 2\) 时不等式成立。由于每一步均为双向，反向推理亦成立，但一般不应假设待证结论为真。
(b) 设 \(a_{1}, \dots, a_{2^{k}}, a_{2^{k}+1}, \dots, a_{2^{k+1}}\) 为任意非负实数。由归纳假设，
[ l_{1} = \frac{a_{1} + \dots + a_{2^{k}}}{2^{k}} \ge \sqrt[2^{k}]{a_{1} \cdots a_{2^{k}}} = r_{1} ,
l_{2} = \frac{a_{2^{k}+1} + \dots + a_{2^{k+1}}}{2^{k}} \ge \sqrt[2^{k}]{a_{2^{k}+1} \cdots a_{2^{k+1}}} = r_{2} .
对 \(l_{1}, l_{2}\) 应用 (a) 得
[ \frac{l_{1} + l_{2}}{2} \ge \sqrt{l_{1} l_{2}} \ge \sqrt{r_{1} r_{2}} .
左边
[ \frac{l_{1} + l_{2}}{2} = \frac{\frac{a_{1} + \dots + a_{2^{k}}}{2^{k}} + \frac{a_{2^{k}+1} + \dots + a_{2^{k+1}}}{2^{k}}}{2} = \frac{a_{1} + \dots + a_{2^{k+1}}}{2^{k+1}} ,
右边
[ \sqrt{r_{1} r_{2}} = \sqrt{\sqrt[2^{k}]{a_{1} \cdots a_{2^{k}}} \cdot \sqrt[2^{k}]{a_{2^{k}+1} \cdots a_{2^{k+1}}}} = \sqrt[2^{k+1}]{a_{1} \cdots a_{2^{k+1}}} .
故 \(\frac{a_{1} + \dots + a_{2^{k+1}}}{2^{k+1}} \ge \sqrt[2^{k+1}]{a_{1} \cdots a_{2^{k+1}}}\)，即 AM-GM 对 \(n = 2^{k+1}\) 成立。
(c) 设 \(a_{1}, \dots, a_{k}\) 为任意非负实数。由归纳假设
[ \frac{a_{1} + \dots + a_{k}}{k} \ge \sqrt[k]{a_{1} \cdots a_{k}} .
令 \(a_{k} = \frac{a_{1} + \dots + a_{k-1}}{k-1}\)，则
[ \frac{a_{1} + \dots + a_{k-1} + \frac{a_{1} + \dots + a_{k-1}}{k-1}}{k} = \frac{\frac{k}{k-1}(a_{1} + \dots + a_{k-1})}{k} = \frac{a_{1} + \dots + a_{k-1}}{k-1} ,
且
[ \sqrt[k]{a_{1} \cdots a_{k-1} \cdot \frac{a_{1} + \dots + a_{k-1}}{k-1}} .
于是
[ \frac{a_{1} + \dots + a_{k-1}}{k-1} \ge \sqrt[k]{a_{1} \cdots a_{k-1} \cdot \frac{a_{1} + \dots + a_{k-1}}{k-1}} .
两边同取 \(k\) 次幂，再同除以 \(\frac{a_{1} + \dots + a_{k-1}}{k-1}\)，得
[ \left(\frac{a_{1} + \dots + a_{k-1}}{k-1}\right)^{k-1} \ge a_{1} \cdots a_{k-1} .
取 \((k-1)\) 次根得
[ \frac{a_{1} + \dots + a_{k-1}}{k-1} \ge \sqrt[k-1]{a_{1} \cdots a_{k-1}} ,
即 AM-GM 对 \(n = k-1\) 成立。
(d) 对任意正整数 \(k\)，存在 \(2\) 的幂 \(2^{\ell} \ge k\)。由 (a) 的基础情形出发，反复应用 (b) 可得 AM-GM 对 \(n = 2^{\ell}\) 成立；再反复应用 (c) 从 \(2^{\ell}\) 向下归纳到 \(n = k\)。故 AM-GM 不等式对所有正整数 \(n \ge 2\) 成立。
解答来源：solutions/homework/hw01-sol.pdf · 6-8 · confidence: high
题面来源：homework/hw01.pdf · 2-3 · confidence: high
注意 3：你的"朋友"Stanley Ford 建议你和他玩下面的游戏。你和他各自从一堆 \(n\) 枚硬币开始。每一轮，你选择自己的一堆硬币（其中至少含两枚硬币）并将其分成两堆，每堆至少含一枚硬币。该轮的得分为所得两堆硬币数量的乘积（例如，把一堆 5 枚硬币分成 3 枚与 2 枚两堆，则得分为 \(3 \cdot 2 = 6\)）。你持续轮流操作，直到所有硬币堆都只含一枚硬币。随后 Stan 用他的一堆 \(n\) 枚硬币进行同样的游戏，最终总得分高者获胜。
证明：无论你如何选择分堆方式，你的总得分恒为
[ \frac{n(n-1)}{2} .
（这意味着你和 Stan 的最终得分与操作无关，因此这个游戏相当无聊。）
考虑对 \(n\) 使用强归纳法（strong induction）。基础情形 \(n=1\) 时游戏立即结束，总得分为 \(0\)。在归纳步骤中，第一次分堆把 \(n+1\) 枚分成 \(s_{1}\) 与 \(s_{2}\) 两堆（\(s_{1}+s_{2}=n+1\)），总得分由三部分构成：本次得分 \(s_{1}s_{2}\)，以及后续对两堆分别得分，后者可由归纳假设得到。把三部分之和化简为 \((n+1)n/2\)。
对 \(n\) 使用强归纳法。
基础情形 \(n=1\)：起始即为一堆 1 枚硬币，游戏立即终止，总得分为 \(0\)，而 \(\frac{n(n-1)}{2} = \frac{1 \cdot 0}{2} = 0\)，成立。
归纳假设：设对任意 \(i \in \{1, 2, \dots, n\}\)，从 \(i\) 枚硬币开始无论采用何种策略，总得分均为 \(\frac{i(i-1)}{2}\)。
归纳步骤 \(n+1\)：从 \(n+1\) 枚硬币开始。第一步必把整堆分成两堆，记其大小为 \(s_{1}, s_{2}\)，满足 \(s_{1} + s_{2} = n+1\) 且 \(s_{1}, s_{2} \ge 1\)。总得分由三部分构成：
本次得分：\(s_{1}s_{2}\)；
后续对第一堆的得分：由归纳假设为 \(\frac{s_{1}(s_{1}-1)}{2}\)；
后续对第二堆的得分：由归纳假设为 \(\frac{s_{2}(s_{2}-1)}{2}\)。
故总得分为
[ s_{1}s_{2} + \frac{s_{1}(s_{1}-1)}{2} + \frac{s_{2}(s_{2}-1)}{2} = \frac{s_{1}(s_{1}-1) + 2s_{1}s_{2} + s_{2}(s_{2}-1)}{2} .
重组分子：
[ \frac{[s_{1}(s_{1}-1) + s_{1}s_{2}] + [s_{2}(s_{2}-1) + s_{1}s_{2}]}{2} = \frac{s_{1}(s_{1}+s_{2}-1) + s_{2}(s_{1}+s_{2}-1)}{2} = \frac{(s_{1}+s_{2})(s_{1}+s_{2}-1)}{2} .
由 \(s_{1}+s_{2} = n+1\)，得总得分
[ \frac{(n+1)(n+1-1)}{2} = \frac{(n+1)n}{2} ,
即为所求。归纳完成。
解答来源：solutions/homework/hw01-sol.pdf · 8-9 · confidence: high
题面来源：homework/hw01.pdf · 3 · confidence: high
homework/hw01.pdfsolutions/homework/hw01-sol.pdf