Задача 35656

Темы:    [ Комбинаторная геометрия (прочее) ] [ Разбиения на пары и группы; биекции ]

Сложность: 4 Классы: 10,11

Условие

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

Подсказка

Рассмотрите достаточно большой квадрат на бесконечной доске. Незанятых черных клеток в этом квадрате гораздо меньше, чем белых.

Решение

Предположим, что фишки расставлены на черных полях (см. картинку). Рассмотрим достаточно большой квадрат (4N-3)*(4N-3) (значение N уточним позже), в углах которого расставлены фишки, а также квадрат размером (4N+1)*(4N+1), полученный из квадрата (4N-3)*(4N-3) расширением на 2 клетки в каждую сторону. Число белых полей в квадрате (4N-3)*(4N-3) равно A(N) = ((4N-3)*(4N-3)-1)/2 = 8N²-12N+4. Если бы конь обошел все не занятые фишками поля, то с каждого белого поля квадрата (4N-3)*(4N-3) он бы пошел на одно из черных полей квадрата (4N+1)*(4N+1), не занятых фишками (причем все эти черные поля должны быть различны). Всего внутри этого квадрата N² полей заняты фишками, поэтому число незанятых черных полей равно B(N) = ((4N+1)*(4N+1)+1)/2-N² = 7N²+4N+1. Итак, если конь обошел оставшуюся часть доски, то B(N) должно быть не меньше, чем A(N). Однако при N>16 имеем: A(N)-B(N) = N²-16N+3 = N(N-16)+3 > 0. Таким образом, мы получили противоречие, показывающее, что искомый обход конем бесконечной доски невозможен.

Ответ

нельзя.

Источники и прецеденты использования

web-сайт

задача