2. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если число, составленное из цифр-названий этих городов, делится на 3. Постройте граф и ответьте на вопрос, можно ли добраться из города 1 в город 9?

Решение:

Правило соединения городов: Два города соединены, если число, составленное из их названий (цифр), делится на 3. По признаку делимости на 3, число делится на 3, если сумма его цифр делится на 3. В нашем случае названия городов — это однозначные числа, поэтому города соединяются, если сумма их номеров делится на 3.

Правило соединения для однозначных чисел: Два города с номерами A и B соединены, если A + B делится на 3.

Список соединений (ребер графа):

• Город 1: соединён с городами, сумма номеров с которыми делится на 3. 1+2=3, 1+5=6, 1+8=9. Значит, 1 соединён с 2, 5, 8.
• Город 2: соединён с 1 (2+1=3), 4 (2+4=6), 7 (2+7=9).
• Город 3: соединён с 3 (3+3=6), 6 (3+6=9), 9 (3+9=12).
• Город 4: соединён с 2 (4+2=6), 5 (4+5=9), 8 (4+8=12).
• Город 5: соединён с 1 (5+1=6), 4 (5+4=9), 7 (5+7=12).
• Город 6: соединён с 3 (6+3=9), 6 (6+6=12), 9 (6+9=15).
• Город 7: соединён с 2 (7+2=9), 5 (7+5=12), 8 (7+8=15).
• Город 8: соединён с 1 (8+1=9), 4 (8+4=12), 7 (8+7=15).
• Город 9: соединён с 3 (9+3=12), 6 (9+6=15).

Граф:

Можно представить города как вершины, а авиалинии как рёбра. Ниже приведено описание графа:

• Вершины: {1, 2, 3, 4, 5, 6, 7, 8, 9}
• Рёбра: {(1,2), (1,5), (1,8), (2,4), (2,7), (3,3), (3,6), (3,9), (4,5), (4,8), (5,7), (6,6), (6,9), (7,8), (8,7), (9,3), (9,6)}

Можно ли добраться из города 1 в город 9?

Рассмотрим пути из города 1:

1 -> 2 -> 4 -> 5 -> 7 -> 8 -> 1 (цикл)

1 -> 5 -> 4 -> 2 -> 7 -> 8 -> 1 (цикл)

1 -> 8 -> 4 -> 5 -> 7 -> 2 -> 1 (цикл)

1 -> 8 -> 7 -> 5 -> 4 -> 2 -> 1 (цикл)

Из этих соединений видно, что город 1 соединен с городами 2, 5, 8. Город 9 соединен с городами 3, 6.

Чтобы добраться из города 1 в город 9, нужно найти путь, где промежуточные города соединяют эти две группы.

Например, можно ли добраться из города 2 (сосед 1) в город 3 (сосед 9)?

2 -> 4 -> 8 -> 7 -> 5 -> 1. Мы вернулись в 1.

2 -> 7 -> 5 -> 4 -> 8 -> 1. Мы вернулись в 1.

Давайте посмотрим на группы городов, номера которых дают одинаковый остаток при делении на 3:

• Остаток 0: {3, 6, 9}
• Остаток 1: {1, 4, 7}
• Остаток 2: {2, 5, 8}

Правило соединения: Два города соединены, если сумма их номеров делится на 3. Это значит, что города соединяются, если:

• Оба города из группы с остатком 0 (например, 3+6=9, 3+9=12, 6+9=15).
• Оба города из группы с остатком 1 (например, 1+4=5, 1+7=8, 4+7=11 – *ОШИБКА, эти суммы не делятся на 3. Пересмотрим правило.*)

Пересмотр правила: Число делится на 3, если сумма его цифр делится на 3. У нас города — это однозначные числа. Значит, города A и B соединены, если A + B делится на 3.

Группы по остатку от деления на 3:

• Остаток 0: {3, 6, 9}. Суммы пар: 3+6=9, 3+9=12, 6+9=15. Все делятся на 3. Города внутри этой группы соединены.
• Остаток 1: {1, 4, 7}. Суммы пар: 1+4=5, 1+7=8, 4+7=11. Не делятся на 3. Города внутри этой группы НЕ соединены.
• Остаток 2: {2, 5, 8}. Суммы пар: 2+5=7, 2+8=10, 5+8=13. Не делятся на 3. Города внутри этой группы НЕ соединены.

Соединения между группами:

• Город из остатка 0 + Город из остатка 1 = Сумма с остатком 1 (НЕ делится на 3). Например, 3+1=4, 6+4=10, 9+7=16.
• Город из остатка 0 + Город из остатка 2 = Сумма с остатком 2 (НЕ делится на 3). Например, 3+2=5, 6+5=11, 9+8=17.
• Город из остатка 1 + Город из остатка 2 = Сумма с остатком 0 (ДЕЛИтся на 3). Например, 1+2=3, 1+5=6, 1+8=9, 4+2=6, 4+5=9, 4+8=12, 7+2=9, 7+5=12, 7+8=15.

Итог:

• Города {3, 6, 9} соединены только между собой.
• Города {1, 4, 7} соединены только с городами {2, 5, 8}.
• Города {2, 5, 8} соединены только с городами {1, 4, 7}.

Можно ли добраться из города 1 в город 9?

Город 1 относится к группе с остатком 1. Город 9 относится к группе с остатком 0. Между этими группами нет прямого соединения, так как сумма их номеров всегда будет иметь остаток 1 или 2 при делении на 3.

Следовательно, добраться из города 1 в город 9 НЕЛЬЗЯ.

Ответ: Нет, добраться из города 1 в город 9 нельзя.