第 9 章　把它造出来

第六件工具，跟第 6 章的不变量恰好是一对反义词。不变量擅长证"办不到"；这一章的构造法，专管证"办得到"。

很多题问你"是否存在满足某条件的东西"——存在这样的数列吗？能这样染色吗？有这种排法吗？要回答"存在"，最实在、最无可辩驳的办法只有一个：把它亲手造出来，摆在桌上给人看。 你造出一个，“存在"就板上钉钉，再不用多说一句。

构造法的难，不在道理，在手艺：你得真的设计出那个东西。 这考的是巧思，但巧思也有套路——往下看。

一、要多少个，就给你造多少个

例 9.1（☼☼☼，连续合数）证明：无论你要多少个，都能找到那么多个连续的合数（合数 = 不是质数的、大于 1 的整数）。比如要 100 个挨在一起、中间没有任何质数的整数。

质数越往后越稀，但谁能保证中间能空出任意长的一段？光说"应该可以"不算数，造给你看。

想要 $n$ 个连续合数，就盯住阶乘 $(n+1)!=1\cdot2\cdot3\cdots(n+1)$，然后取这一串：

$$(n+1)!+2,\quad (n+1)!+3,\quad \dots,\quad (n+1)!+(n+1).$$

这正好是 $n$ 个连续的整数。逐个看它们为什么都是合数：对其中第 $k$ 个（$2\le k\le n+1$），因为 $k$ 是 $(n+1)!$ 的一个因子，所以 $k$ 既整除 $(n+1)!$，又整除自己 $k$，于是

$$k \ \big|\ (n+1)!+k.$$

也就是说 $(n+1)!+k$ 有一个真因子 $k$（且这数远大于 $k$），它是合数。$n$ 个全是合数，且连续。就这样。

要 100 个，就用 $101!$ 起头；要一百万个，就用 $1000001!$ 起头。构造法的痛快之处在于：它不只回答"存在”，还能按你点的数量当场交货。

有时候你造不出"具体那一个"，但能借第 4 章的抽屉原理，证明"它必然存在"，再顺手把它的样子认出来。这是构造与抽屉的合体，很常见。

例 9.2（☼☼☼）证明：对任意正整数 $n$，都存在一个 $n$ 的倍数，它的十进制写法里只有 0 和 1 两种数字（比如 110、1011000 这样）。

只用 0 和 1 拼出来的数，最朴素的是这一串：

$$1,\ 11,\ 111,\ \dots,\ \underbrace{11\cdots1}_{n+1\ \text{个}1}.$$

我一口气写出 $n+1$ 个这样的数（全是 1 拼的）。它们除以 $n$，余数只可能是 $0,1,2,\dots,n-1$ 这 $n$ 种——余数是 $n$ 个笼子，这 $n+1$ 个数是鸽子，必有两个数除以 $n$ 余数相同。

设这两个数是 $\underbrace{1\cdots1}_{a\text{个}}$ 和 $\underbrace{1\cdots1}_{b\text{个}}$（$a>b$），它们余数相同，差就能被 $n$ 整除。而它俩的差，恰好是

$$\underbrace{1\cdots1}_{a-b\,\text{个}}\underbrace{0\cdots0}_{b\,\text{个}},$$

即"几个 1 后面跟几个 0"——只含 0 和 1。这个差就是要找的那个 $n$ 的倍数。就这样。

这道题示范了构造法的高阶玩法：你未必能直接写出答案，但可以用抽屉原理逼出"必有两个东西相同"，再让它们的差（或和、或某种组合）正好就是你要构造的对象。

构造题最让人没底，因为它要你"无中生有"。但无中生有也有几条常走的路，卡住时挨个试：

上手清单
题目问"是否存在 / 能不能 / 是否可以"？→ 这是构造法的主场，目标是造一个出来。
造不出具体的，就用抽屉原理逼出"必有重复"，取它们的差/组合。
多条件 → 先满足最苛刻的；要数量 → 用阶乘打底批量生产。
收尾：把"我造的东西满足每一条要求"逐条验给人看。

（回头对照第 6 章：判断"能不能变到目标"，证不能用不变量，证能就靠这一章把路构造出来。两章是一体两面。）

这一章要带走的东西：

就这样。