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, противоречие.