Разрезание пирога

[AD]

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

Разрезать пирог радиуса $1$ на $n$ равных по площади частей, минимизируя суммарную длину разрезов.

Очевидная верхняя оценка - $n$: то есть $n$ разрезов длины $1$ от центра по радиусам, как это нормальные люди и делают.

Собственно, я еще не вполне уверенно чувствую себя в плане формализации. То есть понятно, что мы будем оперировать только спрямляемыми кривыми, и поэтому все куски будут измеримыми по Жордану, но все равно как-то не формулируется пока.

Ну да ладно, вот такая штука

[ИСН]

Прозреваю, что начиная с 4 верхняя оценка перестанет быть точной.

[Nilenbert]

Очевидная оценка снизу следует из изопериметрического неравенства - суммарная длина разрезов не меньше $\pi(\sqrt{n}-1)$. Если рассмотреть разрезание на правильные шестиугольники, то получится что-то около $\sqrt{2\sqrt{3}\pi n}+...$(плюс члены меньшего порядка).

[В.О.]

Разрезаем пирог на криволинейные полосы. Записываем условие равенства площадей, варьируем суммарную длину разрезов. Ищем минимум. Получается что-то типа уравнения Эйлера.

Можно немножко обобщить. Пусть пирог заполняет всю плоскость. Вырезать N кусков заданной одинаковой площади минимизируя длинну разрезов.

[AD]

Кстати, а мы требуем связность кусков? Или: можно ли доказать, что несвязные куски всегда неоптимальны? Вообще, достигается ли у нас минимум?

(Оффтоп)

Один дурак столько вопросов задаст ...

[В.О.]

Здесь не нужно задаваться лишними вопросами. Нужно найти решение изопериметрической задачи и проделать аналогичные выкладки. Все получится. Решение уравнения Эйлера ответит на все вопросы.

[ИСН]

Решение уравнения Эйлера в данном случае - это прямая. Но сама по себе она ничего не отвечает. Весь вопрос в том, как её (ну, их) провести.

[В.О.]

ИСН в сообщении #438653 писал(а):

Решение уравнения Эйлера в данном случае - это прямая.

Непонятно. При N=2 это прямая. При бОльших значениях N это , как минимум, несколько прямых. Выразитесь, пожалуйста, точнее.
Нужно выполнить условие равенства площадей. Это даст какие-то соотношения между краевыми условиями.

[ИСН]

Ну ладно: несколько прямых. И ещё, кажется, там могут быть дуги окружностей.

[В.О.]

ИСН в сообщении #439061 писал(а):

Ну ладно.... И ещё, кажется, там могут быть...

Вот спасибо... Теперь все встало на свои места.

-- Чт апр 28, 2011 00:11:11 --

А задача - то изящная. Жалко если никто ничего...

[Circiter]

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

P.S.: Сначала я подумал, что близко к истине будет решение с концентрическими круговыми разрезами, но потом дочитал сообщение топикстартера до строчки о том, что нормальные люди режут пироги не концентрически, а радиально -- стало стыдно. :)

[Nilenbert]

В.О. в сообщении #438441 писал(а):

Можно немножко обобщить. Пусть пирог заполняет всю плоскость. Вырезать N кусков заданной одинаковой площади минимизируя длинну разрезов.

В таком виде это двумерный вариант задачи Кельвина получается. Вот ссылка про задачу Кельвина, там требуется найти такое разбиение пространства на фигуры при котором площадь поверхности минимальна. Задача не решена до сих пор.

На плоскости вроде бы наилучший результат даёт замощение шестиугольниками. Вообще в этой области точных результатов мало, даже контактное число в четырёхмерном пространстве только в 2004 году нашли.

[В.О.]

Да, очень похоже. Но в задаче Кельвина требуется, чтобы пена покрывала все бесконечное пространство без пропусков. А здесь, во-первых, покрывается не бесконечное пространство а только часть, во-вторых, могут быть пропуски. Т.е. задача Кельвина это, физически, замощение пространства. А здесь нужно наградить N человек одинаковыми кусками, затратив минимальные усилия на разрезание.
Исходный вариант ближе к задаче Кельвина. Можно сказать, задача Кельвина для ограниченной фигуры.Вот только структура покрытия будет определяться формой фигуры.

Шестиугольники это наилучшее замощение всей плоскости?

[scwec]

А если максимизировать длину разрезов, типа, а если бы он вез патроны?

[AD]

scwec в сообщении #439963 писал(а):

А если максимизировать длину разрезов

Да тут-то вроде понятно, рисуем даже пусть один маленький неспрямляемый участок - и вот вам бесконечная длина разреза.