Задача 116671

Темы:    [ Шахматные доски и шахматные фигуры ] [ Примеры и контрпримеры. Конструкции ] [ Комбинаторика (прочее) ]

Сложность: 4- Классы: 7,8,9

Условие

Автор: Клепцын В.А.

Клетки доски размером 5×5 раскрашены в шахматном порядке (угловые клетки – чёрные). По чёрным клеткам этой доски двигается фигура – мини-слон, оставляя след на каждой клетке, где он побывал, и больше в эту клетку не возвращаясь. Мини-слон может ходить либо в свободные от следов соседние (по диагонали) клетки, либо прыгать (также по диагонали) через одну клетку, в которой оставлен след, на свободную клетку за ней. Какое наибольшее количество клеток сможет посетить мини-слон?

Решение

  Приведём вначале пример маршрута мини-слона, который обеспечит посещение им двенадцати клеток (см. рис., числа от 1 до 12 показывают порядок обхода клеток).

  Докажем, что все чёрные клетки мини-слон обойти не сможет. Рассмотрим четыре угловые клетки. Выйти из такой клетки мини-слон может либо в соседнюю клетку, либо в центральную. В соседнюю клетку из угловой он может пойти только первым ходом. Действительно, попасть в угловую клетку можно либо из соседней, либо из центральной, перепрыгнув через уже пройденную соседнюю. В обоих случаях, снова пойти в соседнюю клетку мини-слон не сможет. В центральную клетку из угловой мини-слон может пойти также не более одного раза. Таким образом, мини-слон покинет угловые клетки не более двух раз, значит, он посетит не более трёх угловых клеток.

Ответ

12 клеток.

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

олимпиада
Название	Московская устная олимпиада для 6-7 классов
год/номер
Номер	10 (2012 год)
Дата	2012-03-9
класс
	1
Класс	7 класс
задача
Номер	7.9