Задача про коня на клетчатой плоскости.

[karandash_oleg]

Здравствуйте! Подскажите, пожалуйста, идею, как упростить перебор вариантов?

На клетчатой плоскости отмечено несколько клеток. На каждой клетке плоскости написано, за какое наименьшее число ходов шахматный конь может дойти от этой клетки до какой-нибудь отмеченной. Андрей вырезал из плоскости полоску
$5\times 1$, не содержащую отмеченных клеток. Докажите, что в клетках этой полоски есть два равных числа.

Первое, что я сделал -- это взял отмеченную точку и начал заполнять плоскость числами.



Но если добавляется еще одна отмеченная точка где-то поблизости, то часть этих чисел может измениться. Как можно учесть все эти нюансы. Ведь тут куча вариантов выходит.

[grizzly]

karandash_oleg в сообщении #1038031 писал(а):

Первое, что я сделал -- это взял отмеченную точку и начал заполнять плоскость числами.

Надо было начать с другого -- разобраться, как ходит конь Я ещё не вникал, но первая же клетка, которую я проверил, была ошибочная (в соседней по диагонали от выделенной должно быть 2, а не 3).

[whitefox]

Ну вот стоит у вас конь в какой-нибудь клетке, и пусть в этой клетке записано число $n>0.$ Значит найдётся хотя бы одна клетка на которую конь может перейти за один ход и в которой записано число $n-1.$ А сколькими способами он может вернуться на прежнюю линию? И не забудьте, что отмеченных клеток несколько (то есть больше одной).

[TOTAL]

karandash_oleg в сообщении #1038031 писал(а):

Как можно учесть все эти нюансы.

Внутри полоски из любой клетки в любую нужно не более трех ходов. Поэтому в полоске не могут быть разные числа (ведь среди них были бы отличные минимум на 4)

[karandash_oleg]

whitefox в сообщении #1038039 писал(а):

Ну вот стоит у вас конь в какой-нибудь клетке, и пусть в этой клетке записано число $n>0.$ Значит найдётся хотя бы одна клетка на которую конь может перейти за один ход и в которой записано число $n-1.$ А сколькими способами он может вернуться на прежнюю линию? И не забудьте, что отмеченных клеток несколько (то есть больше одной).

В такой ситуации -- один способ из клетки с номером $1$.



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

[whitefox]

А вы рассмотрите не клетку с числом 2, а клетку слева от неё. Впрочем, это уже не важно — TOTAL дал полное решение.

[karandash_oleg]

Спасибо, TOTAL, решение просто шикарно и лаконично)))