Режем торт

[grizzly]

Три А,да в сообщении #1182162 писал(а):

Я так понял, что используемый алгоритм сначала делит торт на $N$ кусков, потом на $N-1$ и так далее. Эффективнее ли будет получать решение для $N$ из уже известного решения при $N-1$?

Одним словом -- нет.
Да Вы просто попытайтесь для $N=5$ или $N=6$ решить головоломку руками. Это может быть само по себе интересно.

[worm2]

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

[OlegCh]

(Оффтоп)

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

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

Хочу (с опозданием ) Вас поблагодарить, спасибо! (всего-то год прошел с небольшим... )

[GANJE]

sng1 в сообщении #1072259 писал(а):

Найти минимальное число частей $F(N)$, на которое можно разрезать торт, так чтобы торт можно было разделить поровну между любым числом гостей от $1$ до $N$.

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

[kotenok gav]

К примеру, если 3 гостя, то число кусков 6.

[Geen]

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

К примеру, если 3 гостя, то число кусков 6.

4 куска...

[grizzly]

GANJE в сообщении #1291100 писал(а):

1) торт без крема - режем горизонтально на N блинов;
2) торт с кремом - режем вертикально на N секторов.

Не пойдёт. У нас торт с вишенкой

[kotenok gav]

Geen в сообщении #1291114 писал(а):

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

К примеру, если 3 гостя, то число кусков 6.

4 куска...

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

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

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

[Sender]

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", хотя я не уверен, что этим решателям удастся справиться с этой задачей в отведённое время.

[Sender]

Ещё одно решение, найденное Армином Биере для 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, сравнялось с количеством решений с меньшими кусками.

[dimkadimon]

Спасибо очень заинтересовала задача. А где можно найти лучшие результаты на данный момент для всех N?

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

[Sender]

dimkadimon в сообщении #1314879 писал(а):

А где можно найти лучшие результаты на данный момент для всех N?

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

[grizzly]

dimkadimon в сообщении #1314879 писал(а):

А где можно найти лучшие результаты на данный момент для всех N?

В этой теме, я думаю :)

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

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

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

[dimkadimon]

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

[kotenok gav]

dimkadimon в сообщении #1315040 писал(а):

Наверняка есть более эффективный метод.

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