2014 dxdy logo

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

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




 
 Игра "раскраски".
Сообщение05.10.2017, 14:10 
Помогите разобраться, плиз!

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

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

 
 
 
 Re: Игра "раскраски".
Сообщение05.10.2017, 17:05 
Коряво сформулировал, сейчас напишу дословно предпоследнее предложение:
Проигрывает тот, после чьего хода один конь не сможет по доске доскакать до другого. Андрей или Антон сможет заведомо выиграть и как?

 
 
 
 Re: Игра "раскраски".
Сообщение06.10.2017, 22:44 
Видимо слишком скучная задача или же я написал настолько все в корне неверно, что и отвечать не хочется?))

 
 
 
 Re: Игра "раскраски".
Сообщение06.10.2017, 22:57 
Или задачка кажется читателям достаточно сложной, хотя сама по себе интересная. Мне пока не пришло в голову ни одной хорошей идеи, каких-то простых симметричных стратегий вроде не просматривается. Центральная симметрия ведет к поражению, а симметрия относительно вертикальной (или горизонтальной) прямой не реализуется, ибо незакрашиваемым угловым клеткам сопоставляются закрашиваемые клетки.

 
 
 
 Re: Игра "раскраски".
Сообщение06.10.2017, 23:09 
Представить все пути в виде графа, посчитать "узости", их и закрашивать, оставляя одну нетронутой (вариантов ходов почти всегда много) как ловушку сопернику. Когда-то возникнет ситуация когда других ходов не останется и любой из них ведёт к разрыву связности вершин графа - вот тот игрок и проиграет.
Граф не слишком большой, длина наибольшего пути без циклов ограничена.
Но считать всё это откровенно лень.

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

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

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

 
 
 
 Re: Игра "раскраски".
Сообщение07.10.2017, 00:10 
Аватара пользователя
12d3 в сообщении #1253816 писал(а):
Центральная симметрия ведет к поражению
А если второй игрок не будет до конца следовать центральной симметрии? Можем красить симметрично до тех пор, пока не останется ровно один маршрут? А потом вспомним, что количество клеток в любом маршруте нечётное.

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

-- 07.10.2017, 00:12 --

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

 
 
 
 Re: Игра "раскраски".
Сообщение07.10.2017, 00:37 
grizzly в сообщении #1253827 писал(а):
PS. Это не решение, только мысли вслух.

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

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

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group