1.8　习题Exercises

本页为译文 + 高中讲解合一：黑色正文（题目编号

）为对原书习题的忠实翻译；彩色框（解题思路 / 分步推演 / 例）与配图为面向高中生的方法提示，逐步推演、举例、画图，不用比喻。这里只给思路与下手方向，完整解答见对应的“习题解答”一节。
本节用到的三类证明技巧（原书在习题前的小结）
1. 组合证明（combinatorial proof）：要证两个表达式 \(A\) 与 \(B\) 相等，就说明它们都在数同一个集合的元素个数。
2. 双射证明（bijective proof）：要证两个有限集合 \(S\) 与 \(T\) 元素个数相同，就构造一个双射 \(f:S\to T\)。
3. 反证法（indirect proof）：要证一个命题为真，先假设它的反面成立，再从中推出矛盾。
本节大量习题正是这三种武器的练习。带 “+” 号的题为进阶题。

1. 某航空公司有两个售票柜台。在某一时刻，第一个柜台前排了 \(n\) 个人，第二个柜台前排了 \(m\) 个人。

   (a) 假设排队不必按“先到先得”的顺序。在不允许任何人换柜台的前提下，重新排列这两条队伍共有多少种方式？

   (b) 用 (a) 的答案来说明（论证）约定 \(0!=1\) 的合理性。

   思路(a) 两条队伍互不干扰，用乘法原理（product rule）：第一队 \(n\) 人的排法有 \(n!\) 种，第二队 \(m\) 人的排法有 \(m!\) 种，相乘得 \(n!\,m!\)。
   (b) 取一种特殊情形让等式逼着我们承认 \(0!=1\)。
   1. 把第一队 \(n\) 个人排成一列：第 1 个位置有 \(n\) 种选法，第 2 个位置有 \(n-1\) 种……共 \(n!\) 种。第二队同理 \(m!\) 种。
   2. 两队各自独立，总方案 \(=n!\cdot m!\)。
   3. (b) 令 \(m=0\)（第二队没有人）。此时两队“整体排法”显然就等于第一队自己的排法 \(n!\) 种。
   4. 按公式应为 \(n!\cdot 0!\)，于是 \(n!\cdot 0!=n!\)，两边除以 \(n!\) 得 \(0!=1\)。

2. 用与上一题类似的方式，论证约定 \(m^0=1\) 的合理性。

   思路\(m^k\) 数的是“把 \(k\) 个有标号物体各自从 \(m\) 个盒子里选一个放”的方式数（每个物体 \(m\) 种选择，乘起来）。让 \(k=0\)：没有物体要放，什么都不做本身算 \(1\) 种方式。
   1. 把“长度为 \(k\)、每位取自 \(m\) 个符号”的序列个数记作 \(m^k\)。
   2. 当 \(k=0\) 时，唯一的序列是空序列，恰好 \(1\) 个。
   3. 所以约定 \(m^0=1\) 与这个计数一致。

3. 在 \(n\times n\) 的棋盘上放置 \(n\) 个车（rook），使得任意两个车都不互相攻击，共有多少种方法？

   思路车互不攻击 \(\Leftrightarrow\) 每行恰好一个、每列恰好一个。于是“放法”等价于行到列的一一对应（排列）。
   1. 第 1 行的车放在哪一列：\(n\) 种选择。
   2. 第 2 行不能与第 1 行同列：剩 \(n-1\) 种。依次类推。
   3. 总数为 \(n\cdot(n-1)\cdots 1=n!\)。

4. 在 \(n\times n\) 的棋盘上放置若干个（可以是任意数量，含 0 个）车，使得任意两个车都不互相攻击，共有多少种方法？

   思路这次车的个数 \(k\) 可变（\(0\le k\le n\)）。先选 \(k\) 个，再按上一题排列，最后对 \(k\) 求和。
   1. 固定放 \(k\) 个车：从 \(n\) 行里选 \(k\) 行用 \(\binom{n}{k}\) 种，从 \(n\) 列里选 \(k\) 列用 \(\binom{n}{k}\) 种，再把选中的行与列一一配对 \(k!\) 种。即 \(\binom{n}{k}^2 k!\)。
   2. 对所有可能的 \(k\) 求和：\(\displaystyle\sum_{k=0}^{n}\binom{n}{k}^2 k!\)。
   3. 可化简为 \(\displaystyle\sum_{k=0}^{n}\binom{n}{k}\frac{n!}{(n-k)!}\)，验证小例子 \(n=1\) 得 \(2\)（不放 / 放一个）。

5. 一场长跑比赛有 15 名选手，其中包括 Amy 和 Bob。若已知 Amy 的名次领先于 Bob，问可能的比赛结果（完整名次）有多少种？

   思路用对称性 + 除法。15 人全排列共 \(15!\) 种；在每一种里，要么 Amy 在前，要么 Bob 在前，两种情况一一对应、各占一半。
   1. 无约束时名次共 \(15!\) 种。
   2. 把每个排列中 Amy 与 Bob 互换，得到一个“反向”排列，这是 \(15!\) 个排列上的一个配对（双射）。
   3. 每对中恰有一个满足“Amy 在前”，故答案 \(=\dfrac{15!}{2}\)。

6. 在佛罗里达某彩票游戏中，需要从 49 个号码里命中 6 个才能中奖。为了确保命中一注完美匹配，最少要买多少张彩票？

   思路“确保命中”就是把所有可能的 6 元子集全买下来，个数即组合数 \(\binom{49}{6}\)。
   1. 从 49 个号里无序取 6 个的方式数为 \(\binom{49}{6}=\dfrac{49!}{6!\,43!}\)。
   2. 逐项约简：\(\dfrac{49\cdot48\cdot47\cdot46\cdot45\cdot44}{720}=13\,983\,816\)。

7. 有多少个四位正整数，既含有数字 3，又能被 5 整除？

   思路“含有数字 3”不好正面数，用减法原理（补集法）：在“被 5 整除的四位数”里减去“被 5 整除但不含数字 3”的。
   1. 四位数被 5 整除：末位是 0 或 5。总数 \(A\)：首位 \(9\) 种（1–9）、中间两位各 \(10\) 种、末位 \(2\) 种，\(|A|=9\cdot10\cdot10\cdot2=1800\)。
   2. 其中不含 3 的（坏家伙 \(B\)）：首位不能是 0 或 3，得 \(8\) 种；中间两位不能是 3，各 \(9\) 种；末位是 0 或 5（都不是 3），\(2\) 种。\(|B|=8\cdot9\cdot9\cdot2=1296\)。
   3. 所求 \(=|A|-|B|=1800-1296=504\)。

8. 某公寓楼的门只能用四位数密码打开。一位住户忘了密码，但记得密码恰好用到数字 3、5、9 这三个数字，且不含任何其他数字。在最坏情况下，他最多要试多少次才能进楼？

   思路“恰好用到 3、5、9 三个数字”意味着四位里每位取自 \(\{3,5,9\}\)，且三种数字全都出现。先数“每位取自三数”的全部，再减去“漏掉某个数字”的（容斥）。
   1. 每位 3 选 1：共 \(3^4=81\) 个四位串。
   2. 减去只用到至多两种数字的：选掉 1 个不用的数字有 \(\binom{3}{1}\) 种，剩两种填四位得 \(2^4\)，但只用一种的被减两次要加回。
   3. 容斥：\(3^4-\binom{3}{1}2^4+\binom{3}{2}1^4=81-48+3=36\)。最坏情况需试 \(36\) 次。

9. 把数字 \(1,1,2,2,3,4,5\) 排成一列，使得数字 3 和 4 不相邻，共有多少种排法？

   思路“不相邻”用减法：先数全部排列（含重复元素），再减去“3、4 相邻”的。重复元素用多重集排列公式 \(\dfrac{n!}{n_1!\,n_2!\cdots}\)。
   1. 全部排列：7 个位置，1 和 2 各重复两次，故 \(\dfrac{7!}{2!\,2!}=1260\)。
   2. “3 4 相邻”：把 3、4 捆成一个整体（两种内部顺序 34 或 43），相当于排 6 个对象，其中仍有两个 1、两个 2：\(2\cdot\dfrac{6!}{2!\,2!}=2\cdot180=360\)。
   3. 不相邻 \(=1260-360=900\)。

10. 一名学生在书店打工，要求每周工作至少 4 天、至多 5 天，且其中至少一天是周末（周六或周日）。这名学生每周可以有多少种不同的排班表？

    思路按工作天数 4 或 5 分类；每类用“总选法减去不含周末的选法”。一周 7 天里有 2 个周末日、5 个工作日。
    1. 工作 4 天：从 7 天选 4 天 \(\binom{7}{4}=35\)；其中全是平日（4 天都来自 5 个平日）\(\binom{5}{4}=5\)。含周末的 \(=35-5=30\)。
    2. 工作 5 天：\(\binom{7}{5}=21\)；全平日 \(\binom{5}{5}=1\)。含周末 \(=21-1=20\)。
    3. 总计 \(30+20=50\) 种。

11. 一名大学橄榄球教练要从 20 名新生中挑选 4 人授予奖学金，这 20 人里一半是进攻球员、一半是防守球员。教练可以任意发放奖学金，只要进攻球员和防守球员各至少有一人获得奖学金即可。教练有多少种可能的方案？

    思路同样用补集：从 20 人任选 4 人，减去“全是进攻”和“全是防守”两种不合法的情形。进攻、防守各 10 人。
    1. 从 20 人选 4 人：\(\binom{20}{4}=4845\)。
    2. 全进攻：\(\binom{10}{4}=210\)；全防守：\(\binom{10}{4}=210\)。
    3. 合法 \(=4845-210-210=4425\)。

12. 考虑例 1.26 中讨论过的方格网。从 \(O=(0,0)\) 走到 \(A=(6,6)\)，若必须经过 \(B=(4,4)\)，但必须避开 \(C=(3,1)\)，共有多少种走法？（每步只能向右或向上。）

    思路格路计数：从 \((0,0)\) 到 \((a,b)\) 的最短路有 \(\binom{a+b}{a}\) 条。先用“经过 \(B\)”拆成两段相乘，再在前半段里用减法去掉经过 \(C\) 的。
    1. “经过 \(B\)”\(=O\to B\) 的路数 \(\times\) \(B\to A\) 的路数 \(=\binom{8}{4}\cdot\binom{4}{2}\)。
    2. “经过 \(B\) 且经过 \(C\)”\(=O\to C\to B\to A=\binom{4}{3}\cdot\binom{4}{1}\cdot\binom{4}{2}\)（\(C=(3,1)\) 到 \(B=(4,4)\) 需右 1 上 3）。
    3. 所求 \(=\)（经过 \(B\)）\(-\)（经过 \(B\) 且经过 \(C\)），代入数字即得。

13. 证明公式 (1.7)。

    思路(1.7) 是本章给出的二项式系数恒等式（关于 \(\binom{n}{k}\) 的对称/递推关系）。用组合证明：让等式两边数同一类对象（从 \(n\) 元集中选 \(k\) 元子集，按某元素“选不选”分两类），即得递推 \(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\) 一类的结论。

14. 证明：对一切满足 \(k\le n\) 的正整数 \(k,n\)，有 \[\binom{n}{k}=\binom{k-1}{k-1}+\binom{k}{k-1}+\cdots+\binom{n-1}{k-1}.\]

    思路（曲棍球棒恒等式 / 组合证明）右边按“被选中的最大元素是谁”给 \(k\) 元子集分类。
    1. 从 \(\{1,2,\dots,n\}\) 中取 \(k\) 元子集，共 \(\binom{n}{k}\) 个（左边）。
    2. 按子集中最大元素 \(=j\) 分类（\(j\) 从 \(k\) 到 \(n\)）：其余 \(k-1\) 个元素取自 \(\{1,\dots,j-1\}\)，有 \(\binom{j-1}{k-1}\) 种。
    3. 对 \(j=k,k+1,\dots,n\) 求和，恰为右边。也可对 \(n\) 用归纳法配合帕斯卡递推。

15. (+) 设 \(n,p,q\) 为固定正整数，满足 \(p\le n\)、\(q\le n\)。证明恒等式 \[\binom{n}{p}\binom{n}{q}=\sum_{k=0}^{n}\binom{n}{k}\binom{n-k}{p-k}\binom{n-k}{q-k}.\]

    思路（双计数）两边都数“在 \([n]\) 中选一个 \(p\) 元子集 \(P\) 与一个 \(q\) 元子集 \(Q\)”的方式，右边按 \(k=|P\cap Q|\) 分类。
    1. 左边：独立地选 \(P\)（\(\binom{n}{p}\)）和 \(Q\)（\(\binom{n}{q}\)）。
    2. 右边：先选公共部分 \(P\cap Q\)（\(k\) 个，\(\binom{n}{k}\)）；在剩 \(n-k\) 个里选 \(P\) 独有的 \(p-k\) 个（\(\binom{n-k}{p-k}\)）；再在剩下里选 \(Q\) 独有的 \(q-k\) 个（\(\binom{n-k}{q-k}\)）。
    3. 对 \(k\) 求和，两种数法相等。

16. 设 \(n=4k+2\)（\(k\) 为某个非负整数）。证明：\([n]\) 的全部子集中，恰好有四分之一的子集其大小能被 4 整除。

    思路（单位根筛 / 复数代入）子集按大小计数即二项式系数，对 \((1+x)^n\) 代入 \(x=1,-1,i,-i\)，把“下标 \(\equiv 0\pmod 4\)”的项筛出来。
    1. 大小被 4 整除的子集数 \(=\dfrac14\big[(1+1)^n+(1-1)^n+(1+i)^n+(1-i)^n\big]\)。
    2. \((1+i)^n+(1-i)^n=2\cdot 2^{n/2}\cos\frac{n\pi}{4}\)。当 \(n=4k+2\) 时 \(\frac{n\pi}{4}=k\pi+\frac{\pi}{2}\)，余弦为 0，该项消失。
    3. 于是结果 \(=\dfrac14\cdot 2^n\)，恰为全部子集数 \(2^n\) 的四分之一。

17. 求下列表达式的闭合公式（closed formula）： \[\sum_{k=0}^{n}\binom{n}{k}4^k(-1)^{n-k}.\]

    思路认出这就是二项式定理 \(\sum\binom{n}{k}a^k b^{n-k}=(a+b)^n\) 的形态，取 \(a=4,\ b=-1\)。
    1. \(\displaystyle\sum_{k=0}^{n}\binom{n}{k}4^k(-1)^{n-k}=(4+(-1))^n=3^n\)。
    2. 小验证 \(n=1\)：\(\binom10(-1)+\binom11\cdot4=-1+4=3=3^1\)。

18. 一位篮球迷瞄了一眼报纸，看了他喜爱球队所在分区（共 7 支队）的排名。后来他想回忆完整排名，但记不全。他记得：湖人（Lakers）排第 1，超音速（Sonics）排第 5；此外国王（Kings）排在开拓者（Trailblazers）前面，而开拓者又排在快船（Clippers）前面。这给完整排名留下了多少种可能？

    思路固定两支队的名次后，剩下 5 支队排进剩下 5 个位置；其中 3 支队（国王、开拓者、快船）有固定的先后顺序，用除法处理。
    1. 湖人占第 1、超音速占第 5：固定。剩下名次 2、3、4、6、7 共 5 个位置给剩 5 支队。
    2. 5 支队全排列 \(5!=120\) 种。
    3. 其中“国王 < 开拓者 < 快船”这一指定顺序只占 \(3!\) 种排法中的 1 种，故除以 \(3!=6\)。
    4. 答案 \(=\dfrac{5!}{3!}=\dfrac{120}{6}=20\)。

19. 上一题的篮球迷又试图回忆另一个 7 支队分区的排名，细节仍记不全。他只记得：火箭（Rockets）和灰熊（Grizzlies）名次相邻（但忘了谁前谁后），且掘金（Nuggets）排在马刺（Spurs）后面。这给完整排名留下多少种可能？

    思路“相邻”用捆绑法，“某队在另一队之后”用除以 2 的对称性。
    1. 把火箭、灰熊捆成一个整体（内部顺序 2 种），与其余 5 队共 6 个对象排列：\(6!\cdot2=1440\) 种。
    2. 这 1440 种里，掘金在马刺之前、之后各占一半，故满足“掘金在马刺之后”的有 \(1440/2=720\) 种。

20. 重新考虑例 1.43，这次要把比赛主客场也算进去。即：魔术队（Magic）与本分区每支队打的四场，两场主场两场客场；与另一个联盟每支队打的两场，一主一客；最后，魔术可以从剩下的对手中选 5 支，对这 5 支打两主一客，对剩下的 4 支打两客一主。魔术队共有多少种不同的赛程？

    思路把“例 1.43 的纯赛程数”当作一个固定基数，再乘上各类比赛主客场分配的方式数；唯一需要计数的自由度是“从剩 9 支对手里挑 5 支享受两主一客”。
    1. 本分区与跨联盟各队的主客场是规定死的，不产生选择。
    2. 剩下 9 支对手中选 5 支“两主一客”：\(\binom{9}{5}\) 种；另 4 支自动“两客一主”。
    3. 把这个 \(\binom{9}{5}\) 乘到例 1.43 已算出的赛程总数上即可。

21. 从 \([n]\) 中选取两个子集 \(S\) 和 \(T\)，若对这两个子集不加任何条件，共有多少种方法？

    思路\(S,T\) 各自独立地是 \([n]\) 的任意子集，每个有 \(2^n\) 种，乘法原理。
    1. 子集个数 \(=2^n\)（每个元素“在/不在”二选一）。
    2. \(S\)、\(T\) 独立：\(2^n\cdot2^n=4^n\)。

22. (a) 从 \([n]\) 中选子集 \(S\) 与 \(T\)，使得 \(S\) 包含 \(T\)（即 \(T\subseteq S\)），有多少种方法？
    (b) 从 \([n]\) 中选不相交的子集 \(R\) 与 \(U\)，有多少种方法？

    思路逐元素决定“归属”，每个元素的可选状态数相乘。
    1. (a) 每个元素有三种状态：在 \(T\)（从而也在 \(S\)）、只在 \(S\)、都不在。故 \(3^n\)。
    2. (b) \(R,U\) 不相交，每个元素三种状态：在 \(R\)、在 \(U\)、都不在。故 \(3^n\)。

23. 要把 \(2n\) 名网球选手两两配成 \(n\) 对，打 \(n\) 场比赛。共有多少种配对方法？

    思路这是“完美匹配”计数。两种等价算法：逐次取人配对，或用阶乘除以重复。
    1. 取出标号最小的人，他的对手有 \(2n-1\) 种选法；再取剩下里最小的，对手 \(2n-3\) 种……
    2. 得 \((2n-1)(2n-3)\cdots3\cdot1=(2n-1)!!=\dfrac{(2n)!}{2^n\,n!}\)。
    3. 验证 \(n=2\)（4 人）：\(3\) 种，公式 \(\dfrac{4!}{4\cdot2}=3\)，吻合。

24. 设 \(r>e\)。证明对一切 \(n\ge1\) 有不等式 \[n!>\left(\frac{n}{r}\right)^n.\] 不要使用斯特林公式（Stirling's formula）。可以利用微积分中学过的事实：数列 \(a_n=\left(\dfrac{n}{n+1}\right)^n\) 单调递减且收敛到 \(1/e\)。

    思路（数学归纳法）对 \(n\) 归纳；归纳步里用提示数列把 \((n+1)!\) 与 \(\big(\frac{n+1}{r}\big)^{n+1}\) 比较。
    1. 基础 \(n=1\)：\(1!=1>1/r\)（因 \(r>e>1\)）。
    2. 归纳假设 \(n!>(n/r)^n\)。乘以 \((n+1)\)：\((n+1)!>(n+1)(n/r)^n\)。
    3. 欲证 \((n+1)(n/r)^n\ge\big(\frac{n+1}{r}\big)^{n+1}\)，整理为 \(r\ge\big(\frac{n+1}{n}\big)^n=1/a_n\)。由 \(a_n\downarrow1/e\) 知 \(1/a_n\uparrow e

25. (+) 求卡塔兰数（Catalan numbers）\(c_n\) 的显式公式。\(c_n\)（在例 1.34 之后）定义如下，按以下步骤完成：

    (a) 注意由减法原理，\(c_n\) 等于：从 \((0,0)\) 到 \((n,n)\) 的全部东北向格路（northeastern lattice paths）的数目 \(a_n\)，减去其中在某处越过主对角线上方的格路数目 \(b_n\)。请先求出 \(a_n\) 的显式公式。

    (b) 在 \(b_n\) 所计的格路集合 \(S\) 与“从 \((-1,1)\) 到 \((n,n)\) 的全部东北向格路”集合 \(T\) 之间建立一个双射。

    (c) 求 \(|T|\) 的公式，并应用减法原理。

    思路（反射原理 reflection）这是卡塔兰数的经典推导：好路 = 全部路 − 坏路，坏路通过“关于直线反射”与另一端点的全部路一一对应。
    1. (a) \(a_n=\binom{2n}{n}\)（\(2n\) 步里选 \(n\) 步向右）。
    2. (b) 坏路必首次触到对角线上方的某直线；把首触点之前的部分关于该直线反射，起点 \((0,0)\) 变为 \((-1,1)\)，得到 \(T\) 中的路，且可逆，是双射。
    3. (c) \(|T|=\binom{2n}{n-1}\)。于是 \(c_n=\binom{2n}{n}-\binom{2n}{n-1}=\dfrac{1}{n+1}\binom{2n}{n}\)。

26. (+) 设 \(k\) 为正整数。设 \((a,b)\) 是第一象限内位于直线 \(x=ky\) 上或其下方的一点。证明：从 \((0,0)\) 到 \((a,b)\) 且除起点外不接触直线 \(x=ky\) 的东北向格路数目为 \[\frac{a-kb}{a+b}\binom{a+b}{a}.\]

    思路（推广的循环引理 / 反射）这是上一题反射原理的推广（“循环移位法 cycle lemma”给出比例因子 \(\frac{a-kb}{a+b}\)）。
    1. 从 \((0,0)\) 到 \((a,b)\) 的全部格路有 \(\binom{a+b}{a}\) 条。
    2. 用反射/循环引理证明：不接触直线的路恰占比例 \(\dfrac{a-kb}{a+b}\)。
    3. 两者相乘得所求。可取 \(k=1,(a,b)=(n,n)\) 退化为上题的卡塔兰数验证。

27. 求下列表达式的闭合公式： \[\sum_{k=1}^{n}\frac{k}{n^{k}}\binom{n}{k}.\]

    思路用恒等式 \(k\binom{n}{k}=n\binom{n-1}{k-1}\) 降阶，再凑成二项式展开。
    1. \(k\binom{n}{k}=n\binom{n-1}{k-1}\)，于是和 \(=\displaystyle\sum_{k=1}^{n}\frac{n}{n^k}\binom{n-1}{k-1}=\frac{1}{n}\sum_{j=0}^{n-1}\binom{n-1}{j}\frac{1}{n^{j}}\)（令 \(j=k-1\)）。
    2. 由二项式定理 \(\sum_j\binom{n-1}{j}n^{-j}=(1+\tfrac1n)^{n-1}=\big(\tfrac{n+1}{n}\big)^{n-1}\)。
    3. 故原式 \(=\dfrac{(n+1)^{\,n-1}}{n^{\,n}}\)。

28. (+) 证明恒等式 \[n=\sum_{k=1}^{n}\frac{k}{n^{k}}\binom{n+1}{k+1}.\]

    思路与上题同源，仍用 \(\binom{n+1}{k+1}\) 的吸收恒等式把 \(k\) 吸收掉，凑出 \((1+1/n)\) 的幂，再求和化简。
    1. 利用 \((k+1)\binom{n+1}{k+1}=(n+1)\binom{n}{k}\) 及 \(k=(k+1)-1\) 拆项。
    2. 把和化成两个二项式型求和（一个对应 \((1+1/n)^{n}\) 类，另一个可裂项）。
    3. 化简后正好得到 \(n\)；可先用 \(n=2\) 数值核对再写一般证明。

29. 一场网球锦标赛有 85 名参赛者。输一场的选手立即被淘汰，赢的选手继续打。组织者有很多选择：可以给一些选手第一轮轮空（bye），使第一轮后正好剩 \(2^6=64\) 人，此后不再需要轮空；也可以给最强的选手第二轮轮空，甚至给极强者第三轮轮空。若组织者想用尽可能少的比赛场数选出冠军，最佳策略是什么？

    思路（淘汰赛关键洞察）每场比赛恰好淘汰一人；要决出唯一冠军，必须淘汰其余所有人。
    1. 85 人中要淘汰 \(85-1=84\) 人，每场淘汰 1 人。
    2. 所以无论怎样安排轮空，都恰好需要 \(84\) 场比赛——场数与策略无关。
    3. 这正是“一一对应：每场比赛 ↔ 一个被淘汰者”的双射思想。

30. 16 名选手参加单循环（round-robin）网球赛，每两人都比赛一场。已知每人的胜场数各不相同。问最终排名第 6 的选手赢了多少场？

    思路每人胜场数互不相同，且取值范围在 \(0\) 到 \(15\)（每人打 15 场）。16 个互不相同的数恰好填满 \(0,1,\dots,15\)。
    1. 总场数 \(\binom{16}{2}=120\)，恰等于 \(0+1+\cdots+15=120\)，说明胜场数恰为 \(0,1,\dots,15\) 的一个排列。
    2. 第 1 名胜 15 场，第 2 名胜 14 场……第 \(r\) 名胜 \(16-r\) 场。
    3. 第 6 名胜 \(16-6=10\) 场。

31. 设 \(A_1,A_2,\dots,A_k\) 是有限集合，不必两两不相交。证明 \[|A_1\cup A_2\cup\cdots\cup A_k|\le|A_1|+|A_2|+\cdots+|A_k|.\]

    思路右边把交叠部分的元素重复计了数，左边每个元素只算一次，故左 ≤ 右。可对 \(k\) 归纳。
    1. 对每个 \(x\in A_1\cup\cdots\cup A_k\)，它在右边至少被计一次（落在某个 \(A_i\)）。
    2. 左边对它恰计一次，故右边计数 \(\ge\) 左边计数。
    3. 形式化：用 \(|A\cup B|=|A|+|B|-|A\cap B|\le|A|+|B|\) 起步，再归纳。

32. 证明：即使不假设集合 \(A_1,A_2,\dots,A_k\) 两两不相交，鸽笼原理（pigeonhole principle）仍然成立。

    思路结合上一题的不等式：若每个 \(|A_i|\) 都太小，则并集也小，与“元素总数固定”矛盾，即用反证法。
    1. 反设每个 \(A_i\) 的元素都不超过某上界 \(b\)。
    2. 由上题 \(\big|\bigcup A_i\big|\le\sum|A_i|\le kb\)。
    3. 若总元素数 \(>kb\)，则与上式矛盾，故必有某 \(A_i\) 的元素数超过 \(b\)，即鸽笼原理成立。

33. (+) 平面上所有整点（坐标为整数的点）被染成红、蓝、绿三色之一。证明：必存在一个四个顶点同色的矩形。

    思路（两层鸽笼）先在一列里靠鸽笼找到两个同色点，再在很多列里靠鸽笼找到“同色对的模式”重复的两列。
    1. 取一列 \(x=0\) 上 4 个整点：3 种颜色染 4 点，必有两点同色（鸽笼）。
    2. 每一列用前几个点（比如纵坐标 \(1,\dots,N\)）记录“哪两行同色 + 什么颜色”这一“模式”；模式种类有限。
    3. 取足够多列，必有两列模式相同 → 这两列上对应的同色两行，构成 4 个同色顶点的矩形。

34. 一个计算机程序随机生成了 175 个正整数，其中没有任何一个含有大于 10 的素因子。证明：总能从中找到三个数，它们的乘积是某个整数的立方。

    思路（指数模 3 + 鸽笼 + 选 3 个）每个数都形如 \(2^a3^b5^c7^d\)；把每个指数模 3 看作四元向量，向量种类有限。
    1. 小于等于 10 的素数只有 \(2,3,5,7\) 四个，故每个数对应一个“指数模 3”向量 \((a,b,c,d)\bmod3\)，共 \(3^4=81\) 种。
    2. 175 个数里，两个向量相同的两数相乘，其每个指数和 \(\equiv\) 偶数倍但还不一定是 3 的倍数；更稳的做法：先两两配对凑出“乘积为平方”的数，再在这些平方数里用 \(2^4=16\) 种奇偶向量配对——逐层用鸽笼制造立方。
    3. 核心是：足够多的数（\(175>2\cdot81\)）保证能挑出三个，使每个素数的总指数都被 3 整除，从而乘积是立方数。

---

返回 全书目录