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

Ваш вопрос интересный и требует разбора двух отдельных задач. Давайте рассмотрим каждую из них по очереди.

Задача 1: Страна Цифра

В этой задаче нужно определить, в какие города можно попасть из города 1, используя авиалинии, которые соединяют города, если из их названий можно составить двузначное число, делящееся на 3. Двузначное число делится на 3, если сумма его цифр делится на 3.

Итак, начнем с города 1. Смотрим, какие города можно достичь:

• Чтобы сформировать число с 1, которое делится на 3, нужно, чтобы вторая цифра (после 1) в сумме давала число, делящееся на 3. Это могут быть города 2, 5, и 8 (так как 1+2=3, 1+5=6, 1+8=9).
• Из города 2 можно попасть в города 1, 4, 7 (2+1=3, 2+4=6, 2+7=9).
• Из города 5 можно попасть в города 1, 4, 7 (5+1=6, 5+4=9, 5+7=12).
• Из города 8 можно попасть в города 1, 4, 7 (8+1=9, 8+4=12, 8+7=15).

Таким образом, из города 1 можно попасть в города 2, 5, 8, а из них - в города 1, 4, 7. Следовательно, доступны города 1, 2, 4, 5, 7, 8.

Задача 2: Страна Циферка

Здесь нужно найти наименьшее количество дорог, чтобы добраться из города 7 в город 9, если дороги соединяют города, из названий которых можно составить двузначное число, делящееся на 8. Двузначное число делится на 8, если его последние две цифры делятся на 8.

Рассмотрим возможные комбинации:

• Из города 7 можно попасть в города, где последняя цифра вместе с 7 формирует число, делящееся на 8. Это города 2 и 6 (72 и 76 делятся на 8).
• Из города 2 можно попасть в города 4 и 8 (24 и 28 делятся на 8).
• Из города 6 можно попасть только в город 4 (64 делится на 8).
• Из города 4 можно попасть в город 8 (48 делится на 8).
• Из города 8 можно попасть в город 9 (89 делится на 8).

Таким образом, чтобы добраться из города 7 в город 9, можно выбрать маршрут 7-2-4-8-9 или 7-6-4-8-9. В обоих случаях потребуется проехать 4 дороги. Это наименьшее количество дорог для данного маршрута.