|
|
 |
Условие
Назовём крокодилом шахматную фигуру, ход которой заключается в прыжке на m клеток по вертикали или по горизонтали, и потом на n клеток в перпендикулярном направлении. Докажите что для любых m и n можно так раскрасить бесконечную клетчатую доску в два цвета (для каждых конкретных m и n своя раскраска), что каждые две клетки, соединённые одним ходом крокодила, будут покрашены в разные цвета.
Решение
Пусть d = НОД(m, n), то есть m = du, n = dv, где u и v взаимно просты. Рассмотрим два случая.
1) u и v нечётны. Разделим доску на вертикальные полосы ширины d и раскрасим их попеременно в белый и чёрный цвет. При любом ходе крокодил смещается по горизонтали на расстояние, в нечётное число раз большее d, то есть попадает в полосу другого цвета.
2) u и v – числа разной чётности. Разделим доску на квадраты d×d и раскрасим их в шахматном порядке. Разобьём ход крокодила на два полухода – по горизонтали и по вертикали. При одном из них крокодил попадает в квадрат другого цвета, а при втором цвет квадрата не меняется. Итак, за целый ход цвет меняется.
Замечания
5 баллов
