[sno]

Наверное, все знают известное правило делёжки пирога на двоих - один режет, второй выбирает. Задача: как разделить пирог на троих, соблюдая тот же принцип. Принцип можно сформулировать так - если кто-то получил, по его мнению, слишком маленький кусок, то он сам в этом виноват, то есть все должны быть простимулированы делить поровнее. P.S. Есть тонкость - возможно ли решить эту задачу, если двое объединятся и хотят обмануть третьего или есть решение, которое защищает права меньшинства?) Решение с виду изящное, но задача сложная, есть подводные камни, мы на мехмате не меньше часа соображали)

[Темный]

А говорит Б разрежь на 3 равные части, потом 1 выберу я , другую выберет В, и останется твоя часть.
Б придется поделить на 3 равные части чтобы взять максимальный кусок. вроде бы так пойдет...хотя слишком легко, где-то вероятно ошибаюсь =)

[Michael_13]

предложу 2 варианта
1. первый режет на 3 части второй выбирает кусок первому затем третий - второму
2. первый отрезает треть. 2 решает отдать эту треть первому или взять себе. Осталось двое - дальше как обычно.

[Shrike]

Мож А режет на 2 части
Б режет один кусок на 3 части. Первым выбирает В, вторым А
В режет другой кусок на 3 части. Первым выбирает Б, вторым А

Не знаю есть ли в этом смысл) Просто пришло в голову)

[Owen]

Кроме нормального, математического решения, есть прикольная дуаль =)

В общем, способ деления произвольного длинного предмета, скажем, вафельного торта (прямоугольного), нарезанного еще заранее на полоски.

Первый заносит нож над полоской там, где она кончается, и начинает медленно двигать оный нож по направлению к другому концу. Как только кому-то покажется, что уже достаточно (на троих - что уже больше трети, скажем, ну или не хочет человек обжираться, тоже бывает), так он кричит "стоп", и ему отрезают свежеотмеренный кусок, после чего процесс повторяется с меньшим числом участников.
Оптимальная стратегия при таком делении сложна и содержит офигительные психологические глубины =))

[Андромеда]

Сейчас попробую рассказать, что придумала, если сама не запутаюсь. Оказалось, что не всё так просто, как казалось вначале.
Назовём этих любителей пирога - Первый, Второй и Третий.
Первый режет пирог на три равные по его мнению части. Потом Второй и Третий выбирают для себя по самому большому, на их взгляд куску.
1) Если они выбрали разные куски - порядок, все довольны, все свободны.
2) Если Второй и Третий выбрали один и тот же кусок пирога. Этот кусок они делят меж собой к обоюдному удовольствию по уже известному сценарию ( один пирог двое делят на двоих). Потом Второй и Третий из двух оставшихся кусков, нарезанных Первым, выбирают каждый себе лучший.
2.1)Если они выбрали один и тот же кусок, то поступают с ним так же, как с первым - один делит на 2 части, второй выбирает. В итоге, Второй и Третий довольны - получили по "лучшей" трети пирога. Доволен и Первый - он же резал, так что его кусок не меньше двух съеденных.
2.2)Если Второй и Третий выбрали разные куски из оставшихся двух, то каждый из них делит этот кусок с Первым, соблюдая уже известный принцип "деления пирога на двоих".



--------------------

[ilia_gold]

насколько я понял, человек получивший кусок,по его мнению , больше 1\3 остаеться доволен,даже если знает что его сосед получил еще больше?...
тогда я нашел решение попроще...
А режет пирог на 3 равные части и приносит часть 1 к Б.... если Б его хочет (если не хочет,то задача тут же решаеться,его берет либо с либо А и остальное делят 2 других)) , то кусок 1 предлагаеться С, если С его тоже хочет(если не хочет см.выше), то етот кусок откладываеьтся и Б предлагаеться кусок 2. если Б его не хочет то см.выше, если хочет то идем к С...если не хочет то см.выше а если хочет то оставшийся 3 кусок признан обоими меньшим и его лопает А...остальное делят....вот и все.


Андромеда нашла тоже правильное решение..

[Андромеда]

ilia_gold, я поняла, что доволен человек только тогда, когда он считает, что получил кусок НЕ МЕНЬШЕ каждого из двух оставшихся. Тогда ваше решение не проходит.
Просьба к автору задачи - уточните этот момент, пожалуйста.


--------------------

[sno]

Уточняю - Андромеда, конечно, права в последней реплике, но её решение тоже не проходит. Возьмите крайний случай - А плохо порезал, один кусок большой и два маленьких, или один маленький и два больши, но чуть разных, и проверьте ваши решения для этих вариантов - они не работают. Два больших не годится потому, что если В понимает, что ему досталось больше трети, но при этом у А заведомо больше, это не удовлеьворит В: кажлый должен быть уверен что его кусок не меньше любого из других.

[Пошлый]

Насколько я помню, алгоритм дележа торта на n частей выглядит так: n человек становится в очередь, первый из ник отрезает 1/n-ную, по его мнению, часть, И СТАНОВИТСЯ В КОНЕЦ ОЧЕРЕДИ. Второй смотрит на эту часть, и, если она его устраивает, забирает себе. Если же нет, то он просто переходит в конец очереди. Третий делает то же самое. В итоге, если эта 1/n-ая часть никому не понравилась, ее забирает тот, кто ее отрезал. И так далее...
Разумеется, все должны играть честно и не помогать соседу

Это сообщение отредактировал Пошлый - 3/08/2005, 04:23