Режем торт

[Sender]

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

Добавил последовательность значений в OEIS

Строго говоря, мы ещё не установили, что такая последовательность отсутствует в OEIS. Пока что там имеется три кандидата на эту роль:
A085223, A091626 и A242137.

[maxal]

Sender, сторого говоря, да. Но указанные последовательности имеют совсем другую природу, поэтому крайне маловероятно, что они имеют какое-то отношение к данной задаче. Если же вдруг всё-таки это так, то новую последовательность отправим "в отставку" в пользу уже существующей.

[sng1]

Можно, вместо полного перебора матриц $M_{N,k}$, попробовать найти $21$-кусковое решения для $N=9$ путем случайного выбора $21$ столбца в матрице $M_N$. Можно всегда считать первый столбец выбранным, и случайно выбирать остальные $20$.
А как еще сократить вычисления?

[OlegCh]

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

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

Для $N=9$ найти решение с 22 кусками можно довольно легко даже в уме. Я знаю также решение с 21 куском. Более того, знаю что есть решение с меньшим количеством кусков, но вот какое оно и как его найти - совершенно не представляю. А было бы интересно его увидеть.

[Sender]

OlegCh в сообщении #1082776 писал(а):

Я знаю также решение с 21 куском. Более того, знаю что есть решение с меньшим количеством кусков

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

[OlegCh]

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

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

C какого именно?

[grizzly]

OlegCh в сообщении #1082944 писал(а):

C какого именно?

Мы всё равно попросим оба.

[Sender]

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

Мы всё равно попросим оба.

Именно так. Порядок изложения, думаю, особого значения не имеет.

[OlegCh]

Так. Кажется, товарищи, я тут был не точен. У вас стоит задача разделить поровну между любым числом гостей от 1 до N, а у меня есть решение для 7, 8 и 9 гостей при N=9. Для меньшего числа (меньше 7) я не проверял.

[grizzly]

Я попытался без использования компа посмотреть случай $N=10$. Сколько-то алгоритмическими рассуждениями удалось найти рекордное (пока) разбиение на 26 частей (в процессе всё даже казалось более перспективным, но в конце не хватило терпения и я просто подробил два больших куска на 9 мелких, когда заметил локальный рекорд на горизонте).
3,3,3,5,5,7,21,35,49,52,63,77,91,105,108,119,126,133,143,147,161,175,189,217,231,252
Десятки (я использую запятую вместо плюса):
3,3,5,7,108,126 || 3,5,49,52,143 || 35,217 || 63,189 || 91,161 || 119,133 || 105,147 || 77,175 || 21,231 || 252
Девятки:
3,3,5,35,108,126 || 3,5,52,77,143 || 63,217 || 91,189 || 119,161 || 147,133 || 105,175 || 49,231 || 7,21,252
Восьмёрки:
63,252 || 35,49,231 || 7,91,217 || 21,119,175 || 77,105,133 || 126,189 || 3,5,52,108,147 || 3,3,5,143,161
Семёрки:
108,252 || 143,217 || 52,133,175 || 3,126,231 || 3,77,91,189 || 5,5,7,63,119,161 || 3,21,49,35,105,147
Шестёрки:
3,3,5,108,126,175 || 3,5,52,143,217 || 189,231 || 63,77,133,147 || 49,91,119,161 || 7,21,35,105,252

[grizzly]

Под катом небольшое улучшение предыдущего решения.
$N=10$, количество частей 25, кратность 1/2520.

(Оффтоп)

3,3,5,7,8,21,35,49,52,63,77,91,105,108,119,129,133,143,147,161,175,186,217,231,252
Десятки:
3,5,7,108,129 || 8,49,52,143 || 35,217 || 3,63,186 || 91,161 || 119,133 || 105,147 || 77,175 || 21,231 || 252
Девятки:
3,5,35,108,129 || 8,52,77,143 || 63,217 || 3,91,186 || 119,161 || 147,133 || 105,175 || 49,231 || 7,21,252
Восьмёрки:
63,252 || 35,49,231 || 7,91,217 || 21,119,175 || 77,105,133 || 129,186 || 3,5,52,108,147 || 3,8,143,161
Семёрки:
108,252 || 143,217 || 52,133,175 || 129,231 || 3,91,119,147 || 5,8,161,186 || 3,7,21,35,49,63,77,105
Шестёрки:
3,5,108,129,175 || 8,52,143,217 || 3,186,231 || 63,77,133,147 || 49,91,119,161 || 7,21,35,105,252

[grizzly]

Время от времени я возвращаюсь к цифровым медитациям с карандашом и бумагой. С выработкой привычки это занятие становится всё более увлекательным
По-прежнему $N=10$, но количество частей теперь всего 23. Учитывая, как просто находятся новые рекорды, я думаю, что это ещё не предел. Так что и для $N=9$ можно смело делать ставки на уменьшение.

(Подробности)

7,29,32,35,53,63,67,73,81,87,91,98,108,109,115,143,161,171,172,189,199,217,220
Десятки:
7,73,172 || 35,217 || 63,189 || 67,87,98 || 91,161 || 29,108,115 || 109,143 || 81,171 || 53,199 || 220,32
Девятки:
35,73,172 || 32,87,161 || 63,217 || 91,189 || 67,98,115 || 29,108,143 || 109,171 || 81,199 || 7,53,220
Восьмёрки:
91,109,115 || 32,63,220 || 35,81,199 || 7,29,108,171 || 98,217 || 67,87,161 || 143,172 || 53,73,189
Семёрки:
73,115,172 || 143,217 || 171,189 || 161,199 || 87,53,220 || 63,91,98,108 || 7,29,32,35,67,81,109
Шестёрки:
35,53,115,217 || 7,81,143,189 || 63,87,109,161 || 32,91,98,199 || 29,171,220 || 67,73,108,172

[grizzly]

OlegCh в сообщении #1082958 писал(а):

У вас стоит задача разделить поровну между любым числом гостей от 1 до N, а у меня есть решение для 7, 8 и 9 гостей при N=9.

OlegCh в сообщении #1082776 писал(а):

Я знаю также решение с 21 куском. Более того, знаю что есть решение с меньшим количеством кусков, но вот какое оно и как его найти - совершенно не представляю. А было бы интересно его увидеть.

Да, кстати, всё забываю поделиться давно уже виденным в сети решением задачи в Вашей формулировке -- как раз то, что Вас интересует есть здесь (там в ответах есть вариант разрезания на 18 кусков).

[Sender]

grizzly, ваши результаты впечатляют. По-видимому, стоит задуматься об улучшении нижних оценок для $N=9$ и $10$, которые пока составляют $18$ и $20$ соответственно.

-- Сб янв 16, 2016 13:24:07 --

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

в процессе всё даже казалось более перспективным, но в конце не хватило терпения

Вот для таких случаев и придуман комп.

[grizzly]

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

Вот для таких случаев и придуман комп.

Да, с этим не поспоришь. Я забросил свои попытки -- перестало доставлять удовольствие. Как-нибудь попробую запрограммировать свой алгоритм -- рассчитываю, что есть шансы получить точные ответы для $N=9$ и $10$ за вполне разумное время.
Напоследок выложу решение для $N=9$, 21 кусок, которое просто каким-то чудом не сложилось в 20 кусков (я его потому не считал нужным раньше выложить).

(Оффтоп)

1,3,4,21,56,60,74,88,101,109,126,136,140,154,171,178,189,206,220,224,259
Девятки:
21,259 || 56,224 || 3,88,189 || 126,154 || 1,101,178 || 4,136,140 || 109,171 || 74,206 || 60,220
Восьмёрки:
56,259 || 3,88,224 || 126,189 || 60,101,154 || 1,136,178 || 4,140,171 || 109,206 || 21,74,220
Семёрки:
101,259 || 136,224 || 171,189 || 206,154 || 140,220 || 56,126,178 || 1,3,4,21,60,74,88,109
Шестёрки:
74,126,220 || 60,136,224 || 21,140,259 || 4,56,171,189 || 88,154,178 || 1,3,101,109,206
Пятёрки:
60,220,224 || 1,154,171,178 || 4,101,140,259 || 109,189,206 || 3,21,56,74,88,126,136