РЕКЛАМА

Загрузка...

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

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

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

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

Так он педик по ходу,такой же как и ты,вот и послала.
Flint 207 минут назад 55hozinu,
Молодец)))))))))
Flint 209 минут назад Kano,
Хыхыхы. Можешь даже на мена без ответно вякнуть, посмеемся вместе))
Филин 227 минут назад seregas,
Не думаю, что кто-то стал бы снимать противовес ради вечеринки. Конструкция стрелы не располагает для грузов выше 4 тонн. А тут вылет почти на максимум, вертикальное положение без наклона, конструкция и пляшущие черти. Небось еще и ось передняя двухколесная.
В самом конце видно, как конструкция соскальзывает с вил, значит она не была зафиксирована. Быстрее всего при плясках эта конструкция потихоньку сдвигалась к краю вил пока не перевесила.
Kano 302 минут назад Потому что мозг надо иметь. А не только черепную коробку. Kano 305 минут назад Ну в Китае на 1 девченку по статистике 10 ребят. Это не у нас "греби кого попало бо до 30 замуж очень надо, а с мужиками дефицит" Поэтому девачка выпендрэваецца.

Цитата: basalt155
у нас работает мужик ему 37 лет пошёл на свидание с букетом роз за 50 рублей)) она посмотрела сказала иди нах))
Странная логика у мужиков, купил цветы, значит должна дева растаять. А если он ей не нравится совсем? Я бы тоже послала.
rexdeus_live 310 минут назад расстрелять всех Sharki 316 минут назад терь ясно спец назночения этих войск на праздниках погулять эх а раньше мы там гуляли
Новости от партнеров

ИНТЕРЕСНОЕ:

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