Математикадан Эйлер олимпиадасы, 2013-2014 оқу жылы, Дистанциялық кезеңнің 3-ші туры

Екі ойыншы келесі ойынды ойнайды. Басында оларда өлшемі ${m\times n}$ болатын тіктөртбұрышты парақ қағаз бар, бұл жерде $m$ және ${n - 1}$-ден үлкен натурал сандар. Олар кезектесіп жүреді. Әр жүрісте ойыншы тіктөртбұрышты біреуінің ауданы 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.