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

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

Условие

На бесконечной шахматной доске стоит конь. Найти все клетки, куда он может попасть за 2n ходов.


Решение

  Пусть для определённости конь стоит на чёрной клетке. Все клетки, куда он может попасть за два хода, окрашены в синий цвет на рисунке слева. Случай
n = 1  исключительный.

  При  n > 1  множество клеток, куда может попасть конь за 2n ходов, устроено следующим образом. Возьмём квадрат со стороной  8n + 1  (конь стоит в центре этого квадрата). Отрежем от этого квадрата четыре уголка со стороной 2n (на рисунке справа соответствующая фигура изображена для  n = 2).  За 2n ходов конь может попасть в точности во все чёрные клетки полученной фигуры. Докажем это.
  Прежде всего заметим, что после нечётного числа ходов конь попадает на белую клетку, а после чётного – на чёрную. Индукцией по m несложно доказать, что если  m ≥ 3,  то за m ходов конь попадает в любую клетку соответствующего цвета (чёрного при чётном m и белого при нечётном m) фигуры, которая получается при отрезании от квадрата со стороной  4m + 1  четырёх уголков со стороной m. При  m = 3  это легко проверяется, а шаг индукции очевиден.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 16
Год 1953
вариант
Класс 10
Тур 2
задача
Номер 5

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

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