Есть три страны, в каждой по 26 городов. Города связаны дорогой в том и только в том случае, когда они находятся в разных странах. Почтальон Николай хочет проехать по нескольким дорогам на велосипеде (каждая следующая дорога выходит из того города, в который пришла предыдущая), так, чтобы ни на одной дороге не побывать дважды. Какое максимальное число дорог он может посетить?
Answers & Comments
Ответ:
2028 дорог(-и).
Пошаговое объяснение:
1. Пусть n — количество городов в стране. Заметим, что из каждого города выходит чётное число дорог: n в одну страну и n в другую. Из теоремы Эйлера следует, что, если из каждого города выходит чётное число дорог, существует цикл, проходящий по каждой дороге ровно по одному разу. Значит, ответ на задачу — все дороги.
2. Осталось посчитать общее количество дорог на карте. Всего городов 3n, из каждого города выходит по 2n дорог, каждая дорога при этом посчитана дважды. Поэтому — 2n⋅3n2=3n2.