|
|
 |
Условие
Назовем крокодилом шахматную фигуру,
ход которой заключается в прыжке на m клеток по вертикали или по
горизонтали, и потом на n клеток в перпендикулярном направлении.
Докажите что для любых m и n можно так
раскрасить бесконечную клетчатую доску в 2 цвета (для каждых
конкретных m и n своя раскраска),
что всегда 2 клетки, соединенные одним ходом крокодила,
будут покрашены
в разные цвета.
Подсказка
Решите задачу сначала в случае взаимно простых чисел m и n.
Решение
Предположим сначала, что числа m и n взаимно простые. Рассмотрим два случая. Первый случай: числа m и n разной чётности, т. е. одно чётное, а другое нечётное. Тогда искомой будет обычная шахматная раскраска. Второй случай: числа m и n оба нечётные. Тогда раскрашивать доску нужно полосами шириной в одну клетку, чередуя цвета полос. Пусть теперь m и n имеют наибольший общий делитель d > 1. Разобьем доску на квадратные блоки размером d*d клеток. Будем закрашивать доску блоками, считая каждый такой блок за отдельную клетку, для случая хода крокодила на m/d клеток в одном направлении, и на n/d клеток - в перпендикулярном. Поскольку числа m/d и n/d взаимно простые, мы это делать уже умеем.
Источники и прецеденты использования
| web-сайт | |
| задача |
