2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6 ... 11  След.
 
 Re: Режем торт
Сообщение26.11.2015, 21:21 


14/01/11
2916
Вот ещё решение для $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.$

 Профиль  
                  
 
 Re: Режем торт
Сообщение26.11.2015, 22:57 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Мне теперь тоже кажется, что соображения симметрии могут как-то помогать. Я раньше совсем не понимал, как подбирать эти решения. Теперь вот взял для $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)$ у Вас сохранились? Поделитесь -- всё же это может помочь понять.

 Профиль  
                  
 
 Re: Режем торт
Сообщение27.11.2015, 10:18 


14/01/11
2916
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$. :-)

 Профиль  
                  
 
 Re: Режем торт
Сообщение27.11.2015, 11:06 


21/04/08
208
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

 Профиль  
                  
 
 Re: Режем торт
Сообщение27.11.2015, 11:11 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Режем торт
Сообщение27.11.2015, 11:17 


21/04/08
208
12d3 в сообщении #1077276 писал(а):
А как строго доказать, что в оптимальном разрезании куски будут рациональными со знаменателем $\text{НОК}(1,...,N)$, если весь торт считать за $1$?

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

 Профиль  
                  
 
 Re: Режем торт
Сообщение27.11.2015, 11:29 


14/01/11
2916
А вот и разрезание на $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$.

 Профиль  
                  
 
 Re: Режем торт
Сообщение27.11.2015, 12:35 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
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 разрезов довольно многочисленны и разнообразны.

 Профиль  
                  
 
 Re: Режем торт
Сообщение27.11.2015, 13:28 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Sender
worm2
Спасибо за пояснения. Я теперь понимаю намного лучше и становится ещё интереснее :-)
Sender в сообщении #1077283 писал(а):
Части:
$17,23,25,32,37,38,47,52,53,58,67,68,73,80,82,88.$
Тоже, кстати, идеальный центрально-симметричный вариант.

 Профиль  
                  
 
 Re: Режем торт
Сообщение27.11.2015, 13:46 
Заслуженный участник


12/08/10
1608
Ну центральная симметрия из-за того что
Sender в сообщении #1077283 писал(а):
все группы в первом разбиении состоят ровно из двух кусков

 Профиль  
                  
 
 Re: Режем торт
Сообщение30.11.2015, 11:16 


21/04/08
208
Текущий расклад
$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}$), лучшее чем простейшее разрезание одномерного торта?

 Профиль  
                  
 
 Re: Режем торт
Сообщение30.11.2015, 14:02 
Заслуженный участник


12/08/10
1608
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$.

 Профиль  
                  
 
 Re: Режем торт
Сообщение30.11.2015, 16:56 


21/04/08
208
Null в сообщении #1078279 писал(а):
Можете строго доказать? По-моему, там не все так просто.

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

 Профиль  
                  
 
 Re: Режем торт
Сообщение30.11.2015, 20:12 
Заслуженный участник


04/03/09
906
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$

 Профиль  
                  
 
 Re: Режем торт
Сообщение30.11.2015, 21:19 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 159 ]  На страницу Пред.  1, 2, 3, 4, 5, 6 ... 11  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group