СПбГУ 2026, 8-9 классы, задача 8
( баллов) В каждой клетке доски стоит натуральное число от до . Известно, что в каждом столбце все числа разные (в строчках числа могут повторяться). В одной из клеток доски стоит фишка. Разрешается передвинуть фишку из клетки с числом в соседнюю по стороне клетку, если в ней стоит число , , или . Существует ли расстановка чисел и начальная позиция фишки, при которых фишка сможет побывать (хотя бы один раз) в каждой клетке доски?
Ответ
Ответ: нет.
Решение. Заметим, что разрешённое передвижение фишки — это перемещение из клетки с числом одной чётности на клетку с числом другой чётности. Следовательно, в любом пути фишки по полю будут чередоваться клетки с чётными числами и клетки с нечётными числами. То есть, в любом пути фишки от начальной позиции до конечной количество посещенных клеток с чётными числами и количество посещенных клеток с нечётными числами различаются не больше, чем на .
Поскольку по условию каждый столбец состоит из клеток и в них расположены различные числа от до , то в каждом столбце каждое из чисел от до встречается ровно один раз. Поэтому, в каждом столбце нечётных чисел и чётных. Таким образом, на всей доске будет клеток с нечётными числами и клеток с чётными числами.
Если бы существовал путь фишки, проходящий через все клетки поля хотя бы один раз, то он должен был бы пройти через клетки с нечётными числами и клеток с чётными числами (и, возможно, какие-то ещё клетки). То есть в таком пути количества клеток с числами разной чётности различались бы не менее, чем на
Следовательно, такого удовлетворяющего правилам перемещения пути нет.
Верное решение