Городская олимпиада «Аль-Фараби» по математике, 10-11 сыныпы
В некотором государстве система авиалиний устроена так, что любой город соединен авиалиниями не более, чем с тремя другими городами и из любого города в любой другой город можно перелететь, сделав не более одной пересадки. Какое наибольшее число городов может быть в этом государстве?
посмотреть в олимпиаде
Комментарий/решение:
Комментарии от администратора Комментарии от администратора №1. Ответ: 10.
Из фиксированного города A можно проехать без пересадки не более чем в три города, а из каждого из этих городов — еще не более чем в два отличных от A города. Поскольку в каждый город можно долететь из A не более чем с одной пересадкой, то всего в государстве не более 1+3+3⋅2=10 городов. Между 10 городами A1, A2, …, A10 сообщение с наблюдением условий задачи можно установить, например, так, как показано на рисунке ниже.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.