Всесиб 2021, 10 класс, задача 3
( баллов) Найти все натуральные , для которых на клетчатой доске размера на клеток можно отметить клеток, стоящих в разных горизонталях и разных вертикалях, которые можно последовательно обойти ходом шахматного коня, начиная с некоторой, не вставая на одну клетку дважды, и вернуться на исходную клетку. Конь при этом может вставать только на отмеченные клетки.
Ответ. .
Решение. Пример для несложен:
Докажем, что при требуемого в условии набора клеток не существует. Предположим, при данном удалось отметить клеток в разных горизонталях и разных вертикалях доски на , которые можно последовательно обойти ходом шахматного коня и вернуться в исходную отмеченную клетку.
Рассмотрим величины горизонтальных перемещений коня при его последовательных ходах по отмеченным клеткам вертикалей доски. Конь либо придёт в клетку на вертикали (первой слева) из клетки на вертикали (второй слева), а затем уйдёт в клетку на вертикали (третьей слева), либо наоборот.
В первом случае (второй случай симметричен первому), чтобы не было повторов вертикалей, прийти на вертикаль он может только с вертикали , а уйти с вертикали может только на вертикаль . Все предшествующие приходу на вертикаль и последующие за уходом с вертикали ходы делаются с горизонтальным смещением , кроме одного со смещением , который замкнёт цепь перемещений коня и может произойти только у правого края доски.
Всего конь сместится по горизонтали раза на одну клетку и раза на две клетки. Ровно то же самое можно сказать и о его вертикальных перемещениях по горизонталям доски. Каждым ходом конь смещается в одном направлении на одну клетку, а в другом - на две, поэтому в общем наборе из всех его смещений в обоих направлениях число смещений на одну клетку должно совпадать с числом смещений на две клетки, откуда и .
Идея рассмотрения ходов по трём крайним вертикалям (горизонталям) доски