2014 dxdy logo

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

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




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


09/09/14
6328
Три А,да в сообщении #1182162 писал(а):
Я так понял, что используемый алгоритм сначала делит торт на $N$ кусков, потом на $N-1$ и так далее. Эффективнее ли будет получать решение для $N$ из уже известного решения при $N-1$?
Одним словом -- нет.
Да Вы просто попытайтесь для $N=5$ или $N=6$ решить головоломку руками. Это может быть само по себе интересно.

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


01/08/06
3049
Уфа
Если N — простое число, то точно нет. Вот, например, получили мы решение для $N=10$. Скорее всего, у нас там каждый кусок — это $m/2520$, где $m$ — какое-то целое число. Но 2520 не делится на 11, поэтому, чтобы получить решение для 11, нужно будет как минимум 10 разрезов сделать, а это уже слишком тривиальное решение, чтобы быть оптимальным.

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


28/01/14
351
Москва

(Оффтоп)

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

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


05/02/18
31
Новосибирск
sng1 в сообщении #1072259 писал(а):
Найти минимальное число частей $F(N)$, на которое можно разрезать торт, так чтобы торт можно было разделить поровну между любым числом гостей от $1$ до $N$.

Сейчас будут ругаться, что я неправильно поняла условие, но есть два решения:
1) торт без крема - режем горизонтально на N блинов;
2) торт с кремом - режем вертикально на N секторов.
В обоих случаях число частей точно N.

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


21/05/16
4292
Аделаида
К примеру, если 3 гостя, то число кусков 6.

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


01/09/13
4318
kotenok gav в сообщении #1291113 писал(а):
К примеру, если 3 гостя, то число кусков 6.

4 куска...

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


09/09/14
6328
GANJE в сообщении #1291100 писал(а):
1) торт без крема - режем горизонтально на N блинов;
2) торт с кремом - режем вертикально на N секторов.
Не пойдёт. У нас торт с вишенкой :D

 Профиль  
                  
 
 Re: Режем торт
Сообщение08.02.2018, 17:26 


21/05/16
4292
Аделаида
Geen в сообщении #1291114 писал(а):
kotenok gav в сообщении #1291113 писал(а):
К примеру, если 3 гостя, то число кусков 6.

4 куска...

А тогда как разделить между тремя гостями?

-- 09 фев 2018, 00:57 --

А, мы ведь не на одинаковые куски разрезаем... :facepalm: :facepalm: :facepalm: :facepalm:

 Профиль  
                  
 
 Re: Режем торт
Сообщение14.05.2018, 16:31 


14/01/11
2916
grizzly в сообщении #1098098 писал(а):
Для 8--16 тот же алгоритм дал всего 3 решения, чем немало меня удивил (максимальный кусок здесь также строго меньше 105 грамм)

Удалось заинтересовать этой задачей, закодированной в CNF, ни много ни мало профессора Армина Биере. Для решения задачи для 8 гостей и 16 кусков ему потребовалось около 120000 с. на 12-ядерной машине с помощью солвера Treengeling и порядка 30000 с. на одном ядре с помощью солвера Cadical. Потом он запустил задачу для 9 гостей и 19 кусков на свободном кластере, так что, возможно, через каких-нибудь полгода мы увидим решение. Найденные решения для 8-16 ранее не упоминались здесь, что неудивительно, учитывая, что размер максимального куска 105. Итак, сами решения:
размеры кусков: $1,10,14,25,29,41,44,49,56,61,64,76,79,91,95,105.$
8 гостей: $76+29=25+1+79=91+14=105=10+95=49+56=64+41=44+61.$
7 гостей: $76+44=10+49+61=64+56=95+25=91+29=1+14+105=41+79.$
6 гостей: $76+64=49+91=44+95+1=79+61=10+25+105=56+29+14+41.$
5 гостей: $76+91+1=49+14+105=64+25+79=10+56+41+61=44+95+29.$


размеры кусков: $6,9,10,21,25,36,41,49,56,64,69,71,84,95,99,105.$
8 гостей: $25+71+9=64+41=95+10=99+6=69+36=84+21=49+56=105.$
7 гостей: $25+95=71+49=9+105+6=56+64=10+69+41=36+84=99+21.$
6 гостей: $25+105+10=95+9+36=56+84=49+64+21+6=71+69=99+41.$
5 гостей: $25+49+10+84=71+56+41=105+36+21+6=69+99=95+9+64.$

Кроме того, профессор Марижн Хеуле пообещал включить присланные мной задачи в программу приближающихся соревнований SAT-решателей "SAT 2018 Competition", хотя я не уверен, что этим решателям удастся справиться с этой задачей в отведённое время.

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


14/01/11
2916
Ещё одно решение, найденное Армином Биере для 8-16:

размеры кусков: $1,14,25,29,34,41,44,49,56,61,64,71,76,79,91,105.$
8 гостей: $64+41=1+79+25=71+34=29+76=44+61=105=56+49=91+14.$
7 гостей: $64+56=105+1+14=71+49=29+91=76+44=61+34+25=41+79.$
6 гостей: $64+76=71+44+25=61+79=105+1+34=56+29+41+14=49+91.$
5 гостей: $64+79+25=56+71+41=1+91+76=49+44+61+14=105+29+34.$
Понимания особо не добавляет, но можно заметить, что этот результат очень похож на один из двух предыдущих и что количество известных решений с максимальным куском, равным 105, сравнялось с количеством решений с меньшими кусками.

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


01/06/12
1016
Adelaide, Australia
Спасибо очень заинтересовала задача. А где можно найти лучшие результаты на данный момент для всех N?

Кстати, а мы пытаемся уменьшить размер оригинального куска или это не особо важно?

 Профиль  
                  
 
 Re: Режем торт
Сообщение25.05.2018, 16:25 


14/01/11
2916
dimkadimon в сообщении #1314879 писал(а):
А где можно найти лучшие результаты на данный момент для всех N?

Полагаю, в A265286. Сами разбиения ищите в этой теме.

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


09/09/14
6328
dimkadimon в сообщении #1314879 писал(а):
А где можно найти лучшие результаты на данный момент для всех N?
В этой теме, я думаю :)

$N=9$ -- 20 кусков
$N=10$ -- 22 куска

Особенно смешно, что 10--23 было вообще найдено вручную (с карандашом и бумагой :) а потом улучшено до 22.

Моя гипотеза: на чётных увеличивается на 2, на нечётных -- на 3. Тогда должно быть:
8 -- 16 (известно)
9 -- 19
10 -- 21
11 -- 24 ...

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


01/06/12
1016
Adelaide, Australia
Возник очень простой, но фундаментальный вопрос: как проверить что решение правильное? Неужели вручную? Наверняка есть более эффективный метод.

 Профиль  
                  
 
 Re: Режем торт
Сообщение26.05.2018, 03:16 


21/05/16
4292
Аделаида
dimkadimon в сообщении #1315040 писал(а):
Наверняка есть более эффективный метод.

Можно перебирать значения кусков на компе.

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

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



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

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


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

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