![]() |
|
О жизни...
::
|
|
| ||
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)В дележе пирога участвуют Заказчик, Франч и Программист? Рекламное место пустует |
|
Список тем форума
|