В Морском государстве 10 городов, которые соединены 37 паромными переправами (каждая пара городов соединена не более чем одной паромной переправой). Докажите, что из любого города можно добраться в любой другой.
More Questions From This User See All
Answers & Comments
Verified answer
Ответ:
Пошаговое объяснение:
Предположим, что есть какой-то изолированный город, до которого нельзя добраться на паромных переправах.
Тогда все 37 переправ соединяют только 9 городов из 10.
Но, если провести переправы из каждого города во все остальные, то получится 9*8/2 = 36 переправ.
Значит, 37-ая переправа должна соединять один 9 городов с 10-ым городом.
Таким образом, мы доказали, что из любого города можно попасть в этот выделенный город (один из 9), а из него - в изолированный город.
А также из любого города из этих 9 можно попасть в любой другой, из этих же 9 городов.
В итоге - из любого города можно попасть в любой другой.