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