Многие наверное знают следующую задачу.
Дано: один торт (вкусный) и два человека, мечтающий этот торт съесть.
Найти способ честно поделить торт так, чтобы никому не было обидно.
Знает ли кто решение этой задачи в общем случае:
1 торт, N едоков;
K тортов, N едоков;
Здравствуйте, bkat, Вы писали:
B>Еще одна занимательная задачка...
B>Многие наверное знают следующую задачу. B>Дано: один торт (вкусный) и два человека, мечтающий этот торт съесть. B>Найти способ честно поделить торт так, чтобы никому не было обидно.
Первый делит. Второй выбирает.
B>Знает ли кто решение этой задачи в общем случае: B>1 торт, N едоков; B>K тортов, N едоков;
Тоже самое. Один делит, а кусок берет последним. Каждый торт делится отдельно от других.
Здравствуйте, bkat, Вы писали:
B>Здравствуйте, Lexey, Вы писали:
B>>>Знает ли кто решение этой задачи в общем случае: B>>>1 торт, N едоков;
L>>Один делит, а кусок берет последним.
B>А делит только один?
Ага. Поскольку ему не хочется оказаться в проигрыше, ему придется делить все поровну.
L>Тоже самое. Один делит, а кусок берет последним. Каждый торт делится отдельно от других.
А кто выбирает первым? В это случае имеется резон организовать коалицию тому кто делит, и тому, кто первый выбирает. ИМХО, в этом случае должен быть аукцион.
Здравствуйте, Mystic, Вы писали:
L>>Тоже самое. Один делит, а кусок берет последним. Каждый торт делится отдельно от других.
M>А кто выбирает первым? В это случае имеется резон организовать коалицию тому кто делит, и тому, кто первый выбирает. ИМХО, в этом случае должен быть аукцион.
Про коалиции речи в исходной постановке не было. С ними все будет гораздо веселее.
Здравствуйте, Lexey, Вы писали:
L>>>Один делит, а кусок берет последним. B>>А делит только один? L>Ага. Поскольку ему не хочется оказаться в проигрыше, ему придется делить все поровну.
А в каком порядке остальные будут выбирать? Я думаю, что никто не захочет уступить и каждому, кроме первого вполне может показаться, что лучший кусок уже взяли до него.
Могу предложить следующее решение (не очень хорошо подходит для круглых тортов, но в теории и для них все в порядке):
Один плавно ведет ножик вдоль торта (перпендикулярно лезвию), отмечая все больший кусок. Когда кто-то посчитает, что ему хватит, говорит "стоп" и ему отрезают этот кусок. Делящий также может сказать "стоп" в любой момент.
Здравствуйте, Михаил Можаев, Вы писали:
ММ>Здравствуйте, Lexey, Вы писали:
L>>>>Один делит, а кусок берет последним. B>>>А делит только один? L>>Ага. Поскольку ему не хочется оказаться в проигрыше, ему придется делить все поровну.
ММ>А в каком порядке остальные будут выбирать? Я думаю, что никто не захочет уступить и каждому, кроме первого вполне может
Это абсолютно фиолетово. Можно разыграть. При отсутсвии коалиций никакой разницы не будет. С коалициями такой подход неприемлим.
>показаться, что лучший кусок уже взяли до него.
Здравствуйте, bkat, Вы писали:
B>Еще одна занимательная задачка...
B>Многие наверное знают следующую задачу. B>Дано: один торт (вкусный) и два человека, мечтающий этот торт съесть. B>Найти способ честно поделить торт так, чтобы никому не было обидно.
Ну, значит, так.
Спорят они, спорят... И тут прихожу Я,
Беру нож и режу торт на два неравных куска.
1.Спрашиваю: "Я честно поделил, никого не обидел?"
Если отвед "Да" -- задача решена.
Иначе
2. Съедаю меньший кусок.
3. Больший кусок делю на две неравные части.
( Если делить больше нельзя, бросаю исключение и сматываюсь )
4. Goto 1.
Здравствуйте, bkat, Вы писали:
B>Еще одна занимательная задачка...
B>Многие наверное знают следующую задачу. B>Дано: один торт (вкусный) и два человека, мечтающий этот торт съесть. B>Найти способ честно поделить торт так, чтобы никому не было обидно.
B>Знает ли кто решение этой задачи в общем случае: B>1 торт, N едоков; B>K тортов, N едоков;
А если сделать так:
1. Сначала все едоки делают по одному разрезу торта. В итоге имеем 2*N кусков
2. Каждый едок (в порядке очередности из п. 1) берет по куску
3. Каждый едок (в порядке очередности из п. 1) берет по куску
Здравствуйте, bkat, Вы писали:
B>Знает ли кто решение этой задачи в общем случае: B>1 торт, N едоков; B>K тортов, N едоков;
1. Первый намечает один "справедливый" кусок
2. По кругу опрашиваются все осnальные: Не считают ли они "справедливым" уменьшить его
3. Если кто-то согласен уменьшить он намечает свой разрез и далее опрос продолжается исходя из размеров "нового" куска.
4. Когда круг замкнется на первом. Кусок получает тот кто наметил последний разрез.
5. Далее тоже самое для N-1
Здравствуйте, bkat, Вы писали:
B>Дано: один торт (вкусный) и два человека, мечтающий этот торт съесть. B>Найти способ честно поделить торт так, чтобы никому не было обидно.
Решение приведено еще вроде как у Гарднера.
Тривиально обобщается на любое количество тортов.
Смысл в том, что один двигает нож через торт (в оригинале было нечто типа проволоки ), и любой имеет право в любой момент сказать стоп, нож опускается и он берет отрезанный кусок. Для K тортов процедура может быть повторена K раз. Доказательство, что все довольны, тоже довольно тривиальное, идея такая, если у кого-то меньше, чем поровну, тозначит у кого-то другого больше, но "обделенный" перед "жадиной" "стоп" не сказал, потому противоречие.
Здравствуйте, bkat, Вы писали:
B>Многие наверное знают следующую задачу. B>Дано: один торт (вкусный) и два человека, мечтающий этот торт съесть. B>Найти способ честно поделить торт так, чтобы никому не было обидно.
Пришло мне в голову такое обобщение.
У одного из них день рождения и они совместно решил, что имениник должен получить кусок в r раз (r не обязательно целое) больше чем другой.
Найти решение для нецелых r , хотя бы для двух человек, мне с ходу не удалось
Здравствуйте, MichaelP, Вы писали:
MP>Пришло мне в голову такое обобщение. MP>У одного из них день рождения и они совместно решил, что имениник должен получить кусок в r раз (r не обязательно целое) больше чем другой.
Ну, для нецелых, но являющихся обыкновенной дробью — практически как и для целых, то есть, формально, увеличивается число кусков на знаменатель дроби. А вот для всяких там прочих трансцендентных — чего-то не получается, да и вряд ли получится, оценка-то на глаз должна происходить, приборов-то нет.
Вариант "двое на одного" считаем решенным:
первый делит, второй выбирает.
Тепрь обобщаем до "Трое на одного"
A — первый человек
B — второй
С — третий
1) A и B делят торт пополам.
2) C и A делят половинку доставшуюся A
3) А откладывает свою половинку, и делит c B его половинку.
4) Берут "четвертинку", которую отложил A и повторяют операцию снова.
Здравствуйте, gloomy rocker, Вы писали:
GR>Тепрь обобщаем до "Трое на одного"
Да, как представлю такое решение в ситуации "третьим будешь?" — до дойдет.
Здравствуйте, bkat, Вы писали:
B>Еще одна занимательная задачка...
B>Многие наверное знают следующую задачу. B>Дано: один торт (вкусный) и два человека, мечтающий этот торт съесть. B>Найти способ честно поделить торт так, чтобы никому не было обидно.
B>Знает ли кто решение этой задачи в общем случае: B>1 торт, N едоков; B>K тортов, N едоков;
1) Любой делит на N равных частей — ему отдают меньшую
2) Складывают оттавшиеся N-1 частей ... N=N-1 .... и т.д. 1 шаг
B>Дано: один торт (вкусный) и два человека, мечтающий этот торт съесть. B>Найти способ честно поделить торт так, чтобы никому не было обидно. B>Знает ли кто решение этой задачи в общем случае: B>1 торт, N едоков; B>K тортов, N едоков;
Известное решение с перемещением ножа вдоль торта и криками "стоп" уже было.
Пришлось придумать свое.
Уточнения.
1. Каждый претендент хочет получить 1/N часть торта, где N — общее кол-во претендентов.
2. Каждый i претендент обладает некой точностью глазомера D[i]
и в соответствии с ней определяет размер своего куска = 1/N +- D[i]
3. Если размер доставшегося куска находится в пределах 1/N +- D[i] претендент[i] не обижается.
Задача 1.
1 Торт, 2 Претендента
Аксиома:
Если торт делит претендент с наилучшим глазомером (миним. D[i]), то оба претендента остаются довольными независимо от того, кому какой кусок достался.
Решение.
--------
1.0 Пусть тот у кого нож, называется Режущий, а другой будет Оценщик.
1.1 Произвольно выбранный претендент берет нож и показывает как он хочет разделить торт на две равные части ( с учетом своего глазомера ).
Оценщик выражает свое согласие, либо несогласие.
1.2 Если Оценщик согласен, что такой разрез даст два равных (с учетом его глазомера) куска, Режущий делает разрез и берет себе любой кусок.
Очевидно, что довольны оба, так как Режущий предложил такое разделение, а Оценщик согласился. Задача решена.
При этом глазомер Режущего лучше или равен глазомеру Оценщика. (точнее)
1.3 Если Оценщик несогласен, значит глазомер Оценщика точнее. Меняем претендентов местами. Теперь у Режущего глазомер будет точнее и новый Оценщик согласится с предложением. См. п. 1.2.
Задача 2.
1 Торт, 3 Претендента
Решение.
-------
Аналогично Задаче 1.
2.1 Произвольно выбранный претендент берет нож и показывает как он хочет разделить торт на две равные части ( с учетом своего глазомера ).
Оценщики ( их теперь 2 ) выражают свое согласие, либо несогласие.
2.2 Если оба Оценщика согласны, что такой разрез даст три равных (с учетом глазомера каждого) куска, Режущий делает разрез и берет себе любой кусок. Оставшийся кусок делится на двоих как в Задаче 1.
При этом глазомер Режущего лучше или равен глазомеру любого Оценщика. (точнее)
2.3 Если хотя бы один Оценщик несогласен, значит глазомер несогласного Оценщика точнее. Меняем Режущего и несогласного Оценщика местами. Теперь у Режущего глазомер будет точнее, чем глазомер каждого оценщика, и они оба согласятся с предложением.
См. п. 2.2
2.4. Если несогласны оба Оценщика, значит у Режущего самый плохой глазомер. Меняем местами Режущего с любым Оценщиком.
Новый режущий делает свое предложение. Дальше все происходит либо как в п. 2.2, либо как в п. 2.3
Задача с 1 тортом и N Претендентами.
Решается аналогично.
Рекурсивно:
1. Находим претендента с лучшим глазомером.
2. Он отрезает себе 1/N кусок и уходит.
3. Решаем задачу для 1/(N-1) претендентов ( для N = 3 и N = 2 решение показано выше )
Задача с K тортами и N Претендентами.
Сводится к K задачам с 1 тортом и N претендентами.
Единственно, плохо при больших N -- замучаешься выборы проводить...
( может их постепенно упорядочивать в соответствии с глазомером? )
А может проще?
Например, я и моя подруга едим торт.
Я режу его на 2 равных (по моему мнению) куска. Мне безразлично, какой из них есть.
Подруга выбирает из этих двух тот, который (по ее мнению) больше. Теперь она довольна.
Я ем оставшийся, и тоже доволен (см. жирный текст).
Осталось перенести на вариант со мной и k подругами.
на практике бывает так, что после того как ты выбрал или разрезал кусок, оказывается, что можно было это сделать более выгодным образом.
Кроме того, способ не оптимальный: допустим подруге больше нравится левая часть торта, чем правая (правая, с горчицей и луком , ей неприятна). Вам же, наоборот, нравится правая часть. В этом случае можно себе отрезать правый кусок побольше и подруга не обидится, выберет кусок, который ей больше нравится, хоть и меньше. Таким образом у каждого делящего будет кусок, который лучше (по мнению этого человека), чем кусок друга.
Здравствуйте, bkat, Вы писали:
B>Дано: один торт (вкусный) и два человека, мечтающий этот торт съесть. B>Найти способ честно поделить торт так, чтобы никому не было обидно.
B>Знает ли кто решение этой задачи в общем случае: B>1 торт, N едоков; B>K тортов, N едоков;
(Ответ Если нож острый, то весь торт забирает тот, у кого нож. (Выполнение условий Остальные не обижаются потому, что живы остались! А если не верят, что чесно, пусть попробуют обидиться!
Решение в общем случае:
Для 1 торта и N едоков надо брать нож длиной 5см*N+5см, но не больше 1м ...
Для K тортов и N едоков решение анналогично следует из выше сказанного ...
Задача будет интрересней, если будет 1 торт, N едоков и N ножей ...
Прыгая от радости, смотри, чтобы кто-нибудь не убрал у тебя землю из-под ног. << RSDN@Home 1.4 >>
Здравствуйте, bkat, Вы писали:
B>Еще одна занимательная задачка...
B>Многие наверное знают следующую задачу. B>Дано: один торт (вкусный) и два человека, мечтающий этот торт съесть. B>Найти способ честно поделить торт так, чтобы никому не было обидно.
B>Знает ли кто решение этой задачи в общем случае: B>1 торт, N едоков; B>K тортов, N едоков;
Простейший случай все знают (2 человека, 1 торт): один режет, другой выбирает себе кусок.
Случай, когда людей N:
1. Первая итерация такая же как и в простейшем случае.
2. Вторая итерация: каждый из 2-х режет свой кусок ("половинку") на 3 части. Затем третий берет по одному кусочку у каждого.
3. Третья итерация: каждый из 3-х режет свой кусок на 4 части... и т.д. до исчерпания людей
Случай, когда тортов больше одного: всё то же самое что и во втором. Тут возможны варианты в способе деления, но общий смысл алгоритма остается:
1. В первой итерации можно резать все торты пополам,
2. Или разделить все торты пополам (если, например, тортов 3, то по полтора торта).
), и любой имеет право в любой момент сказать стоп, нож опускается и он берет отрезанный кусок. Для K тортов процедура может быть повторена K раз. Доказательство, что все довольны, тоже довольно тривиальное, идея такая, если у кого-то меньше, чем поровну, тозначит у кого-то другого больше, но "обделенный" перед "жадиной" "стоп" не сказал, потому противоречие.
дойдет.
Кр-ть — с.т.
