第13讲 构造与论证 学生版 - 图文

第十三讲

构造与论证

教学目标

1. 掌握最佳安排和选择方案的组合问题. 2. 利用基本染色去解决相关图论问题．

知识点拨

各种探讨给定要求能否实现，在论证中，有时需进行分类讨论，有时则要着眼于极端情形，或从整体把握．设计最佳安排和选择方案的组合问题，这里的最佳通常指某个量达到最大或最小．解题时，既要构造出取得最值的具体实例，又要对此方案的最优性进行论证．论证中的常用手段包括抽屉原则、整除性分析和不等式估计．

组合证明题，在论证中，有时需进行分类讨论，有时则需要着眼于极端情况，或从整体把握。若干点及连接它们的一些线段组成图，与此相关的题目称为图论问题。若干点及连接它们的一些线段组成图，与此相关的题目称为图论问题，这里宜从特殊的点或线着手进行分析．各种以染色为内容，或通过染色求解的组合问题，基本的染色方式有相间染色与条形染色．

例题精讲

模块一 最佳安排和选择方案

1

例题1

2

例题2

3

例题3

一个盒子里有400枚棋子，其中黑色和白色的棋子各200枚．下面我们对这些棋子做如下操作：每次拿出2枚棋子，如果颜色相同，就补1枚黑色棋子回去；如果颜色不同，就补1枚白色的棋子回去．这样的操作，实际上就是每次都少了1枚棋子，那么，经过399次操作后，最后剩下的棋子是 颜色(填“黑”或者“白”)． 5卷本百科全书按从第1卷到第5卷的递增序号排列，今要将它们变为反序排列，即从第 5卷到第1卷．如果每次只能调换相邻的两卷，那么最少要调换多少次? 有3堆小石子，每次允许进行如下操作：从每堆中取走同样数目的小石子，或是将其中的某一石子数是偶数的堆中的一半石子移入另外的一堆．开始时，第一堆有1989 块石子，第二堆有989块石子，第三堆有89块石子．问能否做到：、 (1)某2堆石子全部取光? (2)3堆中的所有石子都被取走?