РЕКЛАМА

Загрузка...

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

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

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

Ученые из Стэнфордского университета создали алгоритм так называемого "честного деления пирога" на трех человек. Статья исследователей пока еще не принята к публикации, однако ее препринт доступен на сайте arXiv.org.
Проблема "честного деления пирога" в самой простой формулировке звучит следующим образом. Предположим, что необходимо поделить пирог на N человек. При этом нам известно, что у каждого из них имеются собственные критерии сравнения различных кусков пирога. Например, кому-то больше нравится кусок с украшениями, а кто-то не любит, когда слишком много начинки. Возникает вопрос, всегда ли можно разрезать пирог так, что каждый из N человек остался доволен, то есть, сравнив свой кусок с остальными, пришел бы к выводу, что его не обделили.
В 1980 году американский математик Уолтер Стромкуист (Walter Stromquist) доказал, что для любого набора критериев, которых придерживаются эти N человек, пирог можно разрезать справедливо ровно за N-1 разрезов. Однако доказательство Стромкуиста не было конструктивным, то есть он не предъявил конкретный алгоритм.
В рамках новой работы математики занимались именно поиском конкретного алгоритма, то есть последовательности действий разрезающего. В полном объеме им решить задачу не удалось, однако они построили алгоритм, который позволяет примерно делить пирог между тремя людьми всего за два разреза. Кроме этого исследователям удалось доказать важное свойство, что задача принадлежит к классу так называемых PPAD-задач. (http://en.wikipedia.org/wiki/PPAD_(complexity))
Данный класс привлекает пристальное внимание ученых в последнее время. Дело в том, что в нем лежит так называемая задача вычисления равновесия Нэша, названного так в честь Джона Нэша, известного широкой публике по фильму "Игры разума". Равновесие Нэша - такой тип решения игры нескольких участников, при котором ни один не может увеличить выигрыш, изменив свое решение в одностороннем порядке, если остальные участники свои решения не меняют.
11
1513
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
Если можно делать несколько разрезов и долю компановать из нескольких кусочков, то задача тривиальна.)
Человек режет торт на равные по его мнению куски. Остальные голосованием выбирают самый маленький на их взгляд и отдают резавшему. И так для любого числа участников.
Посетители, находящиеся в группе Гости, не могут оставлять комментарии в данной новости.
Пятница, 28 Апреля
USD 1.8740
EUR 2.0414
RUB 0.0329
SabakaZ 8 минут назад
Цитата: западная ведьма
на чысто интуитивном уровне ощущение,что навальный каката темная лошадка. хотелось бы альтернативы.
Конечно онъ не простъ, но ужъ точно не плоше вышеозначенныхъ. А альтернативу не такъ давно на Москворецкомъ мосту загубили опричники царя вашаго.
Margasan 10 минут назад С "турбонаддувом"? shield1 10 минут назад Бляя) 22 и 27 надо было для свадебной рубрики оставить) Margasan 11 минут назад Болезнь? Норма? Или 5%? SabakaZ 15 минут назад Наибольшее негодованiе вызвала мамзель съ четвертой фотокарточки. Съ такимъ наборомъ объектовъ поклоненiя какъ на заднемъ плане въ голове нужно иметь даже не сквознякъ, а лошадиные газы.
Высечь, сослать въ Чебоксары на картофельную плантацiю.

А холопы съ 23 фотокарточки, какъ я разумею, втроемъ обоюдно будутъ писаннымъ на телесах маятся? Сами себе написали, кабы не забыть ненарокомъ?
западная ведьма 19 минут назад SabakaZ,
нет,ты не прав,димон,кисилев и путин мне еще больше не нравятся. на чысто интуитивном уровне ощущение,что навальный каката темная лошадка. хотелось бы альтернативы.
фильм этот досмотрела до момента,как он доказывал,что кроссовки именно Медведева))
Mab 25 минут назад
Цитата: dembelvdv
от чего ты взял что они лесбиянки?

А от чего ты взял что нет?
Если бы в таких позах фоткались мужики то ты бы один из первых кричал что они педики.
SabakaZ 28 минут назад
Цитата: западная ведьма
ай,чет не нравится мне этот Навальный..
Не удивленъ. Про товарища Киселева речи не веду, ибо пошлое и глупое деянiе, батраковъ дурныхъ достойное, когда нечего ответить. Но у васъ тамъ и безъ оного малохольного хватаетъ источниковъ, непрестанно напоминающихъ вамъ, что господинъ Навальный вамъ (же) категорически всяко не по нраву.
Новости от партнеров
Сейчас на сайте
68 пользователей, 1921 гость