活用無窮遞降法，巧解奧數難題（19年4月18日）
父母是孩子最好的老師。
這是奧數君第824天給出奧數題講解。
今天的題目是綜合應用題，
解題所用知識不超過小學5年級。
題目（5星難度）：
在紙上任意畫2019個紅點和2019個藍點，任意3個點都不共線。在其中連接2019條線段，使每條線段的端點一個是紅點，另一個是藍色，且所有點都是線段的端點。是否一定能找到一種連接線段的方法，使任意兩條線段都沒公共點？
講解思路：
這道題是一道非常經典的題目，
是一位法國數學教師提出的難題。
他是受費馬的無窮遞降法啟發。
關於無窮遞降法，
在4月14日曾詳細介紹過(點擊進入)。
無窮遞降法的核心思想是：
假設某種連線法使某個值最小，
但又能找到另一個更小的值，
則假設一定是錯誤的。
因此無窮遞降法來源於反證法。
本題總的解題思路是：
假設所有連線法都會相交，
則考慮所有線段和長度最小的連線法，
看能否得到矛盾。
步驟1：
先思考第一個問題，
使所有線段和長度最小的方法是否存在？
由於點的數量是有限的，
故連線的方法也是有限的，
對應的線端和長度數值也是有限個，
因此一定存在某一種連線法，
使所有線段和長度最小。
步驟2：
再思考第二個問題，
任意2個紅點和2個藍點連線，
線段相交時的2條線段長度和會最小嗎？
如下圖所示，
2個紅點是A和C，
2個藍點是B和D，
AB與CD交於E,
則根據三角形兩邊之和大於第三邊，
AE+DE > AD且CE+BE > BC,
二者相加得AB+CD > AD+BC。
因此相交時長度和還可以更小。
步驟3：
綜合上述幾個問題，
考慮原題目的答案。
假設所有連線法都會相交，
考慮所有線段和長度最小的連線法，
則其中至少有兩條線段相交，
根據步驟2的結論，
還能找到另一種連線法，
使這2條線段長度和變小。
應用無窮遞降法的思想，
出現了矛盾，
因此假設不成立，
所以存在一種不相交的連線法。
思考題（3星難度）：
對原題目去掉一個條件。
在紙上任意畫2019個紅點和2019個藍點。在其中連接2019條線段，使每條線段的端點一個是紅點，另一個是藍色，且所有點都是線段的端點。是否一定能找到一種連接線段的方法，使任意兩條線段都沒有公共點？
獲得思考題答案方法：
關注微信公眾號「每天3道奧數題」(tiantianaoshu)
微信回復「20190418」可獲得思考題答案。
同類題目鏈接：
19年3月25日題目（綜合應用題）
19年3月12日題目（綜合應用題）
19年3月8日題目（應用題）
19年3月4日題目（應用題）
19年2月26日題目（應用題）
19年2月25日題目（應用題）
19年1月23日題目（綜合應用題）
推薦閱讀：