Question

Есть три страны, в каждой по 18 городов. Города связаны дорогой в том и только в том случае, когда они находятся в разных странах. Почтальон Пётр хочет проехать по нескольким дорогам на велосипеде (каждая следующая дорога выходит из того города, в который пришла предыдущая), так, чтобы ни на одной дороге не побывать дважды. Какое максимальное число дорог он может посетить?

Answer 1

1. Пусть n — количество городов в стране. Заметим, что из каждого города выходит чётное число дорог: n в одну страну и n в другую. Из теоремы Эйлера следует, что, если из каждого города выходит чётное число дорог, существует цикл, проходящий по каждой дороге ровно по одному разу. Значит, ответ на задачу — все дороги.

2. Осталось посчитать общее количество дорог на карте. Всего городов 3n, из каждого города выходит по 2n дорог, каждая дорога при этом посчитана дважды. Поэтому — 2n⋅3n/2=3n².

Правильный ответ: 192 дорог(-и).

Answer 2

Давайте разберемся с этой задачей. У нас есть три страны с по 18 городами каждая. Всего у нас 54 города (3 страны * 18 городов). Чтобы посетить максимальное количество дорог и не возвращаться по уже пройденным, почтальону Петру нужно будет проехать через все города.

Поскольку города связаны дорогами только в случае, если они находятся в разных странах, Пётр будет вынужден пересекать границы между странами для того, чтобы максимизировать количество дорог.

Чтобы ни на какой дороге не побывать дважды, Пётр должен посещать каждую дорогу только один раз.

Итак, максимальное количество дорог, которые Пётр может посетить, равно (54 города - 1 начальный город) = 53 дороги.