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

Решение:

Давай разберемся, какие города соединены авиалинией. Два города соединены, если из их названий можно составить двузначное число, делящееся на 3. Города у нас с названиями от 1 до 9.

Соединения из города 1:

Мы можем составить следующие двузначные числа, используя цифру 1 как первую:

• 12 (делится на 3)
• 13 (делится на 3)
• 14 (не делится на 3)
• 15 (делится на 3)
• 16 (не делится на 3)
• 17 (не делится на 3)
• 18 (делится на 3)
• 19 (не делится на 3)

Значит, из города 1 можно попасть в города 2, 3, 5, 8.

Соединения из города 2:

Мы можем составить двузначные числа, где первая цифра 2:

• 21 (делится на 3)
• 23 (не делится на 3)
• 24 (делится на 3)
• 25 (не делится на 3)
• 26 (не делится на 3)
• 27 (делится на 3)
• 28 (не делится на 3)
• 29 (не делится на 3)

Из города 2 можно попасть в города 1, 4, 7.

Соединения из города 3:

Двузначные числа, где первая цифра 3:

• 31 (не делится на 3)
• 32 (не делится на 3)
• 34 (не делится на 3)
• 35 (не делится на 3)
• 36 (делится на 3)
• 37 (не делится на 3)
• 38 (не делится на 3)
• 39 (делится на 3)

Из города 3 можно попасть в города 6, 9.

Соединения из города 4:

Двузначные числа, где первая цифра 4:

• 41 (не делится на 3)
• 42 (делится на 3)
• 43 (не делится на 3)
• 45 (делится на 3)
• 46 (не делится на 3)
• 47 (не делится на 3)
• 48 (делится на 3)
• 49 (не делится на 3)

Из города 4 можно попасть в города 2, 5, 8.

Соединения из города 5:

Двузначные числа, где первая цифра 5:

• 51 (делится на 3)
• 52 (не делится на 3)
• 53 (не делится на 3)
• 54 (делится на 3)
• 56 (не делится на 3)
• 57 (делится на 3)
• 58 (не делится на 3)
• 59 (не делится на 3)

Из города 5 можно попасть в города 1, 4, 7.

Соединения из города 6:

Двузначные числа, где первая цифра 6:

• 61 (не делится на 3)
• 62 (не делится на 3)
• 63 (делится на 3)
• 64 (не делится на 3)
• 65 (не делится на 3)
• 67 (не делится на 3)
• 68 (не делится на 3)
• 69 (делится на 3)

Из города 6 можно попасть в города 3, 9.

Соединения из города 7:

Двузначные числа, где первая цифра 7:

• 71 (не делится на 3)
• 72 (делится на 3)
• 73 (не делится на 3)
• 74 (не делится на 3)
• 75 (делится на 3)
• 76 (не делится на 3)
• 78 (делится на 3)
• 79 (не делится на 3)

Из города 7 можно попасть в города 2, 5, 8.

Соединения из города 8:

Двузначные числа, где первая цифра 8:

• 81 (делится на 3)
• 82 (не делится на 3)
• 83 (не делится на 3)
• 84 (делится на 3)
• 85 (не делится на 3)
• 86 (не делится на 3)
• 87 (делится на 3)
• 89 (не делится на 3)

Из города 8 можно попасть в города 1, 4, 7.

Соединения из города 9:

Двузначные числа, где первая цифра 9:

• 91 (не делится на 3)
• 92 (не делится на 3)
• 93 (делится на 3)
• 94 (не делится на 3)
• 95 (не делится на 3)
• 96 (делится на 3)
• 97 (не делится на 3)
• 98 (не делится на 3)

Из города 9 можно попасть в города 3, 6.

Путешествие из города 1:

Начинаем из города 1. Мы можем попасть в города: 2, 3, 5, 8.

Теперь посмотрим, куда мы можем попасть из этих городов, чтобы в итоге добраться до всех остальных:

• Из 1 -> 2 -> 4 -> 5 -> 7 -> 8 -> 1 (можно обойти все города, кроме 3, 6, 9)
• Из 1 -> 3 -> 6 -> 9 -> 3 (можно обойти 3, 6, 9)

Таким образом, мы можем добраться до всех городов, делая пересадки.

Ответ: 1, 2, 3, 4, 5, 6, 7, 8, 9