Олимпиадная задача: игра на клетчатой сетке с разрезанием верёвочек (8–11 класс)
Задача
Клетчатая прямоугольная сетка m×n связана из верёвочек единичной длины. Двое делают ходы по очереди. За один ход можно разрезать (посередине) не разрезанную ранее единичную верёвочку. Если не останется ни одного замкнутого верёвочного контура, то игрок, сделавший последний ход, считается проигравшим. Кто из игроков победит при правильной игре и как он должен для этого играть?
Решение
В начале игры верёвочек единичной длины было m(n + 1) + n(m + 1) = 2mn + m + n. Это число имеет ту же чётность, что и число m + n. Последний ход в игре разрушает последний замкнутый контур.
Но граница замкнутого контура содержит чётное количество верёвочек единичной длины (см. решение задачи 130310). Выигрышная стратегия для любого игрока состоит в том, чтобы не разрушать последний замкнутый контур, пока есть такая возможность.
Ответ
Если m + n чётно, то выигрывает второй игрок, если m + n нечётно, то первый.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь