5) У графа в замке 9 пронумерованных башен, номера которых соответствуют натуральным числам 1, 2, 3, 4, 5, 6, 7, 8, 9. Известно, что башни, номера которых в сумме дают число, кратное 3, имеют соединяющий потайной проход. Можно ли добраться из башни с номером 1 по потайным проходам в башню с номером 9?

Нет. Обоснование ниже. Пошаговое решение 1) Разбор по остаткам от деления на 3 - Остаток 0: {3, 6, 9} - Остаток 1: {1, 4, 7} - Остаток 2: {2, 5, 8} 2) Правило соединений Башни соединены потайным ходом тогда, когда их номера суммируются до кратного 3. Значит: - между двумя числами из остатка 0: все пары соединены (например, 3–6, 3–9, 6–9). - между числами остатка 1 и остатка 2: любые пары соединены (например, 1–2, 1–5, 4–8 и т.д.). - между числами из одного и того же класса 1 или 2 связи нет. - между классами 0 и 1/2 связей нет. 3) Структура графа - Компонента A: остаток 1 и остаток 2 вместе образуют полную двусвязную графу K3,3 между {1,4,7} и {2,5,8}. Это значит, из любой башни из {1,4,7} можно попасть в любую башню из {2,5,8}, и наоборот. - Компонента B: остаток 0 {3,6,9} образуют треугольник (любые две из них соединены). - Нет связей между компонентами A и B. То есть вершины из {1,4,7,2,5,8} не соединены с вершинами из {3,6,9}. 4) Где находятся башни 1 и 9 - 1 принадлежит к компоненте A (остаток 1). - 9 принадлежит к компоненте B (остаток 0). Поскольку между компонентами A и B нет связей, путь из 1 в 9 не существует. Дополнительная иллюстрация (поиск пути) - Из 1 соседями являются 2, 5, 8. - Из 2, 5, 8 — их соседи: 1, 4, 7. - Таким образом достижимые вершины из 1: {1, 2, 4, 5, 7, 8}. Вершины {3, 6, 9} не достижимы. Ответ: нельзя добраться из башни 1 до башни 9 по потайным проходам.