РЕКЛАМА

Загрузка...

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

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

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

Ученые из Стэнфордского университета создали алгоритм так называемого "честного деления пирога" на трех человек. Статья исследователей пока еще не принята к публикации, однако ее препринт доступен на сайте arXiv.org.
Проблема "честного деления пирога" в самой простой формулировке звучит следующим образом. Предположим, что необходимо поделить пирог на N человек. При этом нам известно, что у каждого из них имеются собственные критерии сравнения различных кусков пирога. Например, кому-то больше нравится кусок с украшениями, а кто-то не любит, когда слишком много начинки. Возникает вопрос, всегда ли можно разрезать пирог так, что каждый из N человек остался доволен, то есть, сравнив свой кусок с остальными, пришел бы к выводу, что его не обделили.
В 1980 году американский математик Уолтер Стромкуист (Walter Stromquist) доказал, что для любого набора критериев, которых придерживаются эти N человек, пирог можно разрезать справедливо ровно за N-1 разрезов. Однако доказательство Стромкуиста не было конструктивным, то есть он не предъявил конкретный алгоритм.
В рамках новой работы математики занимались именно поиском конкретного алгоритма, то есть последовательности действий разрезающего. В полном объеме им решить задачу не удалось, однако они построили алгоритм, который позволяет примерно делить пирог между тремя людьми всего за два разреза. Кроме этого исследователям удалось доказать важное свойство, что задача принадлежит к классу так называемых PPAD-задач. (http://en.wikipedia.org/wiki/PPAD_(complexity))
Данный класс привлекает пристальное внимание ученых в последнее время. Дело в том, что в нем лежит так называемая задача вычисления равновесия Нэша, названного так в честь Джона Нэша, известного широкой публике по фильму "Игры разума". Равновесие Нэша - такой тип решения игры нескольких участников, при котором ни один не может увеличить выигрыш, изменив свое решение в одностороннем порядке, если остальные участники свои решения не меняют.
11
1487
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
Если можно делать несколько разрезов и долю компановать из нескольких кусочков, то задача тривиальна.)
Человек режет торт на равные по его мнению куски. Остальные голосованием выбирают самый маленький на их взгляд и отдают резавшему. И так для любого числа участников.
Посетители, находящиеся в группе Гости, не могут оставлять комментарии в данной новости.
Воскресенье, 22 Января
USD 1.9361
EUR 2.0711
RUB 0.0324
Либерман 5 минут назад
Цитата: Mab
Я верю что НН перепечалатала всё именно так как было написано на Спутнике. Вся ответственность за правдивость инфы лежит на Спутнике.

А ответственность за веру в правдивость инфы на Спутнике и за дальнейшее ее распространение тут - полностью на тебе.
Цитата: Mab
До сегодняшнего для я считал sputnik нормальным источником инфы

Цитата: Mab
«Спутнік» — агенцтва навінаў, заснаванае падкантрольным ураду Расіі агенцтвам «Россія сегодня». Генеральны дырэктар — прапагандыст Дзмітрый Кісялёў.

Вот это поворот. Маб киселевщину на банане распространяет )))
Tatur 14 минут назад
Цитата: basalt155
фрр брр слава Богу я не на его месте был. это ж трындец

у вас там, на МТЗ немало девах на конвейере работает, неужто не одна к тебе за столько лет не подкатила)
3ara3a 16 минут назад Политизированное, низкосортное шоу фриков..... А в этом году кастрюлеголовые особенно напрягутся, чтобы обосраться по максимуму ))) У них это хорошо получается. 050822 63 минут назад не пройдут даже в финал...


Цитата: gismo_2
gismo_2
Вчера, 12:29
Цитата: западная ведьма
не хочу обидеть вас, братья белорусы, но мне как то не очень(

Ой, сидела бы и молчала, критик доморощенный. Все очень даже хорошо. Или ты пытаешься к себе внимание привлечь?


мне тоже не понравилось, уже отправляли похожих....
Mab 88 минут назад
Sputnik.by прыпісаў спеваку Lermont словы пра мёртвую мову і пасля зняў іх

«Вы апублікавалі інфармацыю, якая не адпавядае рэчаіснасці. Гаворка пра фразу «беларуская мова — мёртвая». Вы ўзялі яе з партала sputnik.by, які прыпісаў нам тое, чаго мы не казалі. І пазней прыбраў гэта выказванне», — напісаў Васіль Селішчаў у «Арт-Сядзібу».

«Спутнік» — агенцтва навінаў, заснаванае падкантрольным ураду Расіі агенцтвам «Россія сегодня». Генеральны дырэктар — прапагандыст Дзмітрый Кісялёў.

Слоган «Спутніка» — «Распавядаем недамоўленае» («Говорим то, о чем другие молчат»).
PROSTO CHEL 126 минут назад
Цитата: danrom
будем надеяться что просто вчера крафта перепил и ещё исправится

Или будет померать весь день и вообще фиг че запостит
danrom 129 минут назад
Цитата: PROSTO CHEL
Ванеев не запостил Россыпь красивых фотографий.

будем надеяться что просто вчера крафта перепил и ещё исправится

з.ы. а у Вади часы на 5 минут отстают
PROSTO CHEL 134 минут назад Из-за Трампа, Ванеев не запостил Россыпь красивых фотографий. Совпадение, не думаю. Стопудошки дело в Трампе, может стоит прислушаться к Малибушке??
Новости от партнеров

ИНТЕРЕСНОЕ:

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