一、加法法则与乘法法则

1. 加法法则 The Sum Rule

• 适用场景：当任务可分解为 互斥 的若干子任务时（即完成方式之间无重叠）
• 规则：若任务有 $k$ 种互斥的完成方式，分别有 $n_1,n_2,…,n_k$ 种方法，则总方法数为各方法数之和： $n_1+n_2+…+n_k$
• **使用集合进行描述：**若 $A_1,A_2,…,A_m$ 是不相交集，那么集合中元素个数满足： $|A_1\cup A_2\cup…\cup A_m|=|A_1|+|A_2|+…+|A_m|$

示例：从北京到上海可选高铁（5 班次）或飞机（3 班次），共有 5+3=8 种出行方式

2. 乘法法则 The Product Rule

• 适用场景：当任务需 连续完成多个独立步骤 时（每一步的选择不影响其他步骤）
• 规则：若任务分 $k$ 个独立步骤，第 $i$ 步有 $n_i$ 种方法，则总方法数为各步骤方法数之积： $n_1\times n_2\times …\times n_k$
• **使用集合进行描述：**若 $A_1,A_2,…,A_m$ 是有限集，那么集合中元素个数满足： $|A_1\times A_2\times…\times A_m|=|A_1|·|A_2|·…·|A_m|$ （等式左侧为笛卡尔乘积）

示例：选一件衬衫（3 款）和一条裤子（4 款），共有 3×4=12 种搭配

示例：

示例：

示例：

二、鸽巢原理

1. 鸽巢原理 Pigeonhole Principle

1. **基本：**若 $k+1$ 或更多物体被放到 $k$ 个箱子中，则至少有一个箱子有至少 2 个物体

2. **广义：**若 $N$ 个物体被放到 $k$ 个箱子中，则至少有一个箱子有至少 $\lceil N/k\rceil$ 个物体

   **示例：**367 个人必定有至少两人生日相同

3. **定理：**任意不超过 $2n$ 的 $n+1$ 个正整数中，必有一个整数能整除另一个整数

   证明：

   • 把 $n+1$ 个整数 $a_1,a_2,…,a_{n+1}$ 表示为 2 的指数次幂与一个奇数的乘积

     $a_j=2^k\times q_j\ |\ k\in Z^+\land (q_j\ is\ odd)$

     （ $k$ 可为 0，因此所有整数都可按此方法表示）

   • 不超过 $2n$ 的奇数只有 $n$ 个，而在上式中定义的 $q_j$ 有 $n+1$ 个，因此至少有两个整数 $a_i$ 和 $a_j$ 对应的奇数相同，即 $q_i=q_j=q$

   • 设这两个数的分解形式为： $a_i=2^{k_i}q_i,\ a_j=2^{k_j}q_j$

   • 若 $k_i<k_j$，则 $a_i=2^{k_i}⋅q$ 能整除 $a_j=2^{k_j}⋅q$ ，因为 $a_i/a_k=2^{k_i-k_j}$；若 $k_i≥k_j$ 则同理