第一章 什么是组合数学

棋盘完美覆盖

$\displaystyle{ m \times n }$ 棋盘，使用 $\displaystyle{ 1 \times b }$ 大小的条形牌进行覆盖，能够完美覆盖的充要条件是 $\displaystyle{ b }$ 是 $\displaystyle{ m }$ 或 $\displaystyle{ n }$ 的因子。

• 当 $\displaystyle{ b }$ 是素数时，成立
• 当 $\displaystyle{ b }$ 不是素数时，令 $\displaystyle{ m = p b + r , n = q b + s }$，其中 $\displaystyle{ 0 \leqslant r < b , 0 \leqslant s < b }$
  • 不妨设 $\displaystyle{ r < s }$，证明 $\displaystyle{ r = 0 }$ 即可
  • 使用 $\displaystyle{ b }$ 种颜色对棋盘着色，每种颜色格子数应当相同
  • 将棋盘分为三个部分
    • 上方 $\displaystyle{ p b \times n }$ 每种颜色格子数相同
    • 左下方 $\displaystyle{ r \times q b }$ 每种颜色格子数相同
    • 右下方 $\displaystyle{ r \times s }$ 若需要完美覆盖，则需要每种颜色格子相同

$\displaystyle{ 4 \times 4 }$ 的棋盘用 8 张 $\displaystyle{ 2 \times 1 }$ 的牌覆盖，总存在：把这个棋盘横着切成非空的两块或竖着切成非空的两块，而不切断牌中任意一张。

反证法？？

• 设 $\displaystyle{ x _{ 1 } , x _{ 2 } , x _{ 3 } }$ 是被水平切割线切到的牌数量
• $\displaystyle{ x _{ 1 } + x _{ 2 } + x _{ 3 } }$ 是竖着摆放的牌的数量
  • $\displaystyle{ x _{ 1 } , x _{ 2 } , x _{ 3 } > 0 }$，且都是偶数，则和大于等于 6

相互重叠的圆

平面上以普通位置相互重叠的 $\displaystyle{ n }$ 个圆

• 相互重叠：每对圆相交于两个点
• 普通位置：不存在有一个公共点的三个圆

$$\displaystyle{ \begin{aligned}h _{ 1 } & = 2 \\ h _{ 2 } & = 4 \\ h _{ 3 } & = 8 \\ h _{ n } & = h _{ n - 1 } + 2 \left( n - 1 \right) = n ^{ 2 } - n + 2\end{aligned} }$$

Nim 游戏

$\displaystyle{ k }$ 堆硬币，两个玩家按顺序依次从任意一堆中取出若干个硬币，当一个玩家取出所有硬币，则该玩家获胜。

将每堆硬币表示为 2 的幂的和

	$\displaystyle{ 2 ^{ 3 } }$	$\displaystyle{ 2 ^{ 2 } }$	$\displaystyle{ 2 ^{ 1 } }$	$\displaystyle{ 2 ^{ 0 } }$
7	0	1	1	1
9	1	0	0	1
12	1	1	0	0
9	1	0	0	1
按列求和	3	2	1	3

若按列求和不全为偶数，则不平衡；若按列求和全为偶数，则平衡。想要获胜的玩家，需要在一定步骤内，保证游戏的平衡。