Условие
Назовем крокодилом шахматную фигуру,
ход которой заключается в прыжке на 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 взаимно простые, мы это делать уже умеем.
Источники и прецеденты использования
