Question

Клетчатая прямоугольная сетка m x n связана из веревочек единичной длины. Двое делают ходы по очереди. За один ход можно разрезать (посередине) не разрезанную ранее единичную веревочку. Если не останется ни одного замкнутого веревочного контура, то игрок, сделавший последний ход, считается проигравшим. Кто из игроков победит при правильной игре и как он должен для этого играть? 

Answer 1

При правильной игре перед последним ходом все верёвочки, не входящие в  едниственный оставшийся контур, будут перерезаны. (Пусть это не так, тогда игрок, делающий последний ход, может не трогать какой-то контур, но это означает, что его ход не последний, так как он не проиграл после его совершения). Заметим, что каждый замкнутый контур состоит из чётного числа верёвочек (узлы сетки можно покрасить в чёрный и белый цвета так, что чёрный узел соединён только с белыми и наоборот, тогда, если мы будем обходить контур, чёрные и белые узлы будут чередоваться, их будет поровну, тогда и верёвочек будет чётное число). Значит, если изначально число верёвочек было чётно, то перед последним ходом их останется чётное количество, то есть, будет сделано чётное число ходов. Это означает, что последний ход сделает первый игрок, и он проиграет. Аналогично, если число верёвочек было нечётно, то проиграет второй игрок. Заметим, что в прямоугольнике m*n всего m(n+1)+n(m+1) верёвочек,  m(n+1)+n(m+1)=2mn+m+n, это число чётно, когда m+n чётно и нечётно, когда m+n нечётно. Значит, если m+n чётно, то выиграет второй игрок, а если нечётно, то первый.