На уроке географии ученики физматкласса рисовали карту. \(\displaystyle 9\) населённых пунктов пронумеровали цифрами от \(\displaystyle 1\) до \(\displaystyle 9{\small,}\) а затем соединили дорогами лишь те пункты, из номеров которых можно составить двузначное число, делящееся на \(\displaystyle 3{\small.}\)
Можно ли по этой карте дойти по дорогам из пункта \(\displaystyle 1\) в пункт \(\displaystyle 9{\small?}\)
По условию имеем:
- девять населённых пунктов: \(\displaystyle \color{red}{1}{\small,}\)\(\displaystyle \color{red}{2}{\small,}\)\(\displaystyle \color{red}{3}{\small,}\)\(\displaystyle \color{red}{4}{\small,}\)\(\displaystyle \color{red}{5}{\small,}\)\(\displaystyle \color{red}{6}{\small,}\)\(\displaystyle \color{red}{7}{\small,}\)\(\displaystyle \color{red}{8}\) и \(\displaystyle \color{red}{9}{\small;}\)
- между пунктами есть дорога только в том случае, если из их номеров можно составить двузначное число, делящееся на \(\displaystyle 3{\small.}\)
Чтобы ответить на вопрос, изобразим все населённые пункты и дороги между ними в виде графа:
- вершины графа – населённые пункты;
- рёбра (линии, соединяющие вершины) – дороги.
Воспользуемся признаком (или вспомним таблицу умножения)
Признак делимости на \(\displaystyle 3\)
Число делится на \(\displaystyle 3\) тогда и только тогда, когда сумма его цифр делится на \(\displaystyle 3\).
Заметим, что если двузначное число делится на \(\displaystyle 3{\small,}\) то и число, полученное перестановкой его цифр также делится на\(\displaystyle 3\) (так как сумма цифр после перестановки не меняется).
Поэтому, чтобы не запутаться, будем выписывать ребро, ведущее из вершины с меньшим номером в вершину с большим номером.
Из пункта \(\displaystyle \color{red}{\bf1}\) есть дороги в пункты \(\displaystyle \color{red}{\bf2}{\small,}\)\(\displaystyle \color{red}{\bf5}\) и\(\displaystyle \color{red}{\bf8}{\small,}\) так как на \(\displaystyle 3\) делятся: \(\displaystyle \color{blue}{12}\) ( и \(\displaystyle 21\)), \(\displaystyle \color{blue}{15}\) ( и \(\displaystyle 51\)), \(\displaystyle \color{blue}{18}\) ( и \(\displaystyle 81\)).
Начнём составлять список рёбер:
| \(\displaystyle \color{blue}{1-2}\) | \(\displaystyle \color{blue}{1-5}\) | \(\displaystyle \color{blue}{1-8}\) |
Из пункта \(\displaystyle \color{red}{\bf2}\) (кроме уже перечисленных выше) дороги ведут в пункты \(\displaystyle \color{red}{\bf4}\) и\(\displaystyle \color{red}{\bf7}{\small,}\) так как на \(\displaystyle 3\) делятся числа \(\displaystyle \color{blue}{24}\) и \(\displaystyle \color{blue}{27}\) ( а также \(\displaystyle 42\) и \(\displaystyle 72\)).
Продолжим составлять список рёбер:
| \(\displaystyle \color{blue}{1-2}\) | \(\displaystyle \color{blue}{1-5}\) | \(\displaystyle \color{blue}{1-8}\) | \(\displaystyle \color{blue}{2-4}\) | \(\displaystyle \color{blue}{2-7}\) |
Далее перечисляем только невыписанные ранее дороги:
- из пункта \(\displaystyle \color{red}{\bf3}\) в пункты \(\displaystyle \color{red}{\bf6}\) и\(\displaystyle \color{red}{\bf9}{\small,}\) так как делятся на \(\displaystyle 3\) числа\(\displaystyle \color{blue}{36}\) и \(\displaystyle \color{blue}{39}{\small;}\)
- из пункта \(\displaystyle \color{red}{\bf4}\) в пункты \(\displaystyle \color{red}{\bf5}\) и\(\displaystyle \color{red}{\bf8}{\small;}\)
- из пункта \(\displaystyle \color{red}{\bf5}\) в пункт \(\displaystyle \color{red}{\bf7}{\small;}\)
- из пункта \(\displaystyle \color{red}{\bf6}\) в пункт \(\displaystyle \color{red}{\bf9}{\small;}\)
- из пункта \(\displaystyle \color{red}{\bf7}\) в пункт \(\displaystyle \color{red}{\bf8}{\small.}\)
Окончательный список рёбер:
| \(\displaystyle \color{blue}{1-2}\) | \(\displaystyle \color{blue}{1-5}\) | \(\displaystyle \color{blue}{1-8}\) | \(\displaystyle \color{blue}{2-4}\) | \(\displaystyle \color{blue}{2-7}\) | \(\displaystyle \color{blue}{3-6}\) | \(\displaystyle \color{blue}{3-9}\) | \(\displaystyle \color{blue}{4-5}\) | \(\displaystyle \color{blue}{4-8}\) | \(\displaystyle \color{blue}{5-7}\) | \(\displaystyle \color{blue}{6-9}\) | \(\displaystyle \color{blue}{7-8}\) |
| \(\displaystyle \color{blue}{1-2}\) | \(\displaystyle \color{blue}{1-5}\) | \(\displaystyle \color{blue}{1-8}\) | \(\displaystyle \color{blue}{2-4}\) | \(\displaystyle \color{blue}{2-7}\) | \(\displaystyle \color{blue}{3-6}\) | \(\displaystyle \color{blue}{3-9}\) | \(\displaystyle \color{blue}{4-5}\) | \(\displaystyle \color{blue}{4-8}\) | \(\displaystyle \color{blue}{5-7}\) | \(\displaystyle \color{blue}{6-9}\) | \(\displaystyle \color{blue}{7-8}\) |
Нарисуем граф:
Значит, дойти по дорогам из пункта \(\displaystyle \color{red}{\bf1} \) в пункт \(\displaystyle \color{red}{\bf9} \) не удастся.
Ответ: нет.