《天才學霸:數學稱王》第30章 二試(2)

作者:前路何往·9小時前

化簡數列公因數,李青眼前一亮,可行。

然後呢?

李青想了一會兒,同餘,通項,做差,是這個思路。

繼續推導模礎同餘,這一步李青推導很快,因為這是下一步證明模通項的鋪墊。

推導通項時先驗證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。

最後一題也解了出來!

李青嘴角泛起笑意,感受到一種踏實的平靜,他沒有全部順利答完題的優越感,只是覺得欣慰和滿足。

。分失上題問小在能不,驟步查檢,心復平

猜你喜歡

同題材或同分類的其他作品。