Задача 98089
|
|
 |
Условие
В королевстве восемь городов. Король хочет построить такую систему дорог, чтобы из каждого города можно было попасть в любой другой, минуя не более одного промежуточного города, и чтобы из каждого города выходило не более k дорог. При каких k это возможно?
Решение
Если k = 2, то из города А можно "за один ход" попасть не более чем в два города, а из них "следующим ходом" – не более чем в четыре. Итого, из А можно попасть не более чем в шесть городов, а нужно – в семь.
Для k = 3 расположим города в вершинах правильного восьмиугольника, а дороги пустим по всем сторонам и большим диагоналям.
Ответ
При k > 2.
Замечания
1. Ср. с задачей 98099.
2. 6 баллов.
