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

Решение:

Двузначное число делится на три, если сумма его цифр делится на три. Проверим, какие города можно связать с городом 1.

1. Из города 1 можно добраться до городов, названия которых (в сочетании с 1) образуют числа, кратные трём:
• 12 (1+2=3)
• 15 (1+5=6)
• 18 (1+8=9)
2. Из города 2 можно добраться до:
• 21 (2+1=3)
• 24 (2+4=6)
• 27 (2+7=9)
3. Из города 5 можно добраться до:
• 51 (5+1=6)
• 54 (5+4=9)
• 57 (5+7=12)
4. Из города 8 можно добраться до:
• 81 (8+1=9)
• 84 (8+4=12)
• 87 (8+7=15)
5. Из города 4 можно добраться до:
• 42 (4+2=6)
• 45 (4+5=9)
• 48 (4+8=12)
6. Из города 7 можно добраться до:
• 72 (7+2=9)
• 75 (7+5=12)
• 78 (7+8=15)
7. Из города 3 можно добраться до:
• 39 (3+9=12)
8. Из города 9 можно добраться до:
• 93 (9+3=12)

Путешественник может добраться из города 1 в город 9, следуя по маршруту:

• 1 → 2 → 4 → 9 (12, 24, 49)
• 1 → 5 → 7 → 9 (15, 57, 79)
• 1 → 8 → 4 → 9 (18, 84, 49)
• 1 → 2 → 7 → 9 (12, 27, 79)

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