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

Клетчатый прямоугольник со сторонами 629 и 630 разрезан на несколько квадратов (все разрезы идут по линиям сетки). Какое наименьшее число квадратов с нечетной стороной может оказаться в таком разбиении? Не забудьте объяснить, почему в разбиении не может получиться меньшее число квадратов с нечетной стороной.

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

Комментарии от администратора Комментарии от администратора №1.     Ответ. Два.
Решение. Пример, когда квадратов ровно два: два квадрата со стороной 315 примыкают к стороне прямоугольника длиной 630, а оставшийся прямоугольник $630\times314$ разрезан на квадраты $2\times2$. Покажем, что меньшего числа квадратов с нечетной стороной быть не может. В самом деле, к стороне прямоугольника длиной 629 примыкает хотя бы один квадрат с нечетной стороной, так как составить нечетную сторону из отрезков четной длины невозможно. Продолжим сторону $AB$ этого квадрата, перпендикулярную стороне прямоугольника длиной 629, до пересечения с противоположной стороной прямоугольника в некоторой точке $C$. Отрезок $BC$, продолжающий сторону $AB$, имеет нечетную длину $630-AB$, и потому пересекает еще хотя бы один квадрат нечетной длины.