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

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

Город 1 связан только с городами 4 и 7. Из группы 1, 4, 7 нельзя попасть в группу 3, 6, 9.

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