Question

В игре "поймай кота" есть доска 9X9 клеток. Изначально кот стоит в центральной клетке доски. За один ход Илья может поставить забор на сторону какой-то клетки, а кот может перейти на соседнюю по стороне клетку, при этом через забор кот прыгать не умеет. Кот победит, если сможет выбраться за пределы доски, а Илья победит, если запрёт кота на доске, чтобы кот никаким образом не смог выйти за пределы доски. Первый ход делает Илья. Кто победит при правильной игре?

Answer 1

Победит Илья.

Вот стратегия:

Сначала Илья ставит 4 забора на места 1, 2, 3 и 4 (см. фото).

За это время кот может максимум подобраться к краю доски.

Затем есть несколько вариантов:

1) Если кот может следующим ходом сбежать, то ставим забор там, где он может сбежать. (Кот не сбежит следующим ходом, т. к. после проставления заборов 1, 2, 3 и 4 у каждой боковой клетки только 1 выход)

2) Если кот не может следующим ходом сбежать, то ставим забор в любом месте сбоку. (Опять же кот не сбежит следующим ходом)

Так повторяем много раз, и вскоре доска будет огорожена, т. к. каждый раз добавлялся забор сбоку.

Answer 2

Данная игра является примером классической математической задачи, известной как "игра ловушки на графе" или "игра на графе с имеющим противника". В таких играх рассматривается граф (в данном случае, доска 9x9), на котором два игрока ходят по определенным правилам.

Для определения победителя в этой игре, давайте рассмотрим ходы каждого игрока и попытаемся выяснить, какой из них имеет выигрышную стратегию.

1. Первый ход Ильи: Илья делает первый ход, и его задача - поставить забор таким образом, чтобы запереть кота и не дать ему выйти за пределы доски.

2. Ходы кота: Кот стоит в центральной клетке доски. Поскольку кот не умеет прыгать через заборы и перемещаться только на соседние клетки по стороне, то на каждом своем ходе он может переместиться только на одну из 8 соседних клеток, которые не заняты забором.

3. Анализ ситуации: При таких условиях доска разделена на несколько компонент связности, и кот не может перейти из одной компоненты связности в другую, если между ними стоит забор. В начале кот находится в центральной клетке, которая является частью одной из компонент связности. Илья, следуя правилам игры, будет стараться создать новые заборы таким образом, чтобы разделить доску на отдельные компоненты связности и изолировать кота в одной из них.

4. Выигрышная стратегия для Ильи: Илья, будучи вторым игроком, имеет выигрышную стратегию при правильной игре. Он может использовать стратегию, основанную на теории графов, чтобы разделить доску на две компоненты связности. Поскольку кот не может перейти между ними, он будет заперт и не сможет выйти за пределы доски.

Таким образом, при правильной игре Илья победит, запирая кота на доске и не давая ему возможности выйти за ее пределы.