化簡數列公因數,李青眼前一亮,可行。
然後呢?
李青想了一會兒,同餘,通項,做差,是這個思路。
繼續推導模礎同餘,這一步李青推導很快,因為這是下一步證明模通項的鋪墊。
推導通項時先驗證n為3基礎成立,把n=k的式子整齊排布,利用前面的式子代換化簡,分類做差得到兩個關鍵同餘式。
寫到這一步就接近尾聲了。
最後反證,推出和結論矛盾,假設不成立,則r-s≥證畢。
又從頭看了一遍推導過程,嚴謹準確,李青將過程寫到答題卡,眉頭舒緩,內心鬆了一大口氣。
接著他整理心情。
最後一題了!
第4題【設V是空間中2019個點構成的集合,其中任意四點不共面。某些點之間連有線段,記E為這些線段構成的集合。試求最小的正整數n,滿足:若E至少有n個元素,則E一定含有908個二元子集,其中每個二元子集中的兩條線段有公共端點,且任意兩個二元子集的交為空集。】
這道題李青看了很久。
然後開始拆條件,第一時間把幾何語言轉成圖論模型,先在草稿紙上畫了兩三個極簡小圖:1箇中心點帶4片葉子、兩組分開的中心點結構,對應“同中心點再多邊,也只算1組獨立角”。
確定模型沒錯,才開始列式計算頂點與邊數的臨界值。
解題關鍵是必須能拿出908個互不共用頂點的V型角,求保證這件事一定成立的最小邊數n。
一個獨立的V型角,固定消耗1箇中心點+2個葉子點,一共3個頂點;908組互不干涉的角,最少要佔用2724個頂點,但總頂點只有2019,頂點數量不夠純3點一組。
李青又仔細推一遍,沒錯,不夠!
看來必須思考最“省頂點造角”、同時最“費邊造角”的構造,這下就難非常多了。
李青神情專注,不敢有絲毫大意。
接下來要湊出908組獨立角的畫圖方式,只要算出這種最壞結構最多能連多少邊還達不到要求,n就是這個邊數+1。
鎖定極端反例構造!
這類極值圖論題的套路就是想盡量多連邊,只用極少數的中心點來產生夾角,其餘全部是隻連一條邊的葉子。
1箇中心頂點,連著儘可能多的葉子,這個中心點能不斷產出夾角,但所有夾角全都共用這一個中心點,永遠只能算1組獨立角,再多葉子也沒法多出第二組獨立角。
李青開始計算907組獨立角最多能承載的邊數,此時剛好最多隻能取出907組獨立角,不滿足題意。
所以有908個兩兩無共邊的角。
最終得出結論:當邊數≥2795時,無論怎麼連邊,都必然湊出908組互不相交的共端點邊對,最小值為2795。
最後一題也解了出來!
李青嘴角泛起笑意,感受到一種踏實的平靜,他沒有全部順利答完題的優越感,只是覺得欣慰和滿足。
。分失上題問小在能不,驟步查檢,心復平








