Городская олимпиада «Аль-Фараби» по математике, 10-11 классы

В некотором государстве система авиалиний устроена так, что любой город соединен авиалиниями не более, чем с тремя другими городами и из любого города в любой другой город можно перелететь, сделав не более одной пересадки. Какое наибольшее число городов может быть в этом государстве?

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ: 10.
Из фиксированного города $A$ можно проехать без пересадки не более чем в три города, а из каждого из этих городов — еще не более чем в два отличных от $A$ города. Поскольку в каждый город можно долететь из $A$ не более чем с одной пересадкой, то всего в государстве не более $1 + 3 + 3 \cdot 2 = 10$ городов. Между 10 городами $A_1$, $A_2$, $\ldots$, $A_{10}$ сообщение с наблюдением условий задачи можно установить, например, так, как показано на рисунке ниже.