【附】为便于有需要者编辑修改,特提供纯文本文档如下:
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。