Олимпиада имени Леонарда Эйлера
2013-2014 учебный год, III тур дистанционного этапа


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

Комментарий/решение:

Комментарии от администратора Комментарии от администратора №1.     Ответ. Если площадь исходного прямоугольника нечётна, выигрывает первый, если чётна — второй.
Решение.
Лемма. Если площадь $S$ прямоугольника не меньше 3, и обе его стороны длиннее 1, то, отрезав от него единичный прямоугольник параллельно меньшей стороне, мы получим прямоугольник, у которого обе стороны также длиннее 1.
Доказательство. У прямоугольника, площадь которого не меньше 3, длина наибольшей стороны больше 1,5 — иначе его площадь меньше 1,52 = 2,25. Если мы отрежем от него прямоугольник площади 1 параллельно меньшей стороне, большая сторона уменьшится на свою $1/S$-ую часть, то есть не больше, чем на треть своей длины. Значит, её длина останется больше 1. Длина стороны, параллельно которой был проведён разрез, не изменится. Лемма доказана.
Итак, играющие могут делать не ведущие к немедленному проигрышу ходы (например, параллельно меньшей стороне оставшегося прямоугольника), пока площадь оставшейся части не окажется равной 2. Это случится после $mn-2$ ходов. Если это число чётно, очередь хода будет за первым, если нечётно — за вторым, и тот, кто делает этот ход, проигрывает. В самом деле, после этого хода останется прямоугольник площади 1. Если обе его стороны равны 1, то это квадрат $1 \times 1$, а в остальных случаях меньшая его сторона короче 1.