2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 7, 8, 9, 10, 11  След.
 
 Re: Режем торт
Сообщение29.05.2018, 00:00 
Заслуженный участник
Аватара пользователя


09/09/14
6328
12d3 в сообщении #1315720 писал(а):
Приятно возвращаться к задачке через долгое время, с новыми идеями. Вроде как удалось выполнить полный перебор для 8-16...
Поздравляю! Полной проверки для 8--16 раньше ещё не было (у меня было, кажется, для случая максимального куска меньше 105, но это намного проще).

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

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


04/03/09
911
grizzly в сообщении #1315737 писал(а):
1) Это действительно полный перебор для всего 8--16, а не только для 420 элементарных кусочков?
Нецелые куски тоже рассматривались. Повезло, что все-таки все решения целые, а то возни с дробями вышло бы много.
grizzly в сообщении #1315737 писал(а):
2) Вашим алгоритмом реально проверить отсутствие решений для 9--18?
Реально. Переделывать придется не так много, только время выполнения возрастет на порядок-два.

 Профиль  
                  
 
 Re: Режем торт
Сообщение29.05.2018, 06:39 


21/05/16
4292
Аделаида
12d3 в сообщении #1315744 писал(а):
Нецелые куски тоже рассматривались.

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

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


04/03/09
911
kotenok gav в сообщении #1315784 писал(а):
А каким образом? Их ведь бесконечно много.

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

 Профиль  
                  
 
 Re: Режем торт
Сообщение29.05.2018, 13:45 


14/01/11
3062
12d3 в сообщении #1315835 писал(а):
Производился перебор не размеров кусков, а способов их группиповки.

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

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


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

 Профиль  
                  
 
 Re: Режем торт
Сообщение30.05.2018, 10:31 
Аватара пользователя


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

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


14/01/11
3062
12d3, спасибо. У самого были мысли копать в этом направлении, но не хватило решимости. :-)

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


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

 Профиль  
                  
 
 Re: Режем торт
Сообщение04.06.2018, 09:00 


14/01/11
3062
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$.

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


01/08/06
3136
Уфа
Sender писал(а):
ведь это в точности известная задача о 9 бандитах и куске золота, которая имеет следующее решение
Забавно! Получается, что здесь решена гораздо более сложная (и более логичная) задача, когда все гангстеры против всех, и может выжить любое их число, от 0 до 9. Причём удивительно, почти парадоксально, что достаточно всего одного дополнительного куска.

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


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

 Профиль  
                  
 
 Re: Режем торт
Сообщение04.06.2018, 14:52 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
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 еще может существовать?

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


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

 Профиль  
                  
 
 Re: Режем торт
Сообщение06.06.2018, 04:54 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Друзья, я нашёл решение для 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

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

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



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

Сейчас этот форум просматривают: YandexBot [bot]


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

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