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
11058
Россия, Москва
Представить все пути в виде графа, посчитать "узости", их и закрашивать, оставляя одну нетронутой (вариантов ходов почти всегда много) как ловушку сопернику. Когда-то возникнет ситуация когда других ходов не останется и любой из них ведёт к разрыву связности вершин графа - вот тот игрок и проиграет.
Граф не слишком большой, длина наибольшего пути без циклов ограничена.
Но считать всё это откровенно лень.

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


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

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

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


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

 Профиль  
                  
 
 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 ] 

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



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

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


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

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