数学课堂
挑战≈ 15 分钟未开始

构造法

核心概念

构造法:为了证明"存在满足某条件的对象",直接造出一个具体例子;或为了说明某个界限"能达到",给出达到它的具体方案。

两类常见任务:

  • 证存在 / 可行:给出一个具体构造(往往要附上验证);
  • 求最优值:分两步——① 用不等式 / 反证 证明"不可能更好"(给出界);② 构造一个达到该界的例子(说明界可达)。

口诀:存在性靠构造,不可能靠论证。能造出来就证明了存在,造不出来不代表不存在,要另用论证。

直观理解 · 动手试试

很多竞赛题问"最多能怎样 / 最少需要多少 / 是否存在",答案往往是一个具体的数或方案。这类问题的完整解答通常是"两头夹":

  • 一头用反证或不等式说明"不会超过 NN"(上界);
  • 另一头用构造给出"NN 确实能实现"的例子(下界 / 可达)。

只有当"界"和"构造"对上了,才算真正求出了最优值。平时训练时要养成习惯:证完一个界,立刻问自己"这个界取得到吗?给个例子。"构造能力,是把"理论上界"变成"确切答案"的关键。

构造法

8×8 棋盘放互不攻击的车

♜♜♜♜♜♜♜♜
上界:每行最多 1 个,共 8 行 → 至多 8 个。
构造:沿对角线放置,每行每列恰好一个,互不攻击 → 达到 8 个。
两者吻合,最多 8 个。
8×8

求最优值要「两头夹」:先证不超过 n(上界),再构造对角线方案达到 n(可达),答案才确定为 n。

例题 1构造达到上界的例子

要在 8×88\times8 棋盘上放尽量多的"车",使它们两两不互相攻击(同行同列只能有一个)。最多能放几个?

▸查看解答步骤

答: 构造 + 论证两步

例题 2构造存在性例子

是否存在 55 个连续正整数,都不是质数?

▸查看解答步骤

答: 给出具体数列

即时练习

8×88\times8 棋盘上两两不攻击的车最多能放几个?

每行至多 11 个,共 88 行;对角线放置可达 88 个。

证明"存在满足条件的对象",最直接的方法是?

构造一个具体例子用反证法说明不可能染色证明不变量求最大公约数

存在性最直接的证法就是给出一个满足条件的具体构造。

    求最优值通常需要"证上界 + 构造达到上界的例子"两步。

    界说明不可能更好,构造说明界可达,两者吻合才确定最优值。

    存在 100100 个连续的正整数,它们全都是合数。

    取 101!+2,…,101!+101101!+2,\dots,101!+101,第 kk 个能被 kk 整除,全为合数。

    易错点

    • 只证界不给构造。 证明了"不超过 NN"还不够,必须构造达到 NN 的例子才算求出最优。
    • 构造后不验证。 造出例子要逐条验证它确实满足所有条件。
    • 用构造去证"不存在"。 造不出来不等于不存在;否定性结论要靠论证(反证、不变量等)。

    下一步

    前置知识点
    —