Question

В Морском государстве 10 городов, которые соединены 37 паромными переправами (каждая пара городов соединена не более чем одной паромной переправой). Докажите, что из любого города можно добраться в любой другой.

Answer 1

Ответ:

Пошаговое объяснение:

Предположим, что есть какой-то изолированный город, до которого нельзя добраться на паромных переправах.

Тогда все 37 переправ соединяют только 9 городов из 10.

Но, если провести переправы из каждого города во все остальные, то получится 9*8/2 = 36 переправ.

Значит, 37-ая переправа должна соединять один 9 городов с 10-ым городом.

Таким образом, мы доказали, что из любого города можно попасть в этот выделенный город (один из 9), а из него - в изолированный город.

А также из любого города из этих 9 можно попасть в любой другой, из этих же 9 городов.

В итоге - из любого города можно попасть в любой другой.