Режем торт

[Sender]

Вот ещё решение для $10$ гостей из $27$ кусков.
Части: $252,13,125,123,112,73,77,95,91,67,111,50,52,113,59,15,23,119,105,6,202,157,34,78,126,127,115$.
Разбиения:
$119+6+127=123+77+52=112+73+67=111+15+126=95+157=113+105+34=252=13+125+91+23=50+202=59+78+115,$

$95+59+126=52+113+115=125+50+105=119+34+127=252+13+15=202+78=73+67+111+23+6=112+77+91=123+157,$

$252+13+50=91+67+157=112+119+6+78=73+59+23+34+126=125+123+52+15=113+202=95+105+115=77+111+127,$

$123+111+126=91+67+202=252+13+95=113+15+105+127=73+52+157+78=125+59+23+119+34=112+77+50+6+115,$

$77+95+91+157=125+123+113+59=252+13+23+6+126=50+15+119+202+34=73+105+127+115=112+67+111+52+78.$

[grizzly]

Мне теперь тоже кажется, что соображения симметрии могут как-то помогать. Я раньше совсем не понимал, как подбирать эти решения. Теперь вот взял для $F(5)$ и попробовал разложить 60 примерно так, как это вышло в $F(7)$. Видно, что совсем так не получается. Отложил в сторону одну 12. Остальные расставил из соображений симметрии:
$1, 3, 4, 6, 6, 8, 9, 11, \qquad 12$
Сразу видно, что такое решение уже было выше у sng1. Ничего нового. Симметрия тоже перекошена.

Потом попытался найти для $F(6)$ (раньше я полчаса подумал и ничего путного даже близко не сообразил). Теперь не долго думая, и чтоб не слишком нарушать симметрию, отделил от 12 двоечку и от 11 единичку. Получил:
$1, 1, 2, 3, 4, 6, 6, 8, 9, 10, 10$
Получилось. Это уже новое решение, осознанно придуманное за пару минут на основе предыдущего. Симметричность в нём всё ещё скособочена, но какая-никакая намечается.

Может, кому не сложно будет выложить здесь все возможные решения (только итоговые последовательности, не варианты разбиений) для малых $N$? Я надеюсь, что они решаются с готовыми программами очень быстро и этих решений не слишком много.
worm2 -- а другие решения для $F(7)$ у Вас сохранились? Поделитесь -- всё же это может помочь понять.

[Sender]

grizzly в сообщении #1077168 писал(а):

Симметричность в нём всё ещё скособочена, но какая-никакая намечается.

Полной симметричности в этом случае и не может быть. Если средняя часть $x$, а остальные симметричны относительно неё, то сумма всех в случае $11$ слагаемых составит $11x$, в то время как $420$ на $11$ не делится, т.е. $x$ не может быть целым.
Вот парочка конфигураций из $11$ частей:
$1,1,2,3,5,5,7,7,9,10,10$,
$1,2,2,3,5,5,7,7,8,10,10$,
$1,1,3,3,5,5,7,7,9,9,10$.

[sng1]

Cимметрия разностей. Порция гостя при $N$ гостях состоит из двух частей. Похоже это мало помогает, или нет?
0 0 1 1
0 0 1 1 2 2
0 0 1 1 2 2 3 3
0 0 1 1 1 3 3 3
0 1 3 4 5 7 8 9 11 12
0 1 3 4 6 6 8 9 11 12
0 3 4 5 6 6 7 8 09 12
0 1 1 3 3 5 5 7 07 09 09 10
0 2 3 4 4 5 5 6 06 07 08 10

Здесь пока не видно симметрии
1 1 2 3 5 5 7 7 9 10 10
1 2 2 3 5 5 7 7 8 10 10

[12d3]

А как строго доказать, что в оптимальном разрезании куски будут рациональными со знаменателем $\text{НОК}(1,...,N)$, если весь торт считать за $1$?

[sng1]

12d3 в сообщении #1077276 писал(а):

А как строго доказать, что в оптимальном разрезании куски будут рациональными со знаменателем $\text{НОК}(1,...,N)$, если весь торт считать за $1$?

Если весь торт считать $\text{НОК}(1,...,N)$, и куски не целые,то куски можно объединить и уменьшить их число.

[Sender]

А вот и разрезание на $16$ кусков для $8$ гостей.
Части:
$17,23,25,32,37,38,47,52,53,58,67,68,73,80,82,88.$
Разбиения:
$23+82=80+25=88+17=32+73=52+53=38+67=68+37=47+58,$

$23+80+17=25+37+58=88+32=52+68=73+47=82+38=53+67,$

$82+58=88+52=25+68+47=23+80+37=73+67=17+32+53+38,$

$53+68+47=23+82+25+38=80+88=73+37+58=17+32+52+67.$

Продуктивным оказалось предположение о том, что все группы в первом разбиении состоят ровно из двух кусков.
Кстати, тем самым верхняя оценка для $F(9)$ автоматически понижается до $22$.

[worm2]

grizzly в сообщении #1077168 писал(а):

worm2 -- а другие решения для $F(7)$ у Вас сохранились? Поделитесь -- всё же это может помочь понять.

Я искал решения для $F(7)=13$. Не нашёл. Для $F(7)=14$ всех решений не искал.
Ближе всего подошли два варианта, которым не хватало всего одного разреза:
$1, 9, 11, 15, 21, 25, 35, 39, 45, 49, 51, 59, 60$
$3, 7, 8, 17, 27, 29, 31, 33, 43, 52, 53, 57, 60$
Например, первый вариант даёт всего четыре шестых части:
$1+9+60=11+59=21+49=25+45$, а остатки $15, 35, 39, 51$ невозможно разделить на 2 равные части. Можно довести его до решения из 14 разрезов, но разными способами.

Но это не значит, что есть всего два таких варианта. В ходе предварительной оптимизации отсекались некоторые неподходящие варианты. Я даже помню, что одна из предыдущих версий, хуже оптимизированных, выдала больше вариантов с дефицитом в 1 разрез, но не помню точно, сколько их было, вроде бы, не больше шести.
Кроме того, возможна ситуация, что не хватает одного разреза для разделения на 6 частей, одного — для разделения на 5 и одного — для разделения на 4 части, всего трёх разрезов, но при этом всего один разрез позволяет решить все три проблемы.
Это я к тому пишу, что, скорее всего, решения из 14 разрезов довольно многочисленны и разнообразны.

[grizzly]

Sender
worm2
Спасибо за пояснения. Я теперь понимаю намного лучше и становится ещё интереснее

Sender в сообщении #1077283 писал(а):

Части:
$17,23,25,32,37,38,47,52,53,58,67,68,73,80,82,88.$

Тоже, кстати, идеальный центрально-симметричный вариант.

[Null]

Ну центральная симметрия из-за того что

Sender в сообщении #1077283 писал(а):

все группы в первом разбиении состоят ровно из двух кусков

[sng1]

Текущий расклад
$F(1:6)=(1, 2, 4, 6, 9, 11)$ (sng1, Null).
$F(7:8)=(14, 16)$ (Sender, worm2). При $N=7$ или $N=8$, если кусков $2N-1$, то веса кусков пропорциональны $\frac{1}{N(N-1)x}$ (из первых двух разбиений), $\frac{1}{N(N-1)(N-2)}$ (из третьего), и не удовлетворяют четвертому.
$F(9:14) \leq (22, 27, 37, 43, 55, 62)$ (Sender, 12d3).
$F(15:\dots) \leq (72, \dots)$ (Null, Otta). Проcтейшее разрезание одномерного торта.
Может кто-то предложит простое разрезание $J$-мерного торта ($J \in \mathbb{N}$), лучшее чем простейшее разрезание одномерного торта?

[Null]

sng1 в сообщении #1078248 писал(а):

При $N=7$ или $N=8$, если кусков $2N-1$, то веса кусков пропорциональны $\frac{1}{N(N-1)x}$ (из первых двух разбиений), $\frac{1}{N(N-1)(N-2)}$ (из третьего), и не удовлетворяют четвертому.

Можете строго доказать? По-моему, там не все так просто.

sng1 в сообщении #1078248 писал(а):

$F(15:\dots) \leq (72, \dots)$ (Null, Otta). Простейшее разрезание одномерного торта.

Тут можно вычесть 1(и даже больше): Пример для $N=7$: Рассмотрим куски $\frac{1}{6},\frac{1}{30},\frac{23}{210},\frac{2}{35},\frac{1}{7}$ и остальное- 6 кусков,
Возьмем из них 2 раза $\frac{1}{7}$ и сделаем еще 4 разреза на остальное(включая не использованные $\frac{1}{6},\frac{2}{35}$),
Возьмем из них 2 раза $\frac{1}{6}$ и сделаем еще 3 разреза на остальное,
Возьмем из них 2 раза $\frac{1}{5}$ и сделаем еще 2 разреза на остальное,
Взяв разрезание на 6 частей сделаем еще 2 разреза для $\frac{1}{4}$. Итого 17 кусков. Так можно делать для кусков $\frac{1}{N},\frac{1}{N-1}$ и $1/ $ простое число между $[\frac{N}{2}]+1$ и $N-2$.

[sng1]

Null в сообщении #1078279 писал(а):

Можете строго доказать? По-моему, там не все так просто.

Доказать пока не могу, в прежнем доказательстве поспешил с выводом, что $x=(N-2)$.

[12d3]

12d3 в сообщении #1077276 писал(а):

А как строго доказать, что в оптимальном разрезании куски будут рациональными со знаменателем $\text{НОК}(1,...,N)$, если весь торт считать за $1$?

Удивительно, но есть контрпример к этому утверждению.
При $N=5$, если считать весь торт за 120 (вдвое больше НОКа), то куски такие:
$1,5,7,11,13,17,19,23,24$
$1+23=7+17=13+11=19+5=24$
$23+7=17+13=11+19=5+24+1$
$17+23=11+5+24=1+7+13+19$

[Sender]

Да, это тяжёлый удар. К счастью, он никак не вредит доказательству Null для $F(N)\geqslant 2N-1$ при $N>4$, а вот с доказательством оптимальности $14$-кускового разрезания для $7$ гостей могут возникнуть проблемы.