ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

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

Ответ

нельзя.

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

web-сайт
задача

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .