Увидеть граф (переформулировки)

Первое решение.

Сопоставим многоугольнику граф: вершины - клетки, ребра будем проводить между соседними клетками. У каждой клетки 4 стороны, но стороны, которые соприкасаются с соседними клетками в многоугольнике, не учитываются в периметре. Значит, не учитываются те и только те стороны клеток, которым соответствуют ребра в графе (две стороны между соседними клетками соответствуют одному ребру). Граф на вершинах связен (так как у нас связная фигура), следовательно, ребер в нем хотя бы Значит, периметр многоугольника не больше Такой периметр достигается в прямоугольнике

Второе решение.

Оценку можно доказать по-другому. По формуле Пика площадь многоугольника равна , где количество узлов сетки внутри многоугольника, количество узлов сетки на его границе. Поскольку контур многоугольника идет по линиям сетки, то его периметр равен количеству узлов сетки, то есть . Поскольку , то