2014 dxdy logo

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

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





Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5 ... 8  След.
 
 Режем торт
Сообщение11.11.2015, 13:47 


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

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

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

 Профиль  
                  
 
 Re: Найти минимальное число частей
Сообщение11.11.2015, 16:13 


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

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


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

 Профиль  
                  
 
 Re: Найти минимальное число частей
Сообщение11.11.2015, 16:59 


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

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


12/08/10
937
$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, получим точный ответ.

 Профиль  
                  
 
 Re: Найти минимальное число частей
Сообщение12.11.2015, 11:41 


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

 Профиль  
                  
 
 Posted automatically
Сообщение12.11.2015, 11:43 
Модератор


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

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

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

 Профиль  
                  
 
 Posted automatically
Сообщение12.11.2015, 12:22 
Модератор


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

 Профиль  
                  
 
 Re: Найти минимальное число частей
Сообщение12.11.2015, 16:04 
Заслуженный участник


12/08/10
937
$F(7) \leq 17$

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

 Профиль  
                  
 
 Re: Найти минимальное число частей
Сообщение12.11.2015, 16:43 
Заслуженный участник


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

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


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

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

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

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

 Профиль  
                  
 
 Re: Найти минимальное число частей
Сообщение13.11.2015, 11:02 


21/04/08
203
$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$ ?

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


12/08/10
937
Построим двудольный граф $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

 Профиль  
                  
 
 Re: Найти минимальное число частей
Сообщение13.11.2015, 15:40 


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

 Профиль  
                  
 
 Re: Найти минимальное число частей
Сообщение13.11.2015, 16:37 
Заслуженный участник


12/08/10
937
:?: Пусть $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.

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

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

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



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

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


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

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