Условие
Назовём ходы коня, при которых он смещается на две клетки по горизонтали и на одну по вертикали,
горизонтальными, а остальные —
вертикальными. Требуется поставить коня на одну из клеток доски $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$.
Источники и прецеденты использования
|
|
|
олимпиада |
|
Название |
Турнир городов |
|
год/номер |
|
Дата |
2024/25 |
|
Номер |
46 |
|
вариант |
|
Вариант |
осенний тур, сложный вариант, 8-9 класс |
|
задача |
|
Номер |
6 |
