构造相似三角形求最值（组合构造第1章容易求值5）

【附】为便于有需要者编辑修改，特提供纯文本文档如下：

3、极端状态

所谓极端状态，是指组成对象的各个元素处于一种极端分布。比如，大多数元素都聚集在某处，各元素都处于某区域的边界，一部分元素的取值相对很大而另一部分元素的取值又相对很小等等。极端状态，通常能使某种操作易于进行或某种状态易于实现。

例8、在n×n棋盘中（n≥3），将某r个方格染红色，其余方格染白色。规定：如果某个白格至少两个红格相邻（具有公共边），则将此格染红色。如果还有这样的白格则染色继续进行。若不论怎样选取最初哪r个格染红色，都不能通过上述操作使棋盘中所有格都染红色，求r的最大值。

分析与解：取有公共边界的两个方格染红色，若不借助其他的红格，还不能按其规则使某个白格染红色。而若取其对角上有公共点的两个方格染红色，则不借助其他的红格，还可按其规则使2个白格染红色。由此可见，如果红色的格是对角分布，则易于使棋盘中的白格按其规则染红色。这样便得到构造，取位于棋盘对角线上的n个格染红色，则按其规则，可使棋盘中所有格染红色，于是r≤n-1。

当r=n-1时，我们证明：不论怎样选取最初哪r个格染红色，都不能按规则使棋盘中所有格都染红色。我们给出两个证法。

证法1：考察红色区域的边界，最初的n–1个红色方格形成的红色区域边界的总长不大于4n–4。每新染一个红色格，此格在染色前至少有两条红色边，这两条边为红色区域的边界。此格染红后，最多增加两条红色边，但原来两条红色边不再在红色区域的边界上，所以红色区域边界上红色边的总长度不增。注意到所有格都染红色后红色区域边界的总长度为4n，故目标状态不能实现。

证法2：若方格A受红色方格B的影响而被染红，则将A，B的中心连线段。这样的线段连接的是两个相邻格，每一行（列）的格至多连n–1条线段，所以线段的条数至多为2n（n–1）。而某格染红至少占用2条线段，所以至多·2n（n–1）=n（n–1）个格受影响而被染红。要使棋盘全染红，最初至少染红n2–n（n–1）=n>n-1个方格。

综上所述，r的最大值是n–1。

例9、用S（A）表示集合A中所有元素之和，设X={a1，a2，… ，a11}，其中a1<a2<…<a11为自然数。若对任何自然数n≤1500，存在X的子集A，使S（A）=n。求满足上述要求的a10的最小值。

分析与解：为了求a10的最小值，由a10=S10-S9，需要找到常数a、b，使S10≥a，S9≤b。于是考察：Sk=a1 a2 … ak （k=1，2，… ，11），由于存在S（A）=1500，所以S（X）≥S（A）=1500，即S11≥1500。又S1<S2<…<S11，所以必存在m，使 Sm-1<1500≤Sm。

对k=2，3，… ，m，考察数Sk-1 1，由上面讨论可知，它不大于1500，于是必存在集合A，使S（A）=Sk-1 1。但S（{a1，a2，… ，ak-1}）=Sk-1，所以ak≤Sk-1 1（k=2，… ，m）……（1）

否则，S（{ak}）>Sk-1 1，S（{a1，a2，… ，ak-1}）<Sk-1 1。注意到{a1，a2，… ，ak-1}与{ak}之间不存在子集，对于集合P，若P不含ak，ak 1，… ，a11中的任何一个数，则S（P）≥S（{ak}）>Sk-1 1，所以不存在A，使S（A）=Sk-1 1，矛盾。

由（1），有 Sk=Sk-1 ak≤2Sk-1 1……（2）

注意到存在S（A）=1，所以a1=1，由（2）迭代，得

Sk 1≤2（Sk-1 1）≤22（Sk-2 1）≤…≤2k-1（S1 1）=2k ……（3）

特别地，有Sm≤2m-1，所以，2m-1≥Sm≥1500，m≥11。

但｜X｜=11，有m≤11，所以，m=11。由此可知，（2），（3）对k=2，3，… ，11都成立。

由（2），有Sk 1≤2Sk 1，所以（Sk 1-1）≤Sk。又Sk为自然数，所以Sk≥[Sk 1]。特别地，有S10≥[S11]≥[]=7500。

所以a10=S10-S9≥750-511=239（S9≤29-1=511）。

此估计太粗糙，无法使a10=239。利用起点后移，进行修正，有

a9 a10=S10-S8≥750-（28-1）=495。所以495≤a9 a10<2a10，a 10>247，a10≥248。

最后，构造合乎条件的集合X={a1，a2，… ，a11}，使a10=248。注意到一个数n能用X中的若干项的和表示，与二进制的特征相近，于是可取1，2，4，8，16，32，64，128，256，…，但此时不包含248，应去掉256，补上248（这里采用了局部调整构造法，见第8章），此时248排列在第9项，还要在128与248之间补充一个数。

由二进制数的性质可知，用1，2，4，8，16，32，64，128可表出1~255中的所有数，于是，可补充一个小于255的尽可能大的数（一种极端情形），则表出的数将尽可能多，于是补充247。

注意到1~255中的所有数与247相加后得到248~502中的所有数，于是，1，2，4，8，16，32，64，128，247可表出1~502中的所有数。类似可知，1，2，4，8，16，32，64，128，247，248可表出1~750中的所有数，最后补充一个数750，则1，2，4，8，16，32，64，128，247，248，750可表出1~1500中的所有数。

综上所述，集合X合乎条件。故a10的最大值为248。