Дано игральное поле $%n \times n$%, в котором проведена только внешняя граница, а все внутренние линии между квадратами $%1 \times 1$% вытерты. Варя и Таня по очереди проводят границы у клеточек. За один ход разрешается провести ровно один отрезок длины $%1$%, разделяющий две клеточки внутри квадрата, если этот отрезок еще не был проведен. Игра заканчивается, когда после очередного хода все клеточки квадрата разбиваются на две разделенные области, то есть с любой клеточки одной области доски ходами шахматной ладьи нельзя попасть в клеточки, принадлежащие другой области, не пересекая при этом проведенные отрезки. Игрок, после хода которого это случилось, считается проигравшим. Кто из игроков может обеспечить себе победу, если первой делает свой ход Варя?

задан 3 Фев '16 20:36

10|600 символов нужно символов осталось
1

Это на основы теории связности графов. Представим себе клеточки как вершины графа, а отсутствие границ -- рёбра. Клеток у нас $%N^2$%, соответственно для связности минимальное число рёбер равно $%N^2 - 1$%. Изначально рёбер у нас $%2 \cdot N \cdot (N-1)$%. Соответственно провести без проигрыша можно$% 2N^2 - 2N - N^2 + 1 = N^2 - 2N + 1 = (N-1)^2.$% Отсюда получается, что выигрывает Вася, если $%N$% чётно, и проигрывает, если нечётно.

ссылка

отвечен 16 Фев '16 22:24

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×33

задан
3 Фев '16 20:36

показан
980 раз

обновлен
16 Фев '16 22:24

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru