Олимпиадная задача по комбинаторной геометрии и теории графов для 10–11 класса

  Считая клетки единичными квадратами, оценим сверху периметр фигуры. Ясно, что фигуру можно построить, начав с любой клетки и приклеивая клетки поочередно по одной или нескольким сторонам. С каждой новой клеткой периметр либо увеличивается на 2 (если склейка происходит по одной стороне), либо не увеличивается. Приклеив к исходной  2n – 1  клетку, получим периметр не более  4 + 2(2n – 1) = 4n + 2.

  "Горизонтальная" и "вертикальная" часть периметра, очевидно, чётны, поэтому одна из них (пусть горизонтальная) не больше чем 2n. Тогда вертикальные линии сетки разрезают фигуру не более чем на n прямоугольников ширины 1 (на каждый прямоугольник уходит два единичных отрезка из “горизонтального” периметра).

  Если этих прямоугольников меньше n, разрежем один из них на два. Так будем действовать, пока прямоугольников не станет ровно n.