2014-06-08
В некоторой стране любые два города связаны друг с другом непосредственно одним из следующих средств сообщения: автобусом, поездом или самолетом. Известно, что не существует города, обеспеченного всеми тремя видами транспорта, и в то же время не существует таких трех городов, любые два из которых связаны одним и тем же средством сообщения. Найти наибольшее возможное количество городов в этой стране.
Решение:
Предположим, что существуют пять городов, соединенных указанным в задаче образом. Докажем прежде всего, что ни из какого города не выходят три линии одного и того же вида транспорта. Пусть город А соединен с городами В, С и D, например, самолетом. Тогда по условию ни одна пара из городов В, С и D не может быть соединена самолетом. Пусть В и С соединены, например, поездом. Города С и D не могут быть соединены автобусом, так как иначе город С имел бы все три вида транспорта. Поэтому С и D соединены поездом. По тем же причинам города В и D также соединены поездом. Получили, что В, С и D попарно соединены поездом. Противоречие. Итак, из каждого города выходят две транспортные линии одного вида и две транспортные линии некоторого другого вида. Тогда каждый город обслуживается ровно двумя видами транспорта. Поэтому хотя бы один вид транспорта обслуживает не более чем три города (иначе всего городов было бы не менее чем $4 \cdot 3/2 = 6$). Если он обслуживает ровно два города, то из каждого из этих городов выходит только одна транспортная линия такого вида, что невозможно. Если же он обслуживает ровно три города, то они должны быть соединены попарно этим видом транспорта, что также невозможно. Таким образом, мы доказали, что для пяти городов условие задачи невыполнимо. Тем более оно невыполнимо для большего числа городов. Если же рассмотреть четыре города А, В, С и D, которые связаны следующим образом: А с В поездом, С с D автобусом, а все остальные пары самолетом, то все -условия задачи будут выполнены. Следовательно, наибольшее число городов равно 4.