Задача 3.
В городе есть станции метро – Аль, Бета, Гамильтон, Дельта, Лямбда, Эпсилон, Икс и Зета. Известно, что между двумя станциями без пересадок ходит поезд, если количество букв в названиях этих станций имеют разную чётность. Федя хочет проехать как можно более длинный путь, не посещая никакую станцию дважды причём так, чтобы название каждой следующей станции было длинней предыдущей. Какой длины будет этот путь? Ответ объясните.
Ответ на Задачу 3.
Ответ: 3 станции.
Решение:
Заметим, что условие можно переписать так: есть числа 3, 4, 9, 6, 6, 7, 3, 4. Известно, что числа разной чётности соединены отрезком. Требуется найти ломаную с наибольшим количеством вершин. Заметим, что в такой ломаной чётные и нечётные числа чередуются и вдобавок идут по возрастанию. Нечётных числа 4, причём два из них равны, то есть могут быть использованы только числа 3, 7, 9. Поскольку нет чётных чисел меньше 3 и больше 7, то максимальная ломаная содержит не более 3 вершин. Пример для 3 вершин есть: Аль-Бета-Эпсилон.
