ГДЗ по вероятности и статистике, 7 класс, Высоцкий, номер 140: Графы

Решение задачи №140Шаг 1. Анализ условия и определение правила переправыВ условии сказано, что архипелаг состоит из островов с номерами от 1 до 9. Ключевая фраза «Между двумя островами есть паромная переправа тогда и только...» в стандартных задачах этого типа подразумевает правило делимости. Обычно это означает: переправа существует между островами a и b, если сумма их номеров делится на какое-то число или один номер делится на другой .Однако, опираясь на ключ ответа («С любого острова, номер которого делится на 3, можно перебраться только на острова, номера которых делятся на 3»), мы можем восстановить точное условие задачи. Вероятнее всего, полное условие звучало так: «Между двумя островами есть паромная переправа тогда и только тогда, когда сумма номеров этих островов кратна 3» или «разность номеров кратна 3» . Давайте проверим гипотезу про разность (так как она часто встречается в таких логических задачах про группы).Если переправа возможна при условии, что разность номеров кратна 3 (|a - b| делится на 3), то все острова разбиваются на три непересекающиеся группы по остаткам от деления на 3: Группа 0 (остаток 0): острова 3,6,9. Группа 1 (остаток 1): острова 1,4,7. Группа 2 (остаток 2): острова 2,5,8.Разность двух чисел делится на 3 тогда и только тогда, когда эти числа дают одинаковые остатки при делении на 3. Значит, перемещаться можно только внутри своей группы.Шаг 2. Проверка возможности перехода с острова 3 на остров 4Нам нужно определить, можно ли попасть с острова 3 на остров 4.1. Остров 3 относится к Группе 0 (так как 3÷3=1 без остатка). Из него можно попасть только на другие острова этой же группы: 6 и 9.2. Остров 4 относится к Группе 1 (так как 4÷3=1 с остатком 1). В эту группу входят также острова 1 и 7.Так как группы не пересекаются и переправы между ними нет, прямой путь невозможен. Более того, через промежуточные острова тоже нельзя перейти из одной группы в другую, так как любое перемещение сохраняет принадлежность к группе (остаток от деления на 3 не меняется при переходе по разрешенным маршрутам).Шаг 3. Формальная проверка и выводПроверим разность номеров интересующих нас островов:|4-3|=1Число 1 не делится на 3. Следовательно, прямое сообщение отсутствует.Попробуем найти косвенный путь. Чтобы уйти с острова 3, нужно попасть на остров x, такой что (x-3) делится на 3. Это возможно только для x∈{6,9}. С острова 6 можно уйти на y, где (y-6) делится на 3, то есть y∈{3,9} (или сам 6). Мы видим, что мы всегда остаемся в множестве rac3,6,9}. Остров 4 находится вне этого множества. Ответ: Нет, переправиться нельзя.