Задача
Несколько Совершенно Секретных Объектов соединены подземной железной дорогой таким образом, что каждый Объект напрямую соединён не более чем с тремя другими и от каждого Объекта можно добраться под землей до любого другого, сделав не более одной пересадки. Каково максимальное число Совершенно Секретных Объектов?
Решение
Оценка. Из данного Объекта можно добраться за один "ход" до трёх Объектов, а с пересадкой – еще до 2·3 = 6 Объектов. Следовательно, Объектов не больше 10.
Пример с 10 Объектами изображен на рисунке.
Ответ
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет