ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 32072
Темы:    [ Шахматная раскраска ]
[ Четность и нечетность ]
[ Шахматные доски и шахматные фигуры ]
[ Теория алгоритмов (прочее) ]
Сложность: 3+
Классы: 8,9
В корзину
Прислать комментарий

Условие

"Крокодилом" называется фигура, ход которой заключается в прыжке на клетку, в которую можно попасть сдвигом на одну клетку по вертикали или горизонтали, а затем на N клеток в перпендикулярном направлении (при  N = 2  "крокодил" – это шахматный конь).
При каких N "крокодил" может пройти с каждой клетки бесконечной шахматной доски на любую другую?


Решение

  Будем считать, что рассматриваемая бесконечная шахматная доска, как и обычная, раскрашена в белый и чёрный цвета в шахматном порядке. Тогда при нечётном N "крокодил" будет ходить только по клеткам одного цвета, и, тем самым не может пройти на любую клетку.
  Докажем, что при чётном N "крокодил" может пройти с каждой клетки на любую. Достаточно доказать, что он может пройти с любой клетки на соседнюю (смежную по стороне). Покажем, например, как пройти из клетки в соседнюю с ней сверху. Первым ходом ходим на одну клетку вправо и N клеток вверх, а вторым – на одну вправо и N вниз. Так мы окажемся на две клетки правее исходной. Повторив эту пару ходов N/2 раз, мы окажемся на N клеток правее исходной. Теперь пойдем на одну клетку вверх и N влево.

Замечания

Источник решения: книга В.О. Бугаенко "Турниры им. Ломоносова. Конкурсы по математике". МЦНМО-ЧеРо. 1998.

Источники и прецеденты использования

олимпиада
Название Турнир им.Ломоносова
год/номер
Номер 09
Дата 1986
задача
Номер 14

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .