Режем торт

[sng1]

Найти минимальное число частей $F(N)$, на которое можно разрезать торт, так чтобы торт можно было разделить поровну между любым числом гостей от $1$ до $N$.

Наверняка известная задача, но что-то не могу решить и ссылок на нее не попалось.
Может, кто подскажет какую ссылку?

Lia: название темы изменено без согласования с автором

[sng1]

$F(1)=1$; $F(2)=2$; $F(3)=4$; $F(4)=6$;
$F(5)=9$; $F(6)=11$; $F(7)=21$(?)
Судя по числам похоже на http://oeis.org/A220768

[Null]

Ваша последовательность должна быть меньше http://oeis.org/A002088. Как вы получили что $F(5)=9$?

[sng1]

$F(5) \leq 9$:
$(12, \; 3+9, \; 11+1, \; 8+4, \; 6+6)/60=(12, \; 12, \; 12,\; 12,\; 12)/60$
нетрудно показать, что не существует разбиения на 8 или меньше кусков, т.е. $F(5)=9$

[Null]

$F(7) \leq 18$
Пусть торт размера $420$:
60 10 14 21 15 20 28 12 30 30 12 28 20 15 21 14 10 60
нужные доли получаются просто беря числа по порядку.
Например $84=\frac{420}{5}$:

$$60+10+14=21+15+20+28=12+30+30+12=28+20+15+21=14+10+60$$

Так же можно показать что $F(n)\ge 2n-1$ при $n\ge 5$

Если приведете пример для 6, получим точный ответ.

[sng1]

$F(6) \leq 11$ :
$(10, \; 8+2,\; 7+3, \; 5+5, \; 10, \; 4+4+2)/60=(10, \; 10, \; 10, \; 10, \; 10, \; 10)/60$
$(10+2, \; 8+4, \; 7+5, \; 10+2, \; 5+4+3)/60=(12, \; 12, \; 12, \; 12, \; 12)/60$
$(10+5, \; 8+7, \; 10+5, \; 4+4+2+3+2)/60=(15, \; 15, \; 15, \; 15)/60$

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Lia]

Тема перемещена из форума «Карантин» в форум «Математика (общие вопросы)»

[Null]

$F(7) \leq 17$

Один разрез можно сэкономить на равенстве $105+84+60=84+60+105=84+21+39+45+60$ - последнее это общие разрезы

[12d3]

Небольшое общее утверждение: $F(N)-F(N-1) \le N-d(N)$, где $d(N)$ - наибольший делитель $N$, меньший самого $N$.

[Otta]

$F(N)\le\sum_{k=1}^N\varphi(k)$, где $\varphi$ - мультипликативная функция Эйлера.

A002088 (отбрасываем первый элемент)
A092249

Осталось обосновать минимальность.

Хотя вроде многовато для минимума, для пятерки не достигается. :(

[sng1]

$F(7) \leq 15$:
$(60, 5+5+50, 34+26, 15+5+40, 44+16, 54+6, 36+24)/420=(1,1,1,1,1,1,1)/7$
$(60+5+5, 50+15+5, 34+36, 6+24+40, 44+26, 54+16)/420=(1,1,1,1,1,1)/6$
$(60+24, 50+34, 16+36+6+26, 44+40, 54+15+5+5+5)/420=(1,1,1,1,1)/5$
$(60+40+5, 50+34+16+5, 26+5+24+44+6, 54+15+36)/420=(1,1,1,1)/4$

Легко показать, что $F(N) \geq 2N-2$, из того что при делении торта между $N-1$ гостями, порция гостя составная.
А как показать, что $F(N) \geq 2N-1$, при $N \geq 5$ ?

[Null]

Построим двудольный граф $M_{N,N-1}$. Вершины 1 доли содержат группы размера $\frac{1}{N}$, второй группы размера $\frac{1}{N-1}$. На ребре $AB$ расположим куски лежащие одновременно в группах соответствующих $A$ и $B$. Ребер в нем меньше чем кусков всего в разрезании. Граф связен, иначе, взяв 1 компоненту связности c $k_1$ и $k_2$ вершинами в долях и посчитав 2 способами сумму весов ребер, получим что $\frac{k_1}{N}=\frac{k_2}{N-1}$. Значит в графе как минимум $N+N-1-1$ ребер.

Так что если кусков $2N-2$, то граф - дерево и на каждом ребре по 1 куску. Тогда веса всех кусков определяются по графу однозначно(Вес ребра-листа дерева определяется однозначно, можно его выкинуть, одновременно уменьшив суммарный вес вершины-группы к которой оно прицеплено) и значит они все имеют вид $\frac{s}{N(N-1)}$.

Но попытавшись разделить на $N-2$ группы получим что $\frac{1}{N-2}=\frac{S}{N(N-1)}$, а значит
$N(N-1)\vdots (N-2)$, что равносильно $2\vdots (N-2)$, а значит $N\le 4$

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

$F(7) \leq 15$

Как вы строите эти примеры?

Очень похоже что ответ A054519

[sng1]

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

[Null]

Пусть $l=\left[\frac{N}{2}\right]+1$
Рассмотрим систему уравнений:
$X_{i_l,i_{l+1},\dots,i_{N}}$, где $i_k=1..k$ - переменные.

$$\begin{cases} \sum_{i_k=s} X_{i_l,i_{l+1},\dots,i_{N}}=\sum_{i_k=s+1} X_{i_l,i_{l+1},\dots,i_{N}},&\text{где $k=l..N, s=1..k-1$;}\\ \sum X_{i_l,i_{l+1},\dots,i_{N}}=1& \end{cases}$$

Матрица размера $1+\frac{N+l-1}{2}(N-l)\times \frac{N!}{(l-1)!}$ (без столбца свободных членов)
Ответ будет равен рангу этой матрицы$-2$, а пример надо выбирать из тех решений где все переменные $\ge 0$ и максимальное количество из них равно 0.

Это требует проверки.