【附】為便于有需要者編輯修改，特提供純文本文檔如下：

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。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!