Если вы планируете сделку с его участием, мы настоятельно рекомендуем вам не совершать ее до окончания блокировки. Если пользователь уже обманул вас каким-либо образом, пожалуйста, пишите в арбитраж, чтобы мы могли решить проблему как можно скорее.
Проверьте: вы умнее советского школьника-олимпиадника?
Эту задачу предлагали на Всесоюзной математической олимпиаде в 1969 году для учеников восьмого класса.
В некотором государстве система авиалиний устроена таким образом, что любой город соединен авиалиниями не более чем с тремя другими, и из любого города можно попасть в любой другой, сделав не более одной пересадки. Какое наибольшее количество городов может быть в этом государстве?
![bolshaya_peremena.jpg](http://img.tyt.by/620x620s/n/it/0e/d/bolshaya_peremena.jpg)
Эту задачу предлагали на Всесоюзной математической олимпиаде в 1969 году для учеников восьмого класса.
В некотором государстве система авиалиний устроена таким образом, что любой город соединен авиалиниями не более чем с тремя другими, и из любого города можно попасть в любой другой, сделав не более одной пересадки. Какое наибольшее количество городов может быть в этом государстве?
Из фиксированного города А можно попасть напрямую не более, чем в три города, а с одной пересадкой — еще не более, чем в 3·2 = 6 городов. Таким образом, всего городов может быть не более десяти.
Построить сеть из 10 городов возможно, такой граф называется графом Петерсена. Его примеры можно видеть на рисунках:
Построить сеть из 10 городов возможно, такой граф называется графом Петерсена. Его примеры можно видеть на рисунках:
![zagadka_graf_petersona.png](http://img.tyt.by/n/it/0f/10/zagadka_graf_petersona.png)