集合的分划

观察

$n = 4$ ：把 $1, 2, 3, 4$ 分成两类，让每一类里都没有 $x, y, x + y$ （ $x = y$ 也算，比如 $1, 1, 2$ ）。成功了吗？
把 $n$ 调到 $5$ ，再试。试了几次都不行，点“问问电脑”。
读一读下面的“加法原理”读数：不管怎么涂，各类个数之和是多少？
一共有几种成功的涂法？把两种颜色对调算不算新的分法？

把集合 $M$ 写成非空子集 $A_{1}, A_{2}, \dots, A_{n}$ 的并，并且它们两两不交：

A_{i} \cap A_{j} = \emptyset (i \neq = j), A_{1} \cup A_{2} \cup \dots \cup A_{n} = M,

就说 ${A_{1}, \dots, A_{n}}$ 是 $M$ 的一个 $n$ -分划。最直接的推论是加法原理： $∣ M ∣ = ∣ A_{1} ∣ + ∣ A_{2} ∣ + \dots + ∣ A_{n} ∣$ 。

把分划想成涂色最方便：同一块涂同一种颜色。“能不能按要求分划”就变成“能不能按要求涂色”。

先猜后证

把 ${1, 2, 3, 4}$ 分成两块（两块不分先后，每块非空），一共有几种分法？

种

先选定答案，才能看到结论。

第 1 / 5 步

“不妨设”和“被迫”是这类证明的两个关键词：对称性让我们少讨论一半，每一步只剩一种选择，所以几步就走到头。 ${1, 2, 3, 4}$ 却能分： ${1, 4}$ 和 ${2, 3}$ 。 $4$ 和 $5$ 之间，就是“能”与“不能”的分界。

现在要求分成 $3$ 块，每块的元素和相等。先别动手，想一想：总和 $1 + 2 + \dots + n$ 必须满足什么？

n = 8

时总和是

36

，每块该是多少？把

n

调到

7

，再点“问问电脑”。

总和能被 $3$ 整除是必要的；有了它还不够—— $n = 3$ 时总和 $6$ ，每块要是 $2$ ，可 $3$ 自己就超了。必要条件筛掉一大批，剩下的再靠构造一个一个落实。

练习 1基础

把 ${1, 2, 3, 4, 5}$ 分成两块（不分先后，每块非空），有多少种分法？

练习 2基础

$n$ 取 $1, 2, \dots, 10$ 中的哪些值时， ${1, 2, \dots, n}$ 能分成两块，使两块的元素和相等？（用逗号隔开写出所有的 $n$ 。）

练习 3提高

把 ${1, 2, 3, 4, 5}$ 分成三块（不分先后，每块非空），有多少种分法？

练习 4挑战

$n$ 取 $1, 2, \dots, 12$ 中的哪些值时， ${1, 2, \dots, n}$ 能分成三块，使三块的元素和都相等？