Учебник «Вероятность и статистика. 7–9 классы», часть 1, с. 89, §20
№140. Архипелаг Числовой состоит из 9 островов, у которых вместо названий номера от 1 до 9. Между двумя островами есть паромная переправа тогда и только тогда, когда сумма номеров этих островов делится на 3. Можно ли перебраться на паромах с острова 3 на остров 4?
Указание. Постройте граф. Вершины-острова соедините рёбрами-переправами.
Дано:
9 островов с номерами 1–9; паромная переправа между островами есть, если сумма их номеров делится на 3
Найти:
можно ли перебраться с острова 3 на остров 4
Построим граф: острова 1, 2, …, 9 — вершины, а две вершины соединим ребром, если сумма их номеров делится на 3. Проверим все пары. Сумма двух чисел делится на 3 в двух случаях: оба числа делятся на 3 (3, 6, 9 — например, ) или одно даёт остаток 1, а другое остаток 2 при делении на 3 (например, , ).
Острова разбиваются на три группы по остатку от деления номера на 3: {3, 6, 9} (остаток 0), {1, 4, 7} (остаток 1) и {2, 5, 8} (остаток 2). Рёбра такие: все пары внутри {3, 6, 9} (3—6, 3—9, 6—9) и все пары «остаток 1 — остаток 2» (девять рёбер: 1—2, 1—5, 1—8, 4—2, 4—5, 4—8, 7—2, 7—5, 7—8). Всего 12 рёбер.
Остров 3 соединён только с островами 6 и 9, а те — только друг с другом и с островом 3. Значит, с острова 3 можно добраться лишь до островов 6 и 9. Остров 4 лежит в другой части графа (его соседи — острова 2, 5 и 8). Граф несвязный: он состоит из двух частей, и пути с острова 3 на остров 4 нет (проверено перебором).
Объяснение без картинки: с острова, номер которого делится на 3, можно переплыть только на остров, номер которого тоже делится на 3 (ведь сумма делится на 3 только если и второе число делится на 3). А номер 4 на 3 не делится.
Ответ: нет, перебраться с острова 3 на остров 4 нельзя.
Ответ: Нет, нельзя. С любого острова, номер которого делится на 3, можно перебраться только на острова, номера которых делятся на 3, и ни на какие другие.
