Режем торт

[grizzly]

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

Приятно возвращаться к задачке через долгое время, с новыми идеями. Вроде как удалось выполнить полный перебор для 8-16...

Поздравляю! Полной проверки для 8--16 раньше ещё не было (у меня было, кажется, для случая максимального куска меньше 105, но это намного проще).

У меня два вопроса.
1) Это действительно полный перебор для всего 8--16, а не только для 840 элементарных кусочков? (Я помню Ваш удивительный контрпример с весом торта в 2 раза больше НОКа.)
2) Вашим алгоритмом реально проверить отсутствие решений для 9--18? (Я надеюсь, поскольку задачи, по идее, очень похожи, а отсутствие частенько определяется быстрее, чем наличие.)

[12d3]

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

1) Это действительно полный перебор для всего 8--16, а не только для 420 элементарных кусочков?

Нецелые куски тоже рассматривались. Повезло, что все-таки все решения целые, а то возни с дробями вышло бы много.

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

2) Вашим алгоритмом реально проверить отсутствие решений для 9--18?

Реально. Переделывать придется не так много, только время выполнения возрастет на порядок-два.

[kotenok gav]

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

Нецелые куски тоже рассматривались.

А каким образом? Их ведь бесконечно много.

[12d3]

kotenok gav в сообщении #1315784 писал(а):

А каким образом? Их ведь бесконечно много.

Производился перебор не размеров кусков, а способов их группиповки. Далее там решались линейные уравнения с целыми коэффициентами, которые в принципе могут дать нецелые корни, но в данном случае решений с нецелыми частями нет.

[Sender]

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

Производился перебор не размеров кусков, а способов их группиповки.

Припоминаю, что worm2 пытался действовать схожим образом, но добрался только до 6 гостей. Большой прогресс, не можете в двух словах пояснить, какие идеи вы использовали?

[12d3]

Идея растет отсюда и отсюда. Генерируем с помощью стороннего софта все подходящие нам графы, коих оказалось примерно 100000 штук. Потом представляем все куски в виде линейной комбинации с двумя переменными. Сразу можно проверить существование таких значений переменных, чтобы все куски были неотрицательными. Это отсеивает большинство вариантов, остается где-то 2000 штук. Дальше пытаемся раскидать 16 кусков на 6 гостей таким образом: в разбиении на 6 гостей точно присутствует две группы по два куска, вот и переберем все возможные пары групп по два куска и попробуем решить систему из двух линейных уравнений (группы равны по 140 каждая). Если система имеет единственное решение, то проверяем, чтоб все куски были неотрицательные и хоть один не кратен 5 (что случается крайне редко), и раскидывание на 6 и на 5 гостей можно делать уже вручную. А вот если система недоопределена, то проверяем на совместность и только в этом случае перебираем все разбиения 16 кусков на 6 гостей (система из 6 уравнений все еще должна оставаться совместной и недоопределенной, потому что случай определенной системы рассмотрен выше). Избавляемся от одной переменной. Повторяем примерно то же самое для разбиения на 5 гостей.
В общем смысл оптимизации в том, чтобы предварительно делать несколько незатратных по времени проверок, прежде чем переходить собственно к перебору разбиений на группы.

[dimkadimon]

Нашёл несколько сотен почти-решений 10-21, но полное никак не удаётся. В этих решениях не хватает всего двух нужных сумм.

[Sender]

12d3, спасибо. У самого были мысли копать в этом направлении, но не хватило решимости.

[12d3]

9-18 проверил. Результат весьма удивительный вышел: нельзя даже поделить на 9, 8 и 7 гостей (т.е. полноценные проверки на 6 и 5 гостей не понадобились). И это при том, что 9-19, как мы знаем благодаря dimkadimon, существует. Единственная проверка на 5 состояла в том, чтобы были куски, не кратные 5 (или если кусок дробный, то числитель не кратен 5). Возможно, существуют разбиения на 9,8,7 гостей, в которых все куски кратны 5, я такие отсекал заранее.
К слову, в проверке 8-16 обнаружился баг, из-за которого перебор был не полный. Но исправление новых решений все равно не принесло.

[Sender]

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

9-18 проверил. Результат весьма удивительный вышел: нельзя даже поделить на 9, 8 и 7 гостей (т.е. полноценные проверки на 6 и 5 гостей не понадобились).

Вот тут надо аккуратнее, ведь это в точности известная задача о 9 бандитах и куске золота, которая имеет следующее решение, приведённое по ссылке:
Куски:3,7,9,14,16,18,23,24,25,30,31,32,38,40,42,47,49,56.
Разбиения:
На 9: {3,23,30} {7,49} {9,47} {14,42} {16,40} {18,38} {24,32} {25,31} {56}.
На 8: {3,18,42} {7,56} {9,24,30} {14,49} {16,47} {23,40} {25,38} {31,32}.
На 7: {3,7,24,38} {9,14,18,31} {16,56} {23,49} {25,47} {30,42} {32,40}.

К слову, я добавил ограничения, упомянутые dimkadimon в реализации его метода, в свою CNF-кодировку задачи, но видимого улучшения это не принесло.

-- Пн июн 04, 2018 09:10:58 --

Впрочем, да. в упомянутом разбиении в наших терминах все куски кратны 5. Кстати, кто-то уже добавил 19 в A265286.

-- Пн июн 04, 2018 09:25:04 --

Да, эти колдунства с делителями не позволяют отделаться от мысли, что, может статься, это таки A091626. Обратите внимание на реккурентную формулу, там присутствует $\tau$-функция. А в представлении для wolfram mathematica - функция делителей, даже, более точно, количество делителей $n$.

[worm2]

Sender писал(а):

ведь это в точности известная задача о 9 бандитах и куске золота, которая имеет следующее решение

Забавно! Получается, что здесь решена гораздо более сложная (и более логичная) задача, когда все гангстеры против всех, и может выжить любое их число, от 0 до 9. Причём удивительно, почти парадоксально, что достаточно всего одного дополнительного куска.

[12d3]

Все, что я написал в прошлом посте, неверно. Убрал проверку на делители, а задача про бандитов все равно не решилась.)

[dimkadimon]

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

9-18 проверил. Результат весьма удивительный вышел: нельзя даже поделить на 9, 8 и 7 гостей

Спасибо что все проверили. Я очень рад что мы вместе смогли продлить А265286. Кстати для 9-18 я находил решения в которых не хватало 3 суммы (из всех нужных).

Я придумал еще одну оптимизацию для своего метода. Возможно тут уже обсуждалось. Я заметил что часто когда есть кусочек x то есть и его вторая половинка y, так чтобы $x+y=S/N$, где S сумма всех кусков, а N количество гостей. Можно этим воспользоваться задав сколько хотим иметь таких симметричных кусков. К сожалению это мне не помогло найти 10-21, но может кому поможет.

-- 04.06.2018, 20:38 --

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

Все, что я написал в прошлом посте, неверно

Так значит 9-18 еще может существовать?

[12d3]

Решений для 9-18 все-таки нет. Я перерешал задачу о бандитах, нашел больше 1000 решений, скачать можно тут. Все решения либо целые, либо полуцелые, а для существования 9-18 нужны дроби со знаменателем 5.

[dimkadimon]

Друзья, я нашёл решение для 11 гостей и 28 кусков:

9 119 164 209 273 362 441 537 693 749 847 936 968 1001 1188 1199 1211 1253 1267 1309 1321 1332 1519 1552 1584 1771 1827 2079
guests=6: 2079+1827+441+273 = 1771+1519+1321+9 = 1584+1332+847+693+164 = 1552+1267+936+537+209+119 = 1309+1199+1001+749+362 = 1253+1211+1188+968
guests=7: 2079+1519+362 = 1827+1321+693+119 = 1771+1253+936 = 1584+1199+968+209 = 1552+1211+1188+9 = 1332+1001+749+441+273+164 = 1309+1267+847+537
guests=8: 2079+1267+119 = 1827+936+693+9 = 1771+1321+209+164 = 1584+1519+362 = 1552+1199+441+273 = 1332+847+749+537 = 1309+1188+968 = 1253+1211+1001
guests=9: 2079+1001 = 1827+1253 = 1771+1309 = 1584+936+441+119 = 1552+1519+9 = 1332+1211+537 = 1321+1188+362+209 = 1267+847+693+273 = 1199+968+749+164
guests=10: 2079+693 = 1827+936+9 = 1771+1001 = 1584+1188 = 1552+847+209+164 = 1519+1253 = 1332+1321+119 = 1309+749+441+273 = 1267+968+537 = 1211+1199+362
guests=11: 2079+441 = 1827+693 = 1771+749 = 1584+936 = 1552+968 = 1519+1001 = 1332+1188 = 1321+1199 = 1309+1211 = 1267+1253 = 847+537+362+273+209+164+119+9