Ходы конями, доска 3x3.

[mr.tumkan2015]

Можно ли, сделав несколько ходов конями, из положения $1$ получить положение $2$?



Мне кажется, что нельзя. Потому как последний ход всегда тупиковый. Но как это доказать попроще -- не вижу. Можете подсказать?

[svv]

[mr.tumkan2015]

svv в сообщении #1102844 писал(а):

Спасибо, но пока что не очень понял обозначения.

[DeBill]

У способа даже название есть: метод нитей и пуговиц (по Ллойду)...

(Оффтоп)

(Т.е. это подсказка: проделайте в конях дырочки, и нанижите на svv-ниточку)

[arseniiv]

(Если подсказка не сработает, здесь подробнее)

Рёбрами соединены места, для которых из одного в другое конь может перейти за один ход. Графы слева и справа изоморфны, но справа движения коней становятся намного более понятными.

[INGELRII]

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

[arseniiv]

(Оффтоп)

Wut?

Хотя, конечно, импликация «коней можно поменять $\Rightarrow$ коней можно поменять красиво» здесь верна.

[mr.tumkan2015]

Спасибо, но что-то не сходится, вот после двух ходов по указанным числам

[arseniiv]

mr.tumkan2015
Кони на ожерелье не могут друг через друга перешагивать (почему?). Из этого следует, что нельзя просунуть белого между двух чёрных.

[mr.tumkan2015]

arseniiv в сообщении #1102953 писал(а):

mr.tumkan2015
Кони на ожерелье не могут друг через друга перешагивать (почему?). Из этого следует, что нельзя просунуть белого между двух чёрных.

Про изоморфность понял, но не очевидно -- каким образом конкретной позиции коня соответствуют вершины графа и кто должен начинать ходить. А почему нельзя белого просунуть меж двух черных? Это же можно сделать первым ходом $a_{31}\to a_{21}$

[ИСН]

Это не между.

[arseniiv]

mr.tumkan2015 в сообщении #1102965 писал(а):

но не очевидно -- каким образом конкретной позиции коня соответствуют вершины графа

Эээ… Ну, слева они расположены так же, как на исходной доске. Середины только нет, но ведь ясно, почему. В начале 1, 3 vs. 5, 7, в конце 1, 5 vs. 3, 7.

[Someone]

mr.tumkan2015 в сообщении #1102965 писал(а):

arseniiv в сообщении #1102953 писал(а):

mr.tumkan2015
Кони на ожерелье не могут друг через друга перешагивать (почему?). Из этого следует, что нельзя просунуть белого между двух чёрных.

Про изоморфность понял, но не очевидно -- каким образом конкретной позиции коня соответствуют вершины графа и кто должен начинать ходить. А почему нельзя белого просунуть меж двух черных? Это же можно сделать первым ходом $a_{31}\to a_{21}$

Очевидно, про изоморфность не поняли. Хотя соответствие очень простое:

если на поле слева конь находится в клетке с номером 1, то на ожерельи справа он тоже находится на бусине с номером 1;
Если справа конь передвинулся с 1 на 8, то справа он тоже передвинулся с 1 на 8.

[TOTAL]

mr.tumkan2015 в сообщении #1102824 писал(а):

Можно ли, сделав несколько ходов конями, из положения $1$ получить положение $2$?



Мне кажется, что нельзя. Потому как последний ход всегда тупиковый. Но как это доказать попроще -- не вижу. Можете подсказать?

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

[mr.tumkan2015]

Все я понял, извините за то что страшно тупил)