Question

Задача №9 Докажите, что у клетчатого многоугольника с площадью 300 и периметром 300 есть сторона, длиной более, чем 1(Многоугольник не имеет дырок, его граница - замкнутая ломаная без самопересечений)​

Answer 1

Предположим, что существует такой многоугольник, но длина любой его стороны в точности 1.

Рассмотрим такой многоугольник. Будем его расклеивать до тех пор, пока не получим 300 квадратов. Посчитаем общее количество расклеиваний: для этого опишем вокруг границы многоугольника "пояс". С одной стороны для расклеивания потребуется отклеить 300*4 сторон (у каждого квадрата 4 стороны), но так мы посчитаем каждое отклеивание дважды (для квадратов с общей стороной), то есть общее количество отклеиваний равно 300*4/2=600. Но отклеиваний без "пояса" меньше (так как граничные отрезки не участвуют в расклейке) - ровно на половину от суммарного количества граничных клеток - то есть на половину периметра. Итак, общее количество расклеек 600-150=450.

Значит, столько же и склеек. Теперь впишем наш многоугольник в прямоугольник (так, чтоб он был полностью в нем и каждой стороны прямоугольника касалась хотя бы одна клетка многоугольника). Будем конструировать многоугольник заново. Докажем, что количество вертикальных склеек четно по индукции. База: Рассмотрим первый столбец. Будем считать количество вертикальных склеек. В первом их нет (иначе бы было две подряд идущих клетки). Во втором столбце - на каждую клетку из первого должна приходиться клетка из второго, да еще клетки между ними - итого 2k+1 клетка, где k - кол-во клеток из первого столбца. Значит вертикальных склеек 2k+1-1=2k - четное число. База доказана. Переход: пусть в некотором столбце четное количество склеек. Тогда в каждой группе из подряд идущих клеток нечетное количество клеток. Тогда каждой такой группе сопоставляется группа из нечетного количества клеток из соседнего столбца (иначе было бы не менее 2 подряд идущих клеток), значит, в каждой такой группе четное количество склеек. Переход доказан.

Теперь докажем, что количество вертикальных и горизонтальных склеек совпадает. Пусть вертикальных В, а горизонтальных Г.

Рассмотрим склейки в столбцах.

Заметим, что на каждую вертикальную склейку требуется не менее одной горизонтальной, поэтому Г≥В. Повернем многоугольник на 90 градусов. Аналогично получим В≥Г, значит, В=Г.

Значит, всего склеек 2В, но В - четное число, значит, общее количество делится на 4, но общее кол-во равно 450, противоречие.

Answer 2

Допустим, у нас есть клетчатый многоугольник с площадью 300 и периметром 300, и нам нужно доказать, что у него есть сторона длиной более 1.

Давайте рассмотрим, что происходит, когда у многоугольника все стороны имеют длину 1. В этом случае, периметр равен сумме длин всех сторон, и площадь многоугольника равна количеству клеток, которые он охватывает. Таким образом, в нашем случае, если все стороны имеют длину 1, периметр и площадь будут равны 300.

Однако, по условию задачи, у нас есть многоугольник с площадью 300 и периметром 300, что означает, что он заполняет ровно 300 клеток и имеет общую длину границы равной 300.

Теперь предположим, что у нашего многоугольника нет сторон длиной более 1. Это значит, что каждая сторона многоугольника состоит из одной клетки, и граница многоугольника представляет собой непрерывную ломаную линию, обходящую каждую клетку.

Давайте посчитаем длину границы такого многоугольника. Каждая сторона имеет длину 1, а у нас всего 300 сторон. Таким образом, суммарная длина границы будет равна 300.

Однако, по условию задачи, общая длина границы многоугольника равна 300. Если бы у многоугольника были только стороны длиной 1, то длина границы такого многоугольника была бы меньше 300.

Таким образом, мы пришли к противоречию: наш многоугольник не может иметь только стороны длиной 1, чтобы удовлетворять условиям задачи. Значит, у него обязательно есть сторона длиной более 1.