Задачи из журнала «Квант» № M2140

Условие

Восемь клеток одной диагонали шахматной доски назовем забором. Ладья ходит по доске, не наступая на одну и туже клетку дважды и не наступая на клетки забора(промежуточные клетки не считаются посещенными). Какое наибольшее число прыжков через забор может совершить ладья?

Ответ: 47 прыжков.

Решение

рис.1

Разделим доску на четыре квадрата 4\times4. Заметим, что если ладья прыгает через забор, то либо начальная, либо конечная клетка прыжка закрашена цветом - голубым или розовым - на рисунке 1. Так как закрашенных клеток 24 и через каждую может проходить максимум два прыжка, то всего может оказаться не более 48 прыжков. При этом, если их ровно 48, то из каждой закрашенной клетки должно быть сделано два прыжка в не закрашенные клетки( в предыдущем подсчете прыжок из закрашенной в закрашенную будет подсчитан два раза!). Тогда все ходы из голубых клеток будут вести в белый квадрат под диагональю, а оттуда - только в голубые клетки( либо в другие клетки этого же квадрата ). Значит подобным образом ладья никогда не попадет в розовые клетки. Противоречие. Таким образом, количество прыжков не превосходит 47.
Один из возможных примеров с 47 прыжками показан на рисунке 2( числа в клетках указывают, в каком порядке ладья по ним ходит).

рис.2

 

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *