2014 dxdy logo

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

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





Начать новую тему Ответить на тему На страницу Пред.  1 ... 3, 4, 5, 6, 7, 8  След.
 
 Re: Режем торт
Сообщение07.12.2015, 10:26 
Заслуженный участник


14/01/11
1658
maxal в сообщении #1080052 писал(а):
Добавил последовательность значений в OEIS

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

 Профиль  
                  
 
 Re: Режем торт
Сообщение07.12.2015, 16:36 
Модератор
Аватара пользователя


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

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


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

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


28/01/14
302
Москва
Sender в сообщении #1079813 писал(а):
Было бы любопытно оценить возможности вашего метода в прояснении ситуации с $9$ гостями. Если он за разумное время найдёт решение с $22$ кусками, которое заведомо существует, можно попытаться найти решение с $21$ куском.

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

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


14/01/11
1658
OlegCh в сообщении #1082776 писал(а):
Я знаю также решение с 21 куском. Более того, знаю что есть решение с меньшим количеством кусков

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

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


28/01/14
302
Москва
Sender в сообщении #1082941 писал(а):
Вот с этого момента нельзя ли чуть подробнее?

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

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


09/09/14
4604
OlegCh в сообщении #1082944 писал(а):
C какого именно?

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

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


14/01/11
1658
grizzly в сообщении #1082946 писал(а):
Мы всё равно попросим оба.

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

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


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

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


09/09/14
4604
Я попытался без использования компа посмотреть случай $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

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


09/09/14
4604
Под катом небольшое улучшение предыдущего решения.
$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

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


09/09/14
4604
Время от времени я возвращаюсь к цифровым медитациям с карандашом и бумагой. С выработкой привычки это занятие становится всё более увлекательным :-)
По-прежнему $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

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


09/09/14
4604
OlegCh в сообщении #1082958 писал(а):
У вас стоит задача разделить поровну между любым числом гостей от 1 до N, а у меня есть решение для 7, 8 и 9 гостей при N=9.
OlegCh в сообщении #1082776 писал(а):
Я знаю также решение с 21 куском. Более того, знаю что есть решение с меньшим количеством кусков, но вот какое оно и как его найти - совершенно не представляю. А было бы интересно его увидеть.
Да, кстати, всё забываю поделиться давно уже виденным в сети решением задачи в Вашей формулировке -- как раз то, что Вас интересует есть здесь (там в ответах есть вариант разрезания на 18 кусков).

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


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

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

grizzly в сообщении #1088872 писал(а):
в процессе всё даже казалось более перспективным, но в конце не хватило терпения

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

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


09/09/14
4604
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

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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