|
Дано игральное поле $%n \times n$%, в котором проведена только внешняя граница, а все внутренние линии между квадратами $%1 \times 1$% вытерты. Варя и Таня по очереди проводят границы у клеточек. За один ход разрешается провести ровно один отрезок длины $%1$%, разделяющий две клеточки внутри квадрата, если этот отрезок еще не был проведен. Игра заканчивается, когда после очередного хода все клеточки квадрата разбиваются на две разделенные области, то есть с любой клеточки одной области доски ходами шахматной ладьи нельзя попасть в клеточки, принадлежащие другой области, не пересекая при этом проведенные отрезки. Игрок, после хода которого это случилось, считается проигравшим. Кто из игроков может обеспечить себе победу, если первой делает свой ход Варя? задан 3 Фев '16 20:36 
Роман83 |
|
Это на основы теории связности графов. Представим себе клеточки как вершины графа, а отсутствие границ -- рёбра. Клеток у нас $%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
Роман83 |