Skip to content

第一章 什么是组合数学

棋盘完美覆盖

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

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

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

反证法??

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

相互重叠的圆

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

  • 相互重叠:每对圆相交于两个点
  • 普通位置:不存在有一个公共点的三个圆
h1=2h2=4h3=8hn=hn1+2(n1)=n2n+2\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 游戏

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

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

23\displaystyle{ 2 ^{ 3 } }22\displaystyle{ 2 ^{ 2 } }21\displaystyle{ 2 ^{ 1 } }20\displaystyle{ 2 ^{ 0 } }
70111
91001
121100
91001
按列求和3213

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