Question

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

Answer 1

Ответ: 89

Пошаговое объяснение: всего городов 30*3=90 велосипедист начав поездку из а11 (первый индекс номер страны, второй - номер города в своей стране) может поехать в а21, затем в а31,  а12, а22, а32, ... а130, а230, а330. Всего дорог 90-1=89. Конечно это не все дороги, но почтальону ехать второй раз ехать в те города, где он уже был не имеет смысла. Условие задачи не совсем корректно!

Answer 2

Почтальон Андрей может посетить максимальное количество дорог, равное сумме всех дорог между городами в каждой из трех стран. Поскольку в каждой стране 30 городов, а города связаны дорогами только с городами других стран, то количество дорог между городами в каждой стране будет равно 30 * 30 = 900 дорог.

Так как у нас три страны, суммируем количество дорог в каждой из них:

3 * 900 = 2700

Итак, максимальное число дорог, которое может посетить Почтальон Андрей, составляет 2700 дорог.