РЕКЛАМА

Загрузка...

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

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

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

Ученые из Стэнфордского университета создали алгоритм так называемого "честного деления пирога" на трех человек. Статья исследователей пока еще не принята к публикации, однако ее препринт доступен на сайте arXiv.org.
Проблема "честного деления пирога" в самой простой формулировке звучит следующим образом. Предположим, что необходимо поделить пирог на N человек. При этом нам известно, что у каждого из них имеются собственные критерии сравнения различных кусков пирога. Например, кому-то больше нравится кусок с украшениями, а кто-то не любит, когда слишком много начинки. Возникает вопрос, всегда ли можно разрезать пирог так, что каждый из N человек остался доволен, то есть, сравнив свой кусок с остальными, пришел бы к выводу, что его не обделили.
В 1980 году американский математик Уолтер Стромкуист (Walter Stromquist) доказал, что для любого набора критериев, которых придерживаются эти N человек, пирог можно разрезать справедливо ровно за N-1 разрезов. Однако доказательство Стромкуиста не было конструктивным, то есть он не предъявил конкретный алгоритм.
В рамках новой работы математики занимались именно поиском конкретного алгоритма, то есть последовательности действий разрезающего. В полном объеме им решить задачу не удалось, однако они построили алгоритм, который позволяет примерно делить пирог между тремя людьми всего за два разреза. Кроме этого исследователям удалось доказать важное свойство, что задача принадлежит к классу так называемых PPAD-задач. (http://en.wikipedia.org/wiki/PPAD_(complexity))
Данный класс привлекает пристальное внимание ученых в последнее время. Дело в том, что в нем лежит так называемая задача вычисления равновесия Нэша, названного так в честь Джона Нэша, известного широкой публике по фильму "Игры разума". Равновесие Нэша - такой тип решения игры нескольких участников, при котором ни один не может увеличить выигрыш, изменив свое решение в одностороннем порядке, если остальные участники свои решения не меняют.
11
1461
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
Если можно делать несколько разрезов и долю компановать из нескольких кусочков, то задача тривиальна.)
Человек режет торт на равные по его мнению куски. Остальные голосованием выбирают самый маленький на их взгляд и отдают резавшему. И так для любого числа участников.
Посетители, находящиеся в группе Гости, не могут оставлять комментарии в данной новости.
Вторник, 06 Декабря
USD 1.9706
EUR 2.0897
RUB 0.0308
spaceman 10 минут назад
Цитата: западная ведьма
........нет слов
у вас в азии так не делают?
diablo1986 168 минут назад Офигеть, он чуть заточкой об потолок не ебнулся!
Trend 180 минут назад она с украины.
стриптиз прикольно ебошит
Butters 309 минут назад RDF 358 минут назад
Цитата: dianest
т.е. вот так, открыто, ты взял и признался что педик?

он никогда и не скрывал
Mab 369 минут назад
Цитата: Либерман
Херасе, мера у тебя - два литра джин-тоника.Хотя чо это я, для твоей меры "почти в говно" - самое оно.

Ну было 1 раз в жизни такое, причем очень давно.
западная ведьма 390 минут назад 26-128,
Либерман,
ужасно,как такое могло случиться
Либерман 398 минут назад
Цитата: западная ведьма
Либерман, вот ты же умный человек, вот объясни,если можешь, откуда у чеченцев в первую войну столько оружия?

С военных складов, захваченных и оставленных при выводе российских войск из республики.
Новости от партнеров

ИНТЕРЕСНОЕ:

Загрузка...
Сейчас на сайте
5 пользователей, 1428 гостей