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

141 Можно ли выписать в ряд натуральные числа от 1 до 9 так, чтобы сумма любых двух, стоящих рядом, делилась на 5 или на 12?

Указание. Постройте граф, соединив рёбрами числа, которые могут стоять рядом. Затем найдите какую-нибудь цепь в этом графе, проходящую через все рёбра.

Для решения этой задачи, следуя указанию, построим граф. Вершинами графа будут натуральные числа от 1 до 9. Две вершины $u$ и $v$ соединены ребром, если их сумма $u+v$ делится на 5 или на 12. Исходная задача эквивалентна поиску в этом графе гамильтонова пути — пути, который проходит через каждую вершину ровно один раз. Если такой путь существует, то последовательность вершин в этом пути и будет искомым рядом чисел.

Найдем все пары чисел от 1 до 9, которые могут стоять рядом. Сумма двух различных чисел $u$ и $v$ из этого набора ($u \ne v$) находится в диапазоне $1+2=3 \le u+v \le 8+9=17$. Условию, что сумма $u+v$ делится на 5 или на 12, удовлетворяют суммы, равные 5, 10, 15 или 12. Составим список рёбер графа, соединяющих соответствующие пары вершин:

• Сумма равна 5: $(1, 4), (2, 3)$.
• Сумма равна 10: $(1, 9), (2, 8), (3, 7), (4, 6)$.
• Сумма равна 12: $(3, 9), (4, 8), (5, 7)$.
• Сумма равна 15: $(6, 9), (7, 8)$.

Теперь проанализируем полученный граф. Определим степени вершин (количество рёбер, инцидентных каждой вершине):

• $deg(1) = 2$ (соседи 4, 9)
• $deg(2) = 2$ (соседи 3, 8)
• $deg(3) = 3$ (соседи 2, 7, 9)
• $deg(4) = 3$ (соседи 1, 6, 8)
• $deg(5) = 1$ (сосед 7)
• $deg(6) = 2$ (соседи 4, 9)
• $deg(7) = 3$ (соседи 3, 5, 8)
• $deg(8) = 3$ (соседи 2, 4, 7)
• $deg(9) = 3$ (соседи 1, 3, 6)

Вершина 5 имеет степень 1 ($deg(5) = 1$). В графе с более чем двумя вершинами любая вершина со степенью 1 должна быть начальной или конечной точкой гамильтонова пути, если таковой существует. Следовательно, искомый ряд чисел должен начинаться или заканчиваться числом 5.

Поищем гамильтонов путь. Он должен содержать ребро $(5, 7)$, так как это единственное ребро, выходящее из вершины 5. Путем перебора вариантов можно найти один из возможных путей. Например, рассмотрим следующую последовательность вершин:

5 → 7 → 3 → 2 → 8 → 4 → 1 → 9 → 6

Эта последовательность является гамильтоновым путем, так как она включает все вершины по одному разу, и каждая пара соседних вершин соединена ребром в построенном графе. Проверим, удовлетворяет ли найденная последовательность условию задачи, вычислив суммы соседних чисел:

• $5+7=12$ (делится на 12)
• $7+3=10$ (делится на 5)
• $3+2=5$ (делится на 5)
• $2+8=10$ (делится на 5)
• $8+4=12$ (делится на 12)
• $4+1=5$ (делится на 5)
• $1+9=10$ (делится на 5)
• $9+6=15$ (делится на 5)

Все суммы соседних чисел в ряду делятся на 5 или на 12. Следовательно, выписать числа в ряд требуемым образом возможно.

Ответ: Да, можно. Например, в последовательности: 5, 7, 3, 2, 8, 4, 1, 9, 6. Существуют и другие варианты, например: 6, 9, 1, 4, 8, 2, 3, 7, 5.