Вход | Регистрация
 

OFF: алгоритм честного деления пирога на троих

OFF: алгоритм честного деления пирога на троих
Я
   Wasya
 
27.07.09 - 13:43
Математики придумали алгоритм честного деления пирога на троих
http://www.lenta.ru/news/2009/07/27/pies/

Как то Гений задавал эту задачу. Правда вместо пирога, была бутылка водки.
   Нуф-Нуф
 
1 - 27.07.09 - 13:45
текст в студию. лента забанена
   13hero
 
2 - 27.07.09 - 13:46
Очень просто: делящий берёт свою долю пирога последним, тогда, если делящий сделал хоть одну долю меньше остальных - он её и получит.

Крестьянская мудрость.
   tsr
 
3 - 27.07.09 - 13:47
(2) Т.е. Нэша в топку?
   13hero
 
4 - 27.07.09 - 13:49
(3) При чём здесь Нэш?
Кесарю - кесарево.
   Ненавижу 1С
 
5 - 27.07.09 - 13:50
(2) это если бандиты "честные" или друг друга не знают. То есть один делит, второй и третий по очереди выбирают, первый что осталось. Тогда да - ему не более 1/3. Но...
Самый интересный случай, гарантирующий защиту любого бандита от сговора двух других.
   Wasya
 
6 - 27.07.09 - 13:50
http://arxiv.org/abs/0907.1334
Ссылка на препринт

Проблема "честного деления пирога" в самой простой формулировке звучит следующим образом. Предположим, что необходимо разрезать пирог на N частей. При этом нам известно, что у каждого из них имеются собственные критерии сравнения различных кусков пирога. Например, кому-то больше нравится кусок с украшениями, а кто-то не любит, когда слишком много начинки. Возникает вопрос, всегда ли можно разрезать пирог так, что каждый из N человек остался доволен, то есть, сравнив свой кусок с стальными, пришел бы к выводу, что его не обделили.
   tsr
 
7 - 27.07.09 - 13:51
(4) По ссылке

Данный класс привлекает пристальное внимание ученых в последнее время. Дело в том, что в нем лежит так называемая задача вычисления равновесия Нэша, названного так в честь Джона Нэша, известного широкой публике по фильму "Игры разума". Равновесие Нэша - такой тип решения игры нескольких участников, при котором ни один не может увеличить выигрыш, изменив свое решение в одностороннем порядке, если остальные участники свои решения не меняют.
   Ненавижу 1С
 
8 - 27.07.09 - 13:52
+(5) то есть первый в сговоре со вторым и режет так, что один из кусков громадный, достается второму, а потом они его перераспределяют меж собой, оставляя третьего с крохами
   Ygich
 
9 - 27.07.09 - 13:52
блин чета жрать сразу захотелось
   Shurjk
 
10 - 27.07.09 - 13:54
(0) Бутылка водки с ювелирной точностью разливается на три стаканы, неоднократно наблюдал :)
   13hero
 
11 - 27.07.09 - 13:54
(5) Деление можно повторять и выстроить очередь деления.
   Нуф-Нуф
 
12 - 27.07.09 - 13:54
(9)+1
   Старуха Юзергиль
 
13 - 27.07.09 - 13:55
На школьной олимпиаде мне этот вопрос попадался:)
Но решения не помню
   Ненавижу 1С
 
14 - 27.07.09 - 13:56
(11) ну так и выстрой. Это и будет решением
   Wasya
 
15 - 27.07.09 - 13:58
Задача в постановке от Гения 1С.

1) Легкий вариант. Есть бутылка водки и 3 собутыльника. Как поделить так, чтоб каждый считал, что ему досталось не менее 1/3 бутылки. Найти алгоритм для этой задачи нетрудно.

2) Усложненный вариант. Есть бутылка водки и 3 собутыльника. Как поделить так, чтоб каждый считал, что ему досталось не менее чем каждому из двух оставшихся собутыльникам.

Везде предполагается, что глазомер у всех разный. То что одному кажется по-ровну, совсем не означает, что и другим так кажется.
   Ненавижу 1С
 
16 - 27.07.09 - 14:02
(15) второй вариант очевидно же неразрешим в общем случае: например, все считают, что "нормально" это 99% ему.
   DemMif
 
17 - 27.07.09 - 14:08
Решение простое. Каждый по очереди себе кусок отрезает понравившийся. что тут формулы выводить?
   NikVars
 
18 - 27.07.09 - 14:08
(0) По ссылке бред какой-то...
"В 1980 году американский математик Уолтер Стромкуист (Walter Stromquist) доказал, что для любого набора критериев, которых придерживаются эти N человек, пирог можно разрезать справедливо ровно за N-1 разрезов."
Берем стандартный противень, он прямоугольной формы. Хозяйка выпекает пирог на большое количество человек. Например, 8. Берем и делим его на 8 равных частей, для этого требуется всего 4 поперечных разреза и 1 продольный. Всего 5 разрезов.
Бред...
   Wasya
 
19 - 27.07.09 - 14:08
(16) Но ведь каждому можно предложить разделить на троих поровну. Тогда делящий не имеет права отказываться от оставшегося стакана. С его точки зрения там не меньше чем в остальных.
   acsent
 
20 - 27.07.09 - 14:19
(16) В решении предполагается, что если ты делишь, то для тебя все стаканы одинаковы
   Wasya
 
21 - 27.07.09 - 14:23
(3) Для меня это была новость, что Нэш имеет отношение к этой задаче. Так и представляю себе. Переговоры США и СССР по ядерному разоружению. Все ракеты свезли в одно место. Президент США поделил их поровну. А лидер СССР выбрал кучку для себя. Оставшаяся кучка досталась США.
   acsent
 
22 - 27.07.09 - 14:23
(18) Где в твоем решении справедливость?
   NikVars
 
23 - 27.07.09 - 14:25
Ее нет. Гости пришли и берут нарезанные хозяйкой кусочки.
Буду возникать - пойдут мыть посуду.
А вообще в этой ветки думать не хотят.
Интересно, кто первый додумается...
   фросия
 
24 - 27.07.09 - 14:28
про пирог - не знаю подойдет или нет, могу только водку поделить.
одни делит на три равные(как ему кажется части). двое других решают какая из частей самая маленькая и отдают ему.
потом еще один из двоих делит отсавшееся уже на 2 части и второй выбирает тот стакан где больше.
а с пирогом не понятно - ну не будут же они его бесконечно кромсать на кучу маленьких кусочков
   DenLaDen
 
25 - 27.07.09 - 14:58
С фросей пить не буду...
   acsent
 
26 - 27.07.09 - 15:06
(24) Двое ничего не могут решить. (в общем случае)
   acsent
 
27 - 27.07.09 - 15:07
Такая задача помню была в книге а ля "Занимательная математика", только решение жаль не помню
   Жан Пердежон
 
28 - 27.07.09 - 15:11
в общем случае вроде (по памяти) так было:
1. 1ый отрезает N-ую часть и пытается забрать ее себе;
2. если есть кто-то против - то они по очереди уменьшают N-ую часть и пытаются забрать ее себе;
3. никто не против: последний деливший сваливает с 1 частью пирога;
4. пункт 1 только уже на 1 участника меньше;
   Эстет хренов
 
29 - 27.07.09 - 15:33
в общем случае пирог сложной формы,
и у каждого из участников стратегия максимальной доли.
(28) опередил, только он не режет сразу, а планирует разрез
задачка у гарднера кажется была.
   Hitcher
 
30 - 27.07.09 - 16:24
(29)В дележе пирога участвуют Заказчик, Франч и Программист?
 
 Рекламное место пустует


Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Ветка сдана в архив. Добавление сообщений невозможно.
Но вы можете создать новую ветку и вам обязательно ответят!
Каждый час на Волшебном форуме бывает более 2000 человек.