Задача
Назовём ходы коня, при которых он смещается на две клетки по горизонтали и на одну по вертикали,горизонтальными, а остальные —вертикальными. Требуется поставить коня на одну из клеток доски $46\times46$, после чего чередовать им горизонтальные и вертикальные ходы. Докажите, что если запрещено посещать клетки более одного раза, то будет сделано не более 2024 ходов.
Решение
Решение 1:Можно считать, что первый ход был горизонтальным (иначе повернём доску). Разделим доску на 23 вертикальные полосы ширины 2 клетки и раскрасим каждую в белый или чёрный цвет, чередуя цвета полос. Крайние полосы будут одного цвета, пусть чёрного. Тогда белых клеток будет всего $11\cdot2\cdot46=1012$. Заметим, что горизонтальный ход всегда меняет цвет клетки. Пусть всего ходов было хотя бы 2025. Тогда конь посетил 2026 клеток (включая начальную), которые разбиваются на 1013 пар соседних клеток, причём в каждой паре клетки соединены горизонтальным ходом, то есть разного цвета. Тогда белых клеток пройдено минимум 1013, что невозможно.
Решение 2:Пусть первый ход горизонтальный (иначе повернём доску). Покрасим каждую вертикаль в один из 4-х цветов в порядке 1, 2, 3, 4, 1, 2, 3, 4, ..., 1, 2. За три первых хода конь посетит 4 различных цвета. Затем он сместится вертикальным ходом и снова посетит 4 различных цвета и т. д. Сделав 2023 хода, он посетит $44\cdot 46 = 2024$ клетки, поровну всех цветов. Все непосещённые клетки — цвета 1 и 2. Следующий вертикальный ход ещё возможен, а 2025-й — горизонтальный — уже нет.
Решение 3:Сделаем шахматную раскраску доски, тогда каждым ходом конь меняет цвет. Можно считать, что из чёрных клеток делаются вертикальные ходы, а из белых — горизонтальные. Рассмотрим 4 множества: чёрные клетки 1-й, 5-й, ..., 45-й горизонталей; чёрные клетки 2-й, 6-й, ..., 46-й горизонталей; белые клетки 1-й, 5-й, ..., 45-й вертикалей; белые клетки 2-й, 6-й, ..., 46-й вертикалей. Каждое содержит $23\cdot12$ клеток, из которых конь может пойти в $23\cdot11$ клеток. Значит, найдутся $23\cdot4$ клетки, из которых хода не было. Тогда всего ходов было не более $46\cdot46-23\cdot4=2024$.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь