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

Условие

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

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

Решение

рис.1

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

рис.2

 

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

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