Игра "раскраски".

[NL0]

Помогите разобраться, плиз!

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

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

[NL0]

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

[NL0]

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

[12d3]

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

[Dmitriy40]

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

[NL0]

Dmitriy40 в сообщении #1253818 писал(а):

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

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

[Dmitriy40]

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

[grizzly]

12d3 в сообщении #1253816 писал(а):

Центральная симметрия ведет к поражению

А если второй игрок не будет до конца следовать центральной симметрии? Можем красить симметрично до тех пор, пока не останется ровно один маршрут? А потом вспомним, что количество клеток в любом маршруте нечётное.

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

-- 07.10.2017, 00:12 --

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

[12d3]

grizzly в сообщении #1253827 писал(а):

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

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

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Математика (общие вопросы)»
Причина переноса: в соответствующий раздел

NL0 в сообщении #1253813 писал(а):

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

NL0, замечание за бессодержательное сообщение. Имейте терпение, если будет что ответить, Вам обязательно ответят, не засоряйте тему.