Из n правильных шестиугольников со стороной 1 сделали многоугольник на плоскости, склеивая шестиугольники по сторонам. Любые два шестиугольника либо имеют ровно одну общую сторону, либо вообще не имеют общих точек. Внутри многоугольника нет дыр. При этом у каждого шестиугольника хотя бы одна сторона лежит на границе многоугольника. Какой наименьший периметр может иметь многоугольник при данных условиях?
Легко понять, что если точка является концом для хотя бы одной стороны шестиугольника, она является концом для двух или для трёх сторон: больше, чем 3, быть не может потому что все углы равны 120°.
Давайте немного порисуем. Представим себе, что в каждую точку, являющуюся концом для трёх сторон шестиугольника, мы поставили точку красным фломастером. А каждый путь по сторонам шестиугольников от красной точки до красной точки мы обвели синим фломастером. Таким образом, синие линии идут по сторонам шестиугольников и через вершины, из которых выходит только две стороны (иными словами, которые являются вершинами ровно для одного шестиугольника). Заметим, что синие линии не пересекаются иначе, чем в своих концах, являющихся красными точками. Легко понять, что если точка является концом для хотя бы одной стороны шестиугольника, она является концом для двух или для трёх сторон: больше чем 3 быть не может потому что все углы равны 120°.
Рис. 1: Пример многоугольника, сделанного из шестиугольников.
Таким образом, мы получили изображение мультиграфа на плоскости. Для него верна формула Эйлера F − E + V = 2, где F, E, V — количества граней, рёбер и вершин соответственно. Поскольку все вершины имеют степень 3, 3V = 2E. Кроме того F = n + 1, поскольку это все шестиугольники и внешняя грань. Из этих трёх уравнений выводится E = 3n − 3. Пройдём по внешнему циклу. При этом мы шли по всем n шестиугольникам, значит, при n > 1 не менее чем n раз меняли шестиугольник, по которому идем (внимание: этот утверждение неверно, если n = 1: так и ходили по одному шестиугольнику, ни разу его не поменяв). Значит, во внешнем цикле не менее n ребер, значит, в остальном графе не больше 2n − 3 рёбер. Каждое из них состоит ровно из одного отрезка, бывшего стороной для двух шестиугольников, поскольку внутри многоугольника не может быть точек, являющихся концами ровно для двух отрезков сторон. Значит, внутри не больше 4n − 6 сторон шестиугольников, склеенных по парам, значит, на границе лежит не менее 2n + 6 сторон.
Ответ: 2n + 6 при n ≥ 2, 6 при n = 1