РЕКЛАМА

Загрузка...

Ученые из Стэнфордского университета создали алгоритм так называемого "честного деления пирога" на трех человек. Статья исследователей пока еще не принята к публикации, однако ее препринт доступен на сайте arXiv.org.' />

Математики придумали алгоритм честного деления пирога на троих

Математики придумали алгоритм честного деления пирога на троих

Ученые из Стэнфордского университета создали алгоритм так называемого "честного деления пирога" на трех человек. Статья исследователей пока еще не принята к публикации, однако ее препринт доступен на сайте arXiv.org.
Проблема "честного деления пирога" в самой простой формулировке звучит следующим образом. Предположим, что необходимо поделить пирог на N человек. При этом нам известно, что у каждого из них имеются собственные критерии сравнения различных кусков пирога. Например, кому-то больше нравится кусок с украшениями, а кто-то не любит, когда слишком много начинки. Возникает вопрос, всегда ли можно разрезать пирог так, что каждый из N человек остался доволен, то есть, сравнив свой кусок с остальными, пришел бы к выводу, что его не обделили.
В 1980 году американский математик Уолтер Стромкуист (Walter Stromquist) доказал, что для любого набора критериев, которых придерживаются эти N человек, пирог можно разрезать справедливо ровно за N-1 разрезов. Однако доказательство Стромкуиста не было конструктивным, то есть он не предъявил конкретный алгоритм.
В рамках новой работы математики занимались именно поиском конкретного алгоритма, то есть последовательности действий разрезающего. В полном объеме им решить задачу не удалось, однако они построили алгоритм, который позволяет примерно делить пирог между тремя людьми всего за два разреза. Кроме этого исследователям удалось доказать важное свойство, что задача принадлежит к классу так называемых PPAD-задач. (http://en.wikipedia.org/wiki/PPAD_(complexity))
Данный класс привлекает пристальное внимание ученых в последнее время. Дело в том, что в нем лежит так называемая задача вычисления равновесия Нэша, названного так в честь Джона Нэша, известного широкой публике по фильму "Игры разума". Равновесие Нэша - такой тип решения игры нескольких участников, при котором ни один не может увеличить выигрыш, изменив свое решение в одностороннем порядке, если остальные участники свои решения не меняют.
11
1541
28 июля 2009
Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь. Мы рекомендуем Вам зарегистрироваться либо зайти на сайт под своим именем.
Смотрите также
Пирог высотой 10 метров испекли к Рождеству в Индии

Новый мировой рекорд попытались установить индийские пекари, приготовившие рождественский пирог высотой почти 10 метров, сообщает Би-би-си. Гигантское...

Американский пирог - опросАмериканский пирог - опрос

Просто интересно, кому какой больше нравится, возможно несколько вариантов ответа. Не забываем оставлять комментарии....

Американский пирог 4 выйдет в апреле 2012 годаАмериканский пирог 4 выйдет в апреле 2012 года

Студия Universal Pictures назвала дату релиза четвертой части «Американского пирога» – 6 апреля 2912 года. Премьеры предыдуших фильмов проходили в лет...

Мама Стифлера возвращается в Американский пирог 4Мама Стифлера возвращается в Американский пирог 4

Дженнифер Кулидж возвращается к своей роли мамы Стифлера в четвертой части «Американского пирога» – фильме «American Reunion».«Сиквелы – это очень сло...

Загрузка...
Комментарии

Margasan
28 июля 2009 10:04
Помню, как в общаге (был я ещё студентом) мы арбуз делили на 7 человек. Циркули, линейки, калькуляторы ...
Но поделили, если визуально, честно!

meccep
28 июля 2009 10:28
Что тут скажешь.. люди наукой занимаются :)

Andrei
28 июля 2009 10:33
Да людям неПисюны делать )))

Блим Кололей
28 июля 2009 10:50
очень важное открытие

FuryPaladin
28 июля 2009 11:13
Взять транспортир и каждому дать кусок с тупым углом в 120 градусов...

nettle
28 июля 2009 12:47
ну теперь можно спать спокойно) самое главное учёные выяснили...

Gadkiy
28 июля 2009 14:48
FuryPaladin
Взять транспортир и каждому дать кусок с тупым углом в 120 градусов...

Ты бы хоть статью прочитал что ли...

MWt
28 июля 2009 15:09
имхо, это уже давно было известно..

michael vincy
28 июля 2009 19:42
а фильм Игры Разума крут!

Психопат
28 июля 2009 22:57
Margasan,

гГ,чел жжЖоть)))
Цыркули реШают))

Jauhen
29 июля 2009 00:05
Если можно делать несколько разрезов и долю компановать из нескольких кусочков, то задача тривиальна.)
Человек режет торт на равные по его мнению куски. Остальные голосованием выбирают самый маленький на их взгляд и отдают резавшему. И так для любого числа участников.
Посетители, находящиеся в группе Гости, не могут оставлять комментарии в данной новости.
Воскресенье, 25 Июня
USD 1.9284
EUR 2.1544
RUB 0.0323
kotad 53 минут назад
Цитата: Mab
У тебя мозгов нет.

если у тебя мозгов много, то почему ты нищий и безработный? а, плечевая дура маблер псаки?
Цитата: Mab
Остальное не важно.

LOL. и это говорит жертва инцеста и кому в детстве "пистолетом" прочистили "задний гудок".
Mab 78 минут назад
Цитата: kotad
- у меня

У тебя мозгов нет. Остальное не важно.

Агент ФСБ Гравер, приехавший вербовать офицеров СБУ, задержан в Одессе, - журналист. ФОТО
PROSTO CHEL 97 минут назад Та стопудово вброс какой-то. Не поверю что на свете есть такая паскудно-скулящая без дела падоль. kotad 99 минут назад
Цитата: Mab
Оно и заметно...

"заметно" - у меня трудового стажа и знаний по больше, чем у тебя тварь безработная!!!
Цитата: Mab
Ты только сегодня узнал

так какого ХРЕНА ты, маблер псаки лезешь во все темы, мразота педарастная? СЛИЛСЯ, ЗНАЧИТ СЛИЛСЯ!!!! и не плачь малолетка, твоё же место - в дерьме!!!
Nikitosina 102 минут назад
Цитата: Slayer23
Она ничем не рискует- это же российская сборная.

+100500)))
cube.by 130 минут назад напомнило https://www.youtube.com/watch?v=f-absN87sII

там наверное 150 зевак было
Nikitosina 145 минут назад Мав, работу нашел? Или у родителей по прежнему в сорок лет на шее сидишь и на судьбинушку жалишься? Nikitosina 148 минут назад
Цитата: Mab
Асфальт вообще уничтожен.

Я ехал сегодня с площади победы в Уручье. Нет, асфальт в порядке.

Цитата: smav
вот она бульбажорская стабильность )))и без солдат нато местные ватники сами себя разъёбут ))

Привет ватник!
Чо на говно исходишь? С завода не сократили старпер?
Новости от партнеров
Сейчас на сайте
26 пользователей, 785 гостей