2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Ходы конями, доска 3x3.
Сообщение28.02.2016, 16:41 


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

Изображение

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

 Профиль  
                  
 
 Re: Ходы конями, доска 3x3.
Сообщение28.02.2016, 17:11 
Заслуженный участник
Аватара пользователя


23/07/08
10908
Crna Gora
Изображение

 Профиль  
                  
 
 Re: Ходы конями, доска 3x3.
Сообщение28.02.2016, 17:48 


14/10/15
120
svv в сообщении #1102844 писал(а):
Изображение

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

 Профиль  
                  
 
 Re: Ходы конями, доска 3x3.
Сообщение28.02.2016, 17:52 
Заслуженный участник


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

(Оффтоп)

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

 Профиль  
                  
 
 Re: Ходы конями, доска 3x3.
Сообщение28.02.2016, 18:02 
Заслуженный участник


27/04/09
28128

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

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

 Профиль  
                  
 
 Re: Ходы конями, доска 3x3.
Сообщение28.02.2016, 22:14 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Ходы конями, доска 3x3.
Сообщение28.02.2016, 22:23 
Заслуженный участник


27/04/09
28128

(Оффтоп)

Wut? :shock:

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

 Профиль  
                  
 
 Re: Ходы конями, доска 3x3.
Сообщение28.02.2016, 23:03 


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

Изображение

 Профиль  
                  
 
 Re: Ходы конями, доска 3x3.
Сообщение28.02.2016, 23:09 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Ходы конями, доска 3x3.
Сообщение28.02.2016, 23:58 


14/10/15
120
arseniiv в сообщении #1102953 писал(а):
mr.tumkan2015
Кони на ожерелье не могут друг через друга перешагивать (почему?). Из этого следует, что нельзя просунуть белого между двух чёрных.

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

 Профиль  
                  
 
 Re: Ходы конями, доска 3x3.
Сообщение29.02.2016, 08:47 
Заслуженный участник
Аватара пользователя


18/05/06
13438
с Территории
Это не между.

 Профиль  
                  
 
 Re: Ходы конями, доска 3x3.
Сообщение29.02.2016, 09:49 
Заслуженный участник


27/04/09
28128
mr.tumkan2015 в сообщении #1102965 писал(а):
но не очевидно -- каким образом конкретной позиции коня соответствуют вершины графа
Эээ… Ну, слева они расположены так же, как на исходной доске. Середины только нет, но ведь ясно, почему. В начале 1, 3 vs. 5, 7, в конце 1, 5 vs. 3, 7.

 Профиль  
                  
 
 Re: Ходы конями, доска 3x3.
Сообщение29.02.2016, 12:59 
Заслуженный участник
Аватара пользователя


23/07/05
17976
Москва
mr.tumkan2015 в сообщении #1102965 писал(а):
arseniiv в сообщении #1102953 писал(а):
mr.tumkan2015
Кони на ожерелье не могут друг через друга перешагивать (почему?). Из этого следует, что нельзя просунуть белого между двух чёрных.

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

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

 Профиль  
                  
 
 Re: Ходы конями, доска 3x3.
Сообщение01.03.2016, 08:53 
Заслуженный участник
Аватара пользователя


23/08/07
5493
Нов-ск
mr.tumkan2015 в сообщении #1102824 писал(а):
Можно ли, сделав несколько ходов конями, из положения $1$ получить положение $2$?

Изображение

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

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

 Профиль  
                  
 
 Re: Ходы конями, доска 3x3.
Сообщение04.03.2016, 23:03 


14/10/15
120
Все я понял, извините за то что страшно тупил)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group