Режем торт

[Null]

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

Если при $n=10$ взять объём торта равным $2520$, при разбиении на $8$ частей $b_jx=315-28a_j$, что означает нечётность либо полуцелость $x$.
При разбиении на $7$ частей имеем $b_jx=360-28a_j$. Правая часть делится на $4$, значит, $x$-чётное.

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

[Sender]

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

[sng1]

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

[Null]

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

[sng1]

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

имеет единственное решение, иначе 1 переменную можно обнулить, оставив остальные неотрицательными.

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

[Null]

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\}$)

[worm2]

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

[maxal]

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 кусками.

[worm2]

Мой подход оказался слишком неэффективным. Для $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

[Null]

maxal в сообщении #1079752 писал(а):

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

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

[maxal]

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

maxal в сообщении #1079752 писал(а):

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

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

Если вы имеете в виду это:

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

Предположим, что можно разрезать на 13 кусков. Весь торт считаем за 420.

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

[Null]

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

[Sender]

maxal в сообщении #1079752 писал(а):

Решение для $N=7$ с 14 кусками, найденное с помощью MILP-солвера CPLEX
:

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

[Sender]

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

[maxal]

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$. По мере нахождения новых значений, просьба их туда добавлять.