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

Число делится на 3, если сумма его цифр делится на 3. Поэтому соединены города, номера которых в сумме дают число, кратное 3.

Из города 1 можно попасть, например, в город 2, так как число 12 делится на 3. Из города 2 можно попасть в город 4, так как число 24 делится на 3. Из города 4 можно попасть в город 5, так как число 45 делится на 3. Из города 5 можно попасть в город 7, так как число 57 делится на 3. Из города 7 можно попасть в город 9, так как число 79 не делится на 3, однако число 97 также не делится на 3. Поэтому этот путь не подходит.

Подберём другой путь: \(1\to2\to4\to8\to7\to9\) невозможен на последнем переходе, поскольку \(79\) и \(97\) не делятся на 3. Города 1 и 9 принадлежат разным группам по остаткам при делении на 3: \(1\equiv1\pmod3\), \(9\equiv0\pmod3\). Для соединения сумма номеров должна быть кратна 3, значит остатки номеров соединённых городов должны быть противоположными: \(1+2\equiv0\) или \(0+0\equiv0\). Город 9 соединён с городами 3 и 6, а город 1 — с городами 2, 5 и 8. Между этими группами есть переходы, например \(1\to2\to4\to5\to9\): числа \(12\), \(24\), \(45\), \(59\) делятся на 3.

Ответ: да, например, по маршруту \(1\to2\to4\to5\to9\).