Тема Клетчатые задачи

Формула Пика

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела клетчатые задачи

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#40722Максимум баллов за задание: 7

На клетчатой бумаге нарисован многоугольник площади $n$ клеток. Его контур идет по линиям сетки. Каков наибольший периметр многоугольника? Сторона клетки равна $1.$

Показать ответ и решение

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

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

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

Оценку можно доказать по-другому. По формуле Пика площадь многоугольника равна $B A+ 2-− 1$ , где $A−$ количество узлов сетки внутри многоугольника, $B−$ количество узлов сетки на его границе. Поскольку контур многоугольника идет по линиям сетки, то его периметр равен количеству узлов сетки, то есть $B$ . Поскольку $A+ B2-− 1 =n$ , то

B = 2n +2 − 2A ≥2n+ 2

Ответ:

$2n+ 2.$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#77036Максимум баллов за задание: 7

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

Показать ответ и решение

Рассмотрим центры клеток доски. Они образуют сетку со стороной $1.$ Тогда ломанная из условия является целым многоугольником, у которого на границе $8⋅8= 64$ узлов, а внутри узлов нет. По формуле Пика искомая площадь равна $64∕2+ 0− 1= 31.$

Ответ:

$31$

Ошибка.
Попробуйте повторить позже

Задача 3#77038Максимум баллов за задание: 7

Докажите, что существует целый треугольник без точек на границе с площадью, большей $100,$ внутри которого лежит ровно $100$ целых точек.

Показать доказательство

Рассмотрим треугольник с вершинами в точках $(0,0),(1,0),(2,201).$ Заметим, что его площадь равна $1⋅203∕2 =100.5.$ Легко проверить, что на его границе нет целых точек, кроме вершин. Тогда по формуле Пика получаем, что количество внутренних точек равно $100.5− 3∕2+1 =100.$