回復 7# enlighten0626 的帖子
5.
某國有110座城市,其中任4座城市之中都至少有1座城市,會與這4座城市中的其他3座城市有鐵路相通。則該國至少有 座城市,其與該國中的所有其他城市之間有鐵路相通。
[解答]
在\(a_1,a_2,\cdots,a_{110}\)中任取四個,例如取\(a_1,a_2,a_3,a_4\),已知必有一個與其他三個皆相通,可知不可能同時找到四個兩兩不相通
觀察\(a_1,a_2,a_3\),若此三個兩兩不相通,用剩餘的\(a_4,a_5,\cdots,a_{110}\)對這三個觀察可知其餘必皆與此三個相通
觀察\(a_1,a_2,a_4,a_5\),已知\(a_1,a_2\)不相通,故\(a_4,a_5\)必相通才能滿足必有一個與其他三個皆相通
同理即可知\(a_4,a_5,\cdots,a_{110}\)全部互通
由上述可知只要有三個兩兩不相通就有107個全通,如果只有兩個不通易知會有108個,四個兩兩不相通皆不可能發生