Задача 002 — Задачи на Графы

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

Подсказка

Обозначьте узлы за вершины, а базисные отрезки за рёбра. Посчитайте наименьшее количество вершин степени 3.

Решение

Ответ: 4122.

Решение: Рассмотрим граф, вершинами которого являются узлы, а рёбрами — базисные отрезки. Пусть в этом графе $n$ вершин степени $3, m$ вершин степени 4 ; также в нём имеется четыре вершины степени 2.

Посчитаем сумму углов всех прямоугольников. С одной стороны, она равняется $2016 \cdot 360^{\circ}$ . С другой стороны, вершина степени 2 вносит в эту сумму $90^{\circ}$ , вершина степени 3 — $180^{\circ}$ , вершина степени $4-360^{\circ}$ . Следовательно, $2016 \cdot 360^{\circ}=4 \cdot 90^{\circ}+n \cdot 180^{\circ}+m \cdot 360^{\circ}$ , т.е. $n+2 m=4030$ . Пусть количество рёбер в нашем графе равняется $e$ . Тогда $2 e=2 \cdot 4+3 n+4 m$ . Подставляя $4 m=8060-2 n$ , имеем $2 e=8068+n$ . Таким образом, нам нужно доказать, что наименьшее значение, которое может принимать $n$ , равняется 176.

Для начала докажем, что $n \geq 176$ . Проведём через все стороны прямоугольников, не лежащие на сторонах квадрата, прямые. Возьмём какую-нибудь прямую и посмотрим на крайние узлы, оказавшиеся на ней. Соответствующие им вершины, очевидно, не могут иметь степени 2 и 4; значит, они имеют степень 3. Также, очевидно, что никакие две из рассматриваемых вершин не могут совпасть. Следовательно, если $a$ и $b$ — количество вертикальных и горизонтальных прямых соответственно, то вершин степени 3 хотя бы $2(a+b)$ . С другой стороны, эти прямые разбивают квадрат на $(a+1)(b+1)$ прямоугольничков, из которых складываются 2016 прямоугольников из условия. Значит, $(a+1)(b+1) \geq 2016$ . Следовательно, $\quad(a+b+2)^{2} \geq 4(a+1)(b+1) \geq 8064, \quad$ откуда $a+b \geq \sqrt{8064}-2>87, \quad$ а $n \geq 2(a+b) \geq 2 \cdot 88=176$ , что и требовалось.

Теперь приведём пример, в котором $n=176$ . Разделим большой квадрат 44 вертикальными и 44 горизонтальными прямыми на $45^{2}=2025$ маленьких квадратиков. Далее сотрём 9 базисных отрезков, примыкающих к одной из сторон большого квадрата. Тогда прямоугольников разбиения получится ровно 2016, а на каждой из 88 проведённых прямых будет ровно по 2 узла, из которых выходит по 3 базисных отрезка, что и требовалось.