2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Игра "раскраски".
Сообщение05.10.2017, 14:10 


13/02/16
129
Помогите разобраться, плиз!

На позициях $a1$ и $8h$ шахматной доски стоят кони. Антон первым закрашивает красным цветом одну клетку, затем Андрей закрашивает синим еще одну клетку. На красные и синие клетки кони ходить не могут. Проигрывает тот, после чьего хода не сможет по доске доскакать до другого. Андрей или Антон сможет заведомо выиграть и как?

Из угла есть две позиции для хода каждого коня. Их перекрывать полностью невыгодно. То есть, кто закроет вторую из позиций для какого-либо из коней, тот проиграл. Вариантов ходов из конкретной клетки поля -- от 2 до 8, в зависимости от положения на доске. Если будет перекрашены все белые (или все черные клетки), то кони встретиться не смогут, так как при ходе меняется черный на белый цвет и наоборот. Почему-то мне кажется, что Андрею выгодно симметрично закрашивать клетки, но у него последний ход будет проигрышным, потому как именно его ход перекроет доступ от одного коня к другому. Это я экспериментально проверил, получилось, что именно так, но как это доказать -- не знаю и поможет ли это?

 Профиль  
                  
 
 Re: Игра "раскраски".
Сообщение05.10.2017, 17:05 


13/02/16
129
Коряво сформулировал, сейчас напишу дословно предпоследнее предложение:
Проигрывает тот, после чьего хода один конь не сможет по доске доскакать до другого. Андрей или Антон сможет заведомо выиграть и как?

 Профиль  
                  
 
 Re: Игра "раскраски".
Сообщение06.10.2017, 22:44 


13/02/16
129
Видимо слишком скучная задача или же я написал настолько все в корне неверно, что и отвечать не хочется?))

 Профиль  
                  
 
 Re: Игра "раскраски".
Сообщение06.10.2017, 22:57 
Заслуженный участник


04/03/09
906
Или задачка кажется читателям достаточно сложной, хотя сама по себе интересная. Мне пока не пришло в голову ни одной хорошей идеи, каких-то простых симметричных стратегий вроде не просматривается. Центральная симметрия ведет к поражению, а симметрия относительно вертикальной (или горизонтальной) прямой не реализуется, ибо незакрашиваемым угловым клеткам сопоставляются закрашиваемые клетки.

 Профиль  
                  
 
 Re: Игра "раскраски".
Сообщение06.10.2017, 23:09 
Заслуженный участник


20/08/14
11065
Россия, Москва
Представить все пути в виде графа, посчитать "узости", их и закрашивать, оставляя одну нетронутой (вариантов ходов почти всегда много) как ловушку сопернику. Когда-то возникнет ситуация когда других ходов не останется и любой из них ведёт к разрыву связности вершин графа - вот тот игрок и проиграет.
Граф не слишком большой, длина наибольшего пути без циклов ограничена.
Но считать всё это откровенно лень.

 Профиль  
                  
 
 Re: Игра "раскраски".
Сообщение06.10.2017, 23:26 


13/02/16
129
Dmitriy40 в сообщении #1253818 писал(а):
Представить все пути в виде графа, посчитать "узости", их и закрашивать, оставляя одну нетронутой (вариантов ходов почти всегда много) как ловушку сопернику. Когда-то возникнет ситуация когда других ходов не останется и любой из них ведёт к разрыву связности вершин графа - вот тот игрок и проиграет.
Граф не слишком большой, длина наибольшего пути без циклов ограничена.
Но считать всё это откровенно лень.

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

 Профиль  
                  
 
 Re: Игра "раскраски".
Сообщение06.10.2017, 23:45 
Заслуженный участник


20/08/14
11065
Россия, Москва
Не, это грубый набросок оптимальной стратегии. А уж кто выиграет - зависит от чётности количества "узких" мест. Из соображений симметрии их количество вроде как должно быть чётным, но не уверен, может существовать и путь проходящий через центр (не доски, скорее графа) и не имеющий симметричного, тогда количество нечётно и выиграет другой игрок. Собственно тогда можно даже не искать все пути, а лишь проверить существует ли такой "непарный" путь.
От ситуаций тут ничего не зависит т.к. речь про оптимальную стратегию, для худшего случая. Любой другой случай/ситуация лишь приведёт к досрочной победе.

 Профиль  
                  
 
 Re: Игра "раскраски".
Сообщение07.10.2017, 00:10 
Заслуженный участник
Аватара пользователя


09/09/14
6328
12d3 в сообщении #1253816 писал(а):
Центральная симметрия ведет к поражению
А если второй игрок не будет до конца следовать центральной симметрии? Можем красить симметрично до тех пор, пока не останется ровно один маршрут? А потом вспомним, что количество клеток в любом маршруте нечётное.

NL0
Вы думали в этом направлении?

-- 07.10.2017, 00:12 --

PS. Это не решение, только мысли вслух.

 Профиль  
                  
 
 Re: Игра "раскраски".
Сообщение07.10.2017, 00:37 
Заслуженный участник


04/03/09
906
grizzly в сообщении #1253827 писал(а):
PS. Это не решение, только мысли вслух.

Это решение. Даже симметрично не надо. Каждый пусть красит что угодно, лишь бы оставался путь от одной угловой клетки до другой. Когда кто-то не сможет закрасить дальше без прерывания пути? Когда все оставшиеся клетки принадлежат единственному пути. А в этом пути нечетное количество клеток. Значит этот "кто-то" - Андрей, он и проигрывает.

 Профиль  
                  
 
 Posted automatically
Сообщение07.10.2017, 11:47 
Супермодератор
Аватара пользователя


20/11/12
5728
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Математика (общие вопросы)»
Причина переноса: в соответствующий раздел
 ! 
NL0 в сообщении #1253813 писал(а):
Видимо слишком скучная задача или же я написал настолько все в корне неверно, что и отвечать не хочется?))
NL0, замечание за бессодержательное сообщение. Имейте терпение, если будет что ответить, Вам обязательно ответят, не засоряйте тему.

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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