Задача 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