Проверьте: вы умнее советского школьника-олимпиадника?
Эту задачу предлагали на Всесоюзной математической олимпиаде в 1969 году для учеников восьмого класса.
В некотором государстве система авиалиний устроена таким образом, что любой город соединен авиалиниями не более чем с тремя другими, и из любого города можно попасть в любой другой, сделав не более одной пересадки. Какое наибольшее количество городов может быть в этом государстве?
Эту задачу предлагали на Всесоюзной математической олимпиаде в 1969 году для учеников восьмого класса.
В некотором государстве система авиалиний устроена таким образом, что любой город соединен авиалиниями не более чем с тремя другими, и из любого города можно попасть в любой другой, сделав не более одной пересадки. Какое наибольшее количество городов может быть в этом государстве?
Из фиксированного города А можно попасть напрямую не более, чем в три города, а с одной пересадкой — еще не более, чем в 3·2 = 6 городов. Таким образом, всего городов может быть не более десяти.
Построить сеть из 10 городов возможно, такой граф называется графом Петерсена. Его примеры можно видеть на рисунках:
Построить сеть из 10 городов возможно, такой граф называется графом Петерсена. Его примеры можно видеть на рисунках:
