Режем торт

[sng1]

Проверил вручную для $N=1$, $N=2$, $N=3$, пока вроде получается (кроме числа строк в матрице и уменьшения ранга на 2).

[sng1]

$M_N:=\textrm{вышеописанная матрица}$, $b_N:=\textrm{столбец свободных членов}$,
$x_N:=\textrm{некоторое решение матричного уравнения } M_Nx=b_N$ имеющее только неотрицательные компоненты и максимальное число нулевых компонент. Вышенаписанная гипотеза состоит в том, что число ненулевых компонент в $x_N$ является ответом.
Матрица $M_5$ имеет размер $(10,60)$ и ранг равный $10$ (как мы видим, ни ранг матрицы, ни ранг $-2$ в качестве ответа $F(5)=9$ не подходят). Вектор столбец $(12, 0_5, 8, 0_{15}, 3, 0_5, 1, 6, 0_4, 6, 0, 4, 0_{15}, 9, 0_5, 11, 0)^\mathrm{T}/60$ возможный кандидат на $x_N$ (недоказана максимальность числа нулей).
Но как найти $x_N$, или хотя бы число ненулевых компонент в $x_N$, пока непонятно.

[Sender]

Компьютерным перебором нашёл решение из $17$ кусков для $8$ гостей. Объём торта считаем равным $840$.
Части:
$36,35,57,48,105,50,62,15,63,55,42,17,43,34,58,47,73.$
Разбиения:
$36+35+34=50+55=15+17+73=57+48=58+47=105=63+42=62+43,$
$62+58=105+15=48+55+17=36+50+34=47+73=35+42+43=57+63,$
$36+57+47=50+17+73=35+105=55+42+43=48+34+58=62+15+63,$
$105+63=57+62+15+34=36+35+55+42=48+47+73=50+17+43+58.$
Кстати, такой вопрос поднимался на math.stackexchange:
http://math.stackexchange.com/questions/1381042/dividing-the-whole-into-a-minimal-amount-of-parts-to-equally-distribute-it-betwe

-- Сб ноя 21, 2015 21:55:58 --

Уточнение: минимальность этого решения не доказана, т.е. сказанное означает, что $F(8)\leqslant 17.$

[grizzly]

Sender
Есть ли шансы Вашим алгоритмом перебирать для $F(9)$? (Я имею в виду отношение затраченных усилий к надеждам получить близкий к точному результат.)

Пока при каждом переходе от нечётного к чётному было $F(2n)-F(2n-1)=2$. Хочется думать, что эта закономерность никогда не нарушится.
А вот переход от чётного к нечётному пока всегда был таким: $F(2n+1)-F(2n)=n+1$. Но это у нас пока нечётные все были простыми. А тут появляется 9. Я надеюсь, что $19\le F(9)\le 22$, но не рискнул бы предполагать точнее.
(Беглое, но поверхностное, ознакомление со всеми англо-ссылками не добавило мне ни идей, ни понимания.)

[Sender]

grizzly в сообщении #1075548 писал(а):

Есть ли шансы Вашим алгоритмом перебирать для $F(9)$?

Сложно сказать, я скармливаю торт задачу sat-солверу, а там результат непредсказуем. Ясно одно: чем ближе к точному решению, тем дольше он думает. Пока что для $F(9)$ удалось получить верхнюю оценку $26$. Решение с $25$ кусками за полдня не нашлось...

[Sender]

Хотя с другой стороны,

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

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

В самом деле: если нам известно, что $F(8)\leqslant 17,$ возьмём круглый торт и разрежем его на $17$ частей, потом расположим их так, чтобы они образовали $3$ равные доли. Чтобы разрезать на $9$ равных частей, нам надо добавить ещё не более $6$ разрезов, тем самым увеличив количество частей не более, чем на $6$, т.е. $F(9)\leqslant 23.$

[Sender]

Нашлось решение для $7$ гостей из $14$ кусков.
Части:
$45,59,19,41,35,21,39,1,31,11,15,29,25,49.$
Разбиения:
$31+29=11+49=21+39=45+15=59+1=35+25=19+41,$
$59+11=45+25=39+31=41+29=19+35+1+15=21+49,$
$59+25=45+39=41+1+31+11=35+49=19+21+15+29,$
$45+21+39=19+1+31+29+25=41+15+49=59+35+11.$
Таким образом, $13\leqslant F(7)\leqslant 14.$
Следовательно, искомая последовательность - не A054519.

[grizzly]

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

Следовательно, искомая последовательность - не A054519.

Здорово! Я и раньше не верил в эту последовательность, но не до такой же степени :) Чертовски интересно!

[worm2]

Можно оптимизировать процесс поиска для проверки гипотезы $F(7)=13$.
Можно считать, что торт уже разрезан на 7 одинаковых частей (по 60 грамм в каждой).
Только одна из этих седьмых частей не будет разрезана (случай, когда не разрезано 2 части, опровергается отдельно).
Остальные разрезы можно отсортировать по неубыванию веса: из первой части вырезается кусок не больше 10 граммов (если минимальный кусок > 10, то невозможно дополнить 60-граммовый кусок до 70-ти), из второй — не меньше первого, но не больше 30 гр (больше 30 будет 2-я часть) и т.д., из 6-й — не меньше 5-го, но не больше 30. Нужно следить, чтобы из уже отрезанных частей можно было собрать 10 граммов и 24 грамма (для дополнения 60-граммового куска до 1/6 = 70 гр. и до 1/5 = 84 гр.). Эта оптимизация даёт примерно 320 тысяч вариантов вместо 420 миллионов. Точнее, должна давать ещё меньше, т.к. я не довёл оптимизацию до конца.
Если я ничего не напутал, то $F(7)=14$, т.к. у меня подходящая конфигурация из 13 разрезов не нашлась. Нашлось немного конфигураций, в которых не хватает одного разреза.

[Sender]

worm2 в сообщении #1076536 писал(а):

случай, когда не разрезано 2 части, опровергается отдельно

Вот здесь вы не могли бы чуть добавить подробностей? То, что как минимум одна часть равна $\frac{1}{N}$, понятно, причём это верно для любого $F(N)$, равного $2N-1$, где $N$ - количество гостей.

[sng1]

$\mathrm{size}(M_N)=\left(1+\frac{(N+l-2)(N-l+1)}{2}, \frac{N!}{(l-1)!}\right)$, $ \mathrm{size}(M_8)=(23, 1680)$. Можно поискать разрез на $16$ кусков для $8$ гостей, выбирая $k$-м способом $16$ столбцов в матрице $M_8$ из $1680$ столбцов, формируя из них матрицу $M_{N,k}$ и проверяя наличие нужного решения матричного уравнения $M_{N,k}x=b_N$.
Но как эффективно сократить перебор, и как эффективно проверить матрицу $M_{N,k}$ ?

[worm2]

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

Вот здесь вы не могли бы чуть добавить подробностей?

Сначала мне это казалось почти очевидным, а сейчас уверенность куда-то улетучилась
Придётся действительно опровергать это отдельно, возможно, отдельную программу для такой конфигурации надо будет написать.

[worm2]

Написал программу, перебирающую все разрезы пяти из семи 60-граммовых кусков (всего 12 разрезов).
Среди них нашлось 29 конфигураций, которым до полного счастья в общей сложности не хватает четырёх разрезов (например, можно разрезать пол-торта на 3 куска по 70 граммов, а оставшейся половине из девяти кусков не хватает двух разрезов, чтобы быть поделенными ещё на три равных куска; можно выбрать 3 куска по 84 грамма, не хватает одного разреза, чтобы поделить весь торт на 5 частей по 84 гр, можно выбрать две четвертинки, но не больше, ещё один разрез нужен, всего не хватает четырёх).

Последним 13-м разрезом мы можем улучшить ситуацию при всех трёх разрезаниях (на 6, 5 и 4 равных куска), но не более чем на один кусок. Это действительно легко показать с учётом следующего уточнения: хотя последний разрез, позволяющий разделить торт на $n$ равных частей, и добавляет два новых куска, я считаю, что добавляется только один, так как ищу только $n-1$ кусков по $1/n$ торта, оставшийся кусок будет равен $1/n$ автоматически, я его не считаю.

Таким образом, ни одна из 29 конфигураций с дефицитом в 4 разреза (а тем более ни одна из тех, у которых дефицит больше), не может быть улучшена до полного решения последним 13-м разрезом. Ради интереса я всё-таки проверил всевозможные разрезы всех 29 конфигураций и обнаружил, что лучшие результаты (дефицит в один разрез) получаются только при разрезании большого, 60-граммового куска. Т.е. конфигурация, которую я вчера проверял, является наилучшей. Как говорится в том анекдоте, "это действительно очевидно"

[Skeptic]

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

Нашлось решение для $7$ гостей из $14$ кусков.
Части: $45,59,19,41,35,21,39,1,31,11,15,29,25,49.$

Получилась интересная последовательность из 14 элементов

$$59+49+45+41+39+35+31+29+25+21+19+15+11+1$$

[sng1]

Skeptic в сообщении #1076939 писал(а):

Получилась интересная последовательность из 14 элементов

$$59+49+45+41+39+35+31+29+25+21+19+15+11+1$$

Наблюдаю симметрию разностей соседних членов. А что можно заметить для решений при $1 \leq N \leq 6$ ?
А для $N=8$, нет ли решения из $16$ кусков с симметрией разностей соседних членов?