2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7, 8 ... 11  След.
 
 Re: Режем торт
Сообщение04.12.2015, 10:43 
Заслуженный участник


12/08/10
1609
Sender в сообщении #1079339 писал(а):
Если при $n=10$ взять объём торта равным $2520$, при разбиении на $8$ частей $b_jx=315-28a_j$, что означает нечётность либо полуцелость $x$.
При разбиении на $7$ частей имеем $b_jx=360-28a_j$. Правая часть делится на $4$, значит, $x$-чётное.

Эти $b_j$ - разные. А так похоже на правду.

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


14/01/11
2916
Разумеется, разные. Главное, что $x$ один.

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


21/04/08
208
Можно ли доказать рациональность кусков в оптимальном разрезании, или хотя бы существование оптимального разрезания с рациональными кусками?

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


12/08/10
1609
В оптимальном разрезании все куски рациональны.
1. Разрезание - система уравнений с рациональными коэффициентами, где переменные - размеры кусков. а уравнения - группы кусков размера $\frac{1}{k}$.
2. Эта система уравнений в случае оптимального разрезания имеет единственное решение, иначе 1 переменную можно обнулить, оставив остальные неотрицательными.
3. Ну и все: из метода Гаусса следует что все неизвестные рациональны.

 Профиль  
                  
 
 Re: Режем торт
Сообщение05.12.2015, 12:49 


21/04/08
208
Null в сообщении #1079703 писал(а):
имеет единственное решение, иначе 1 переменную можно обнулить, оставив остальные неотрицательными.

1. Это можно сделать всегда?
2. А что можно сказать о знаменателе куска в виде несократимой дроби в оптимальном разрезании?

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


12/08/10
1609
1.Пусть $\vec{a},\vec{a}+\vec{b}$ - 2 разных вектора решений($a_i>0$). $l_i=\frac{a_i}{b_i}$, $l$ - минимальное по модулю из них(пропускаем те где деление на 0). Тогда $\vec{c}=\vec{a}-l \vec{b}$ - искомое решение $c_i=a_i-l b_i\ge |a_i|-|l| |b_i|\ge |a_i|-|l_i| |b_i| =0$, так же очевидно что 1 из переменных обнулилась.
2. Не больше A003433($F(N)$) (существует(неизвестная) система из $F(N)$ уравнений с коэффициентами и свободными членами из $\{-1,0,+1\}$)

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


01/08/06
3049
Уфа
12d3 в сообщении #1078382 писал(а):
Удивительно, но есть контрпример к этому утверждению.
При $N=5$, если считать весь торт за 120 (вдвое больше НОКа), то куски такие:
$1,5,7,11,13,17,19,23,24$

Это единственное такое решение из восемнадцати возможных.
У остальных семнадцати все куски кратны $1/60$ торта.
(я пока со своим подходом добрался только до полного списка решений для $N=5$).

-- Сб дек 05, 2015 17:15:28 --

Остальные решения:
Код:
1, 2, 3, 3, 7, 8, 12, 12, 12
1, 2, 3, 4, 6, 9, 11, 12, 12
1, 2, 3, 4, 7, 8, 11, 12, 12
1, 2, 3, 5, 6, 9, 10, 12, 12
1, 2, 3, 5, 7, 8, 10, 12, 12
1, 2, 4, 5, 7, 8, 10, 11, 12
1, 3, 3, 4, 5, 9, 11, 12, 12
1, 3, 3, 4, 6, 8, 11, 12, 12
1, 3, 3, 5, 7, 8, 9, 12, 12
1, 3, 4, 5, 7, 8, 9, 11, 12
1, 3, 4, 6, 6, 8, 9, 11, 12
2, 3, 3, 4, 7, 8, 9, 12, 12
2, 3, 3, 5, 6, 7, 10, 12, 12
2, 3, 4, 5, 7, 8, 9, 10, 12
2, 3, 5, 6, 6, 7, 9, 10, 12
3, 3, 4, 5, 6, 7, 8, 12, 12
3, 4, 5, 6, 6, 7, 8, 9, 12

 Профиль  
                  
 
 Re: Режем торт
Сообщение05.12.2015, 17:51 
Модератор
Аватара пользователя


11/01/06
5660
grizzly в сообщении #1077168 писал(а):
worm2 -- а другие решения для $F(7)$ у Вас сохранились? Поделитесь -- всё же это может помочь понять.

Решение для $N=7$ с 14 кусками, найденное с помощью MILP-солвера CPLEX:
Код:
[2, 3, 9, 10, 13, 23, 27, 33, 37, 41, 47, 57, 58, 60]

Сейчас ищется решение с 13 кусками.

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


01/08/06
3049
Уфа
Мой подход оказался слишком неэффективным. Для $N=7$ он уже выдохнется.
Но $N=6$ с трудом осилил. Вот все 32 решения, из которых первые 28 с кусками, кратными $1/60$, а последние 4 — кратными $1/120$:
Код:
1, 1, 2, 2, 4, 5, 7, 8, 10, 10, 10
1, 1, 2, 2, 5, 5, 7, 7, 10, 10, 10
1, 1, 2, 3, 4, 5, 7, 8, 9, 10, 10
1, 1, 2, 3, 4, 6, 6, 8, 9, 10, 10
1, 1, 2, 3, 5, 5, 7, 7, 9, 10, 10
1, 1, 3, 3, 5, 5, 7, 7, 9, 9, 10
1, 2, 2, 2, 3, 5, 6, 9, 10, 10, 10
1, 2, 2, 2, 3, 5, 7, 8, 10, 10, 10
1, 2, 2, 2, 5, 5, 6, 7, 10, 10, 10
1, 2, 2, 3, 3, 5, 7, 8, 9, 10, 10
1, 2, 2, 3, 4, 4, 7, 8, 9, 10, 10
1, 2, 2, 3, 4, 5, 6, 8, 9, 10, 10
1, 2, 2, 3, 4, 5, 7, 8, 8, 10, 10
1, 2, 2, 3, 4, 6, 6, 7, 9, 10, 10
1, 2, 2, 3, 5, 5, 6, 7, 9, 10, 10
1, 2, 2, 3, 5, 5, 7, 7, 8, 10, 10
1, 2, 2, 4, 5, 5, 6, 7, 8, 10, 10
1, 2, 3, 3, 5, 5, 7, 7, 8, 9, 10
1, 2, 3, 4, 4, 6, 6, 7, 8, 9, 10
1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10
2, 2, 2, 3, 3, 5, 6, 7, 10, 10, 10
2, 2, 2, 3, 4, 5, 5, 7, 10, 10, 10
2, 2, 3, 3, 4, 5, 6, 7, 8, 10, 10
2, 2, 3, 3, 5, 5, 6, 7, 7, 10, 10
2, 2, 3, 4, 4, 5, 5, 7, 8, 10, 10
2, 2, 3, 4, 5, 5, 6, 6, 7, 10, 10
2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 10
2, 3, 4, 4, 5, 5, 6, 6, 7, 8, 10

1, 3, 4, 5, 7, 11, 13, 17, 19, 20, 20
1, 3, 4, 7, 9, 11, 13, 15, 17, 20, 20
1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 20
3, 4, 5, 7, 9, 11, 13, 15, 16, 17, 20

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


12/08/10
1609
maxal в сообщении #1079752 писал(а):
Сейчас ищется решение с 13 кусками.


Вроде доказали уже что не хватит.

 Профиль  
                  
 
 Re: Режем торт
Сообщение05.12.2015, 19:20 
Модератор
Аватара пользователя


11/01/06
5660
Null в сообщении #1079759 писал(а):
maxal в сообщении #1079752 писал(а):
Сейчас ищется решение с 13 кусками.


Вроде доказали уже что не хватит.

Если вы имеете в виду это:
12d3 в сообщении #1079021 писал(а):
Предположим, что можно разрезать на 13 кусков. Весь торт считаем за 420.

то уже сразу непонятно, почему ограничиваемся лишь 420 составляющими. Кроме того, "проверить электроникой" доказательство не помешает.

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


12/08/10
1609
У него в доказательстве ни где не используется что куски целые. Но там доказано что все куски имеют 1 из видов $10a_i+x,10a_i-x,10a_i$. а потом доказывается что $x$ тоже хороший.

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


14/01/11
2916
maxal в сообщении #1079752 писал(а):
Решение для $N=7$ с 14 кусками, найденное с помощью MILP-солвера CPLEX
:

Было бы любопытно оценить возможности вашего метода в прояснении ситуации с $9$ гостями. Если он за разумное время найдёт решение с $22$ кусками, которое заведомо существует, можно попытаться найти решение с $21$ куском.

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


14/01/11
2916
worm2 в сообщении #1079755 писал(а):
1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 20

Любопытно, тут собраны все нечётные числа, меньшие $20$.
А тут - все нечётные, меньшие $10$:
Цитата:
1, 1, 3, 3, 5, 5, 7, 7, 9, 9, 10

 Профиль  
                  
 
 Re: Режем торт
Сообщение06.12.2015, 23:38 
Модератор
Аватара пользователя


11/01/06
5660
Sender в сообщении #1079813 писал(а):
Было бы любопытно оценить возможности вашего метода в прояснении ситуации с $9$ гостями. Если он за разумное время найдёт решение с $22$ кусками, которое заведомо существует, можно попытаться найти решение с $21$ куском.

Попробую. Пока что эмпирически получается, что если решение существует, то оно отыскивается относительно быстро, а вот если его нет, то установление сего факта занимает существенно больше времени. Например, для $N=7$ и 13 кусков, безрезультатно считается уже сутки.

Я описал две различных MILP-формулировки этой задачи на Mathoverflow:
http://mathoverflow.net/questions/21447 ... e-multiset

-- Sun Dec 06, 2015 15:44:56 --

Добавил последовательность значений в OEIS: A265286. Она ссылается на эту тему как на коллективный труд по установлению значений для $N=1,2,...,8$. По мере нахождения новых значений, просьба их туда добавлять.

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

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



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

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


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

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