Номер 140, страница 88, часть 1 - гдз по алгебре 7-9 класс учебник Высоцкий, Ященко

140 Архипелаг Числовой состоит из 9 островов, у которых вместо названий номера от 1 до 9. Между двумя островами есть паромная переправа тогда и только тогда, когда сумма номеров этих островов делится на 3. Можно ли перебраться на паромах с острова 3 на остров 4?

Указание. Постройте граф. Вершины-острова соедините рёбрами-переправами.

Решение:
Для решения этой задачи воспользуемся теорией графов, как предложено в указании. Острова будут вершинами графа, а паромные переправы — его рёбрами. Всего у нас 9 вершин, пронумерованных от 1 до 9.

Условие существования ребра (переправы) между двумя вершинами (островами) с номерами $a$ и $b$ заключается в том, что их сумма $a+b$ должна делиться на 3. Это можно записать с помощью сравнений по модулю 3: $a + b \equiv 0 \pmod{3}$.

Разобьём все острова на три группы в зависимости от остатка от деления их номера на 3:
1. Острова, номера которых делятся на 3 (остаток 0): {3, 6, 9}. Обозначим эту группу $R_0$.
2. Острова, номера которых при делении на 3 дают в остатке 1: {1, 4, 7}. Обозначим эту группу $R_1$.
3. Острова, номера которых при делении на 3 дают в остатке 2: {2, 5, 8}. Обозначим эту группу $R_2$.

Теперь проанализируем, между какими группами островов могут существовать переправы.

• Пусть остров $a$ принадлежит группе $R_0$, то есть $a \equiv 0 \pmod{3}$. Чтобы сумма $a+b$ делилась на 3, необходимо, чтобы номер острова $b$ также делился на 3, то есть $b \equiv 0 \pmod{3}$. Это означает, что острова из группы $R_0$ могут быть связаны переправами только с другими островами из группы $R_0$.
• Пусть остров $a$ принадлежит группе $R_1$, то есть $a \equiv 1 \pmod{3}$. Чтобы сумма $a+b$ делилась на 3, необходимо, чтобы номер острова $b$ при делении на 3 давал в остатке 2, так как $1 + 2 = 3 \equiv 0 \pmod{3}$. Это означает, что острова из группы $R_1$ могут быть связаны переправами только с островами из группы $R_2$.
• Аналогично, если остров $a$ принадлежит группе $R_2$ ($a \equiv 2 \pmod{3}$), то для существования переправы остров $b$ должен принадлежать группе $R_1$ ($b \equiv 1 \pmod{3}$).

Из этого анализа следует, что наш граф распадается на две несвязанные между собой части (компоненты связности):
1. Первая компонента состоит из островов группы $R_0$: {3, 6, 9}.
2. Вторая компонента состоит из островов групп $R_1$ и $R_2$: {1, 4, 7} и {2, 5, 8}.

Нас интересует, можно ли перебраться с острова 3 на остров 4.
Остров 3 принадлежит первой компоненте связности ($R_0$).
Остров 4 принадлежит второй компоненте связности ($R_1$).
Поскольку между этими двумя компонентами нет ни одной переправы, добраться с острова 3 на остров 4 невозможно.

Ответ: Нет, перебраться на паромах с острова 3 на остров 4 нельзя.