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