【附】為便于有需要者編輯修改,特提供純文本文檔如下:
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每日頭條,我们将持续为您更新最新资讯!