1. Докажите, что числа от 1 до 16 можно записать в строку, но нельзя записать по кругу так, чтобы сумма любых двух соседних чисел была квадратом натурального числа.

Решение:

Для решения этой задачи нам нужно рассмотреть пары чисел, сумма которых равна квадрату натурального числа. Квадраты натуральных чисел в диапазоне, охватываемом числами от 1 до 16, это: \( 1^2 = 1 \), \( 2^2 = 4 \), \( 3^2 = 9 \), \( 4^2 = 16 \), \( 5^2 = 25 \), \( 6^2 = 36 \).

Теперь составим пары чисел от 1 до 16, сумма которых равна одному из этих квадратов:

• Сумма 4: (1, 3)
• Сумма 9: (1, 8), (2, 7), (3, 6), (4, 5)
• Сумма 16: (1, 15), (2, 14), (3, 13), (4, 12), (5, 11), (6, 10), (7, 9)
• Сумма 25: (9, 16), (10, 15), (11, 14), (12, 13)

Рассмотрим числа, которые могут быть соседями. Число 1 может быть соседом только с 3, 8, 15. Число 2 — с 7, 14. Число 3 — с 1, 6, 13. Число 4 — с 5, 12. Число 5 — с 4, 11.

Обратим внимание на числа 1, 4, 9, 16. Они имеют мало возможных пар:

• 1: может быть соседом с 3, 8, 15.
• 4: может быть соседом с 5, 12.
• 9: может быть соседом с 7, 16.
• 16: может быть соседом с 9.

Если мы попробуем расположить числа по кругу, возникнет проблема.

Попробуем построить граф: Вершины — числа от 1 до 16. Ребро между двумя вершинами, если их сумма — квадрат.

Рассмотрим числа с наименьшим числом связей:

• 16 может быть соединено только с 9.
• 1 может быть соединено с 3, 8, 15.
• 4 может быть соединено с 5, 12.
• 9 может быть соединено с 7, 16.

Если мы поставим 16, то его соседом может быть только 9. Значит, в круге 16 и 9 должны стоять рядом. Но 9 может быть соседом с 7. Тогда последовательность будет ...-7-9-16. Но 16 не может иметь других соседей, кроме 9. Следовательно, 7 не может быть соседом 9, если 9 уже сосед 16. Таким образом, по кругу числа расположить невозможно.

Доказательство:

Рассмотрим числа, имеющие ровно два соседа, сумма с которыми является квадратом:

• 16: может быть соседом с 9 (16+9=25).
• 9: может быть соседом с 7 (9+7=16) и 16 (9+16=25).
• 1: может быть соседом с 3 (1+3=4), 8 (1+8=9), 15 (1+15=16).
• 4: может быть соседом с 5 (4+5=9), 12 (4+12=16).

Если бы мы записывали числа по кругу, то каждое число должно иметь ровно двух соседей. Число 16 может быть соседом только с 9. Число 1 может быть соседом с 3, 8, 15. Если 1 сосед 3, то 3 может быть соседом с 1, 6, 13. Если 1 сосед 8, то 8 может быть соседом с 1, 17 (нет), 28 (нет). Если 1 сосед 15, то 15 может быть соседом с 1, 10, 21 (нет).

Предположим, что такое расположение существует. Рассмотрим степени вершин в графе, где вершины - числа, а ребра - пары, сумма которых квадрат. Число 16 имеет одну связь (с 9). Число 1 имеет три связи (с 3, 8, 15). Число 4 имеет две связи (с 5, 12). Число 9 имеет две связи (с 7, 16). В круговом расположении каждая вершина должна иметь степень 2. Вершина 16 имеет степень 1, что делает круговое расположение невозможным.

Вывод: Поскольку число 16 имеет только одну возможную пару (с числом 9), чтобы сумма была квадратом, оно не может иметь двух соседей в круговом расположении. Следовательно, числа от 1 до 16 нельзя записать по кругу так, чтобы сумма любых двух соседних чисел была квадратом натурального числа.