第15章 省賽第一場
此時的徐辰，確實遇到了麻煩。
【這個問題，有點棘手。】
他把陳老師給的競賽資料在腦子裡過了一遍，很確定，沒有講過這類問題的解題技巧。
陳老師的資料也是托關係從別的學校要來的，都是些常規的競賽知識點。對於安城三中大部分學生來說，已經完全夠用了，再深的東西，教了也學不會。
所以，徐辰現在只有一個大概的方向，但缺少趁手的數學工具。
他停下筆，開始思考。
【要證明存在一種「好」的著色方案，可以反過來想，證明「所有方案都不好」的概率小於1。】
【一個「不好」的方案，就是指至少有一條邊的兩個端點顏色相同。】
他想到了概率論里最基礎的工具——聯合界。
【假設A_i是第i條邊顏色相同的事件，那麼P(A_i)= 1/k。如果圖里有m條邊，所有壞事件的概率加起來就是 m/k。】
筆尖在草稿紙上劃了幾行，徐辰又停下了。
【不行。m的最大值能到 Nd/2，這樣算出來的概率和很可能會大於1。聯合界這個方法太粗糙了，行不通。】
他輕輕劃掉了剛寫的幾行字。
徐辰閉上眼睛，屏蔽了周圍的雜音，腦子裡只剩下那張由點和線構成的抽象的圖。
【這些「壞事件」A_i之間，不是完全獨立的。一條邊出問題，會影響到和它共用一個頂點的其他邊……但是，這種影響是局部的。】
「局部」！
這個詞像鑰匙一樣，打開了他腦中的一扇門。
徐辰猛地睜開眼，目光里透著一股專注。
【對，一個事件A_i，只和少數跟它「相鄰」的事件有關。一條邊，最多只和 2(d-1)條其他邊共用頂點。它的影響範圍是有限的。】
【如果能找到一個方法，精確地描述這種「有限影響」，是不是就能把那個大於1的概率和給降下來？】
他沒學過什麼洛瓦茲局部引理。
他的世界裡，沒有現成的公式可以套。
他要做的，是從最基本的概率公理出發，自己動手，搭一座通往答案的橋。
他的筆又動了。
這一次，不再是試探，而是帶著明確的方向進行推演。
他開始嘗試構建一個更精細的概率不等式。
【假設，給每個壞事件A_i，都分配一個在(0，1)之間的權重x_i。如果能證明，每個事件A_i發生的概率，都小於一個由它自己和它所有「鄰居」的權重共同決定的數值……】
這個想法很大膽，推導過程也極其複雜。
P(A_i)≤ x_i *Π_{j與i相關}(1 - x_j)
當這個不等式被他寫在草稿紙上時，他感覺自己抓住了問題的關鍵。
接下來，就是海量的計算和放縮。草稿紙一張接一張地被寫滿，上面的符號和邏輯箭頭，密密麻麻。
【計算量太大了，腦子有點跟不上了。】
徐辰看了看時間，還剩30分鐘，時間有點緊。
【對了，專注膠囊！】
他想起了系統新手任務獎勵的5顆專注膠囊。
【系統，使用專注膠囊。】
一瞬間，徐辰感覺大腦變得異常清晰和冷靜，外界的一切干擾都消失了，全部的注意力都集中在了眼前的題目上。
他的計算速度和思維效率，陡然提升。
5分鐘……
10分鐘……
15分鐘……
汗水從額頭滲出，滑過臉頰，他卻毫無察覺。
當第五張草稿紙寫滿時，那組複雜的不等式，終於被他整理成了一個簡潔而清晰的形態。
若存在x_i∈(0，1)，使得對所有i，都有 P(A_i)≤ x_i *Π_{j∈Γ(i)}(1 - x_j)成立，則 P(∩ A_i^c)＞ 0。
他利用題目給的條件 e(d+1)≤ k，巧妙地構造出了一個統一的權重 x = 1/(d+1)，並最終證明了這個不等式成立！
做出來了。
他並不知道這個引理的名字。
他只是從最基本的概率公理出發，敏銳地抓住了「局部依賴」這一核心，然後用自己恐怖的數學直覺和構建能力，硬生生地在現場，手動推導了「洛瓦茲局部引理」！
他猛地抬頭看了一眼牆上的時鐘。
只剩下……十分鐘了！
而他，才剛剛完成證明，還沒往答題卡上抄！
徐辰立刻開始謄寫。因為是從最基本的原理開始推導，他的證明過程非常長，幾乎寫滿了整個答題區。字跡因為高速書寫而略顯潦草，但每一步都邏輯清晰，無可辯駁。
終於，在距離考試結束還有三分鐘的時候，他停下了筆。
長長地舒了一口氣。
【應該……都做對了。】
【就是不知道最後這道題，過程寫得這麼複雜，會不會被扣步驟分。】
【不過，就算扣幾分，拿個省一，應該也夠了。】
……
第一場考試結束了。
第二場考試和第一場考試中間只有20分鐘的休息時間。
考場外，走廊上。
安城三中的四人，再次聚到了一起。
「唉，最後一題太難了，完全沒思路。」林曉雅一臉沮喪。
「是啊，我連題目的考點都沒看出來。」張浩也嘆了口氣。
李帆因為參加過省城的金牌輔導班，自認為是校隊裡唯一能做出來的人，故作深沉地說道：「考的是洛瓦茲局部引理。不過計算過程啊還是很複雜，我寫上了，但不知道會不會扣過程分。」
他這番話，瞬間引來了林曉雅和張浩崇拜的目光。
「李帆你太厲害了！這都能做出來！」
「看來這次省一有希望了！」
隨後，張浩看向一旁的徐辰，關心得問道。
「徐辰，你考的怎麼樣？」張浩問道「看你一直在算，我看你中途還要了好多草稿紙，應該是卡住了吧」。
徐辰說，「最後一題確實有點難，我花了快40分鐘才寫完。」
「寫完？也就是說，你做出來了？！」張浩吃驚。
李帆則是不太相信地看著他，問道：「你知道【洛瓦茲局部引理】？你不是三天前才學的數學競賽知識嘛，這個知識點算是超綱了，你怎麼會知道。」
徐辰說「我這不知道哪個什麼【洛瓦茲局部引理】，我就是用原始的方法，硬算的」，徐辰實話實說，「過程有點繁瑣，草稿紙都用了五六張。」
「噗——」
李帆像聽到了本世紀最好笑的笑話，誇張地大笑起來：「硬算？徐辰，你開什麼玩笑！那道題的計算量，你用手硬算？不可能，絕對不可能！」
徐辰看著他的模樣，只是笑了笑，沒有再解釋。
有些事情，說再多也沒用。等結果出來，自然就不得不信。
【這個問題，有點棘手。】
他把陳老師給的競賽資料在腦子裡過了一遍，很確定，沒有講過這類問題的解題技巧。
陳老師的資料也是托關係從別的學校要來的，都是些常規的競賽知識點。對於安城三中大部分學生來說，已經完全夠用了，再深的東西，教了也學不會。
所以，徐辰現在只有一個大概的方向，但缺少趁手的數學工具。
他停下筆，開始思考。
【要證明存在一種「好」的著色方案，可以反過來想，證明「所有方案都不好」的概率小於1。】
【一個「不好」的方案，就是指至少有一條邊的兩個端點顏色相同。】
他想到了概率論里最基礎的工具——聯合界。
【假設A_i是第i條邊顏色相同的事件，那麼P(A_i)= 1/k。如果圖里有m條邊，所有壞事件的概率加起來就是 m/k。】
筆尖在草稿紙上劃了幾行，徐辰又停下了。
【不行。m的最大值能到 Nd/2，這樣算出來的概率和很可能會大於1。聯合界這個方法太粗糙了，行不通。】
他輕輕劃掉了剛寫的幾行字。
徐辰閉上眼睛，屏蔽了周圍的雜音，腦子裡只剩下那張由點和線構成的抽象的圖。
【這些「壞事件」A_i之間，不是完全獨立的。一條邊出問題，會影響到和它共用一個頂點的其他邊……但是，這種影響是局部的。】
「局部」！
這個詞像鑰匙一樣，打開了他腦中的一扇門。
徐辰猛地睜開眼，目光里透著一股專注。
【對，一個事件A_i，只和少數跟它「相鄰」的事件有關。一條邊，最多只和 2(d-1)條其他邊共用頂點。它的影響範圍是有限的。】
【如果能找到一個方法，精確地描述這種「有限影響」，是不是就能把那個大於1的概率和給降下來？】
他沒學過什麼洛瓦茲局部引理。
他的世界裡，沒有現成的公式可以套。
他要做的，是從最基本的概率公理出發，自己動手，搭一座通往答案的橋。
他的筆又動了。
這一次，不再是試探，而是帶著明確的方向進行推演。
他開始嘗試構建一個更精細的概率不等式。
【假設，給每個壞事件A_i，都分配一個在(0，1)之間的權重x_i。如果能證明，每個事件A_i發生的概率，都小於一個由它自己和它所有「鄰居」的權重共同決定的數值……】
這個想法很大膽，推導過程也極其複雜。
P(A_i)≤ x_i *Π_{j與i相關}(1 - x_j)
當這個不等式被他寫在草稿紙上時，他感覺自己抓住了問題的關鍵。
接下來，就是海量的計算和放縮。草稿紙一張接一張地被寫滿，上面的符號和邏輯箭頭，密密麻麻。
【計算量太大了，腦子有點跟不上了。】
徐辰看了看時間，還剩30分鐘，時間有點緊。
【對了，專注膠囊！】
他想起了系統新手任務獎勵的5顆專注膠囊。
【系統，使用專注膠囊。】
一瞬間，徐辰感覺大腦變得異常清晰和冷靜，外界的一切干擾都消失了，全部的注意力都集中在了眼前的題目上。
他的計算速度和思維效率，陡然提升。
5分鐘……
10分鐘……
15分鐘……
汗水從額頭滲出，滑過臉頰，他卻毫無察覺。
當第五張草稿紙寫滿時，那組複雜的不等式，終於被他整理成了一個簡潔而清晰的形態。
若存在x_i∈(0，1)，使得對所有i，都有 P(A_i)≤ x_i *Π_{j∈Γ(i)}(1 - x_j)成立，則 P(∩ A_i^c)＞ 0。
他利用題目給的條件 e(d+1)≤ k，巧妙地構造出了一個統一的權重 x = 1/(d+1)，並最終證明了這個不等式成立！
做出來了。
他並不知道這個引理的名字。
他只是從最基本的概率公理出發，敏銳地抓住了「局部依賴」這一核心，然後用自己恐怖的數學直覺和構建能力，硬生生地在現場，手動推導了「洛瓦茲局部引理」！
他猛地抬頭看了一眼牆上的時鐘。
只剩下……十分鐘了！
而他，才剛剛完成證明，還沒往答題卡上抄！
徐辰立刻開始謄寫。因為是從最基本的原理開始推導，他的證明過程非常長，幾乎寫滿了整個答題區。字跡因為高速書寫而略顯潦草，但每一步都邏輯清晰，無可辯駁。
終於，在距離考試結束還有三分鐘的時候，他停下了筆。
長長地舒了一口氣。
【應該……都做對了。】
【就是不知道最後這道題，過程寫得這麼複雜，會不會被扣步驟分。】
【不過，就算扣幾分，拿個省一，應該也夠了。】
……
第一場考試結束了。
第二場考試和第一場考試中間只有20分鐘的休息時間。
考場外，走廊上。
安城三中的四人，再次聚到了一起。
「唉，最後一題太難了，完全沒思路。」林曉雅一臉沮喪。
「是啊，我連題目的考點都沒看出來。」張浩也嘆了口氣。
李帆因為參加過省城的金牌輔導班，自認為是校隊裡唯一能做出來的人，故作深沉地說道：「考的是洛瓦茲局部引理。不過計算過程啊還是很複雜，我寫上了，但不知道會不會扣過程分。」
他這番話，瞬間引來了林曉雅和張浩崇拜的目光。
「李帆你太厲害了！這都能做出來！」
「看來這次省一有希望了！」
隨後，張浩看向一旁的徐辰，關心得問道。
「徐辰，你考的怎麼樣？」張浩問道「看你一直在算，我看你中途還要了好多草稿紙，應該是卡住了吧」。
徐辰說，「最後一題確實有點難，我花了快40分鐘才寫完。」
「寫完？也就是說，你做出來了？！」張浩吃驚。
李帆則是不太相信地看著他，問道：「你知道【洛瓦茲局部引理】？你不是三天前才學的數學競賽知識嘛，這個知識點算是超綱了，你怎麼會知道。」
徐辰說「我這不知道哪個什麼【洛瓦茲局部引理】，我就是用原始的方法，硬算的」，徐辰實話實說，「過程有點繁瑣，草稿紙都用了五六張。」
「噗——」
李帆像聽到了本世紀最好笑的笑話，誇張地大笑起來：「硬算？徐辰，你開什麼玩笑！那道題的計算量，你用手硬算？不可能，絕對不可能！」
徐辰看著他的模樣，只是笑了笑，沒有再解釋。
有些事情，說再多也沒用。等結果出來，自然就不得不信。