Депутат Госдумы предложил считать Змея Горыныча и Соловья-разбойника украинцами  21
13.01 / 13:51
    
24
января
27.07.2009 / 19:51

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

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

Проблема «честного деления пирога» в самой простой формулировке звучит следующим образом. Предположим, что необходимо поделить пирог на N человек. При этом нам известно, что у каждого из них имеются собственные критерии сравнения различных кусков пирога. Например, кому-то больше нравится кусок с украшениями, а кто-то не любит, когда слишком много начинки. Возникает вопрос, всегда ли можно разрезать пирог так, что каждый из N человек остался доволен, то есть, сравнив свой кусок с остальными, пришел бы к выводу, что его не обделили.

В 1980 году американский математик Уолтер Стромкуист (Walter Stromquist) доказал, что для любого набора критериев, которых придерживаются эти N человек, пирог можно разрезать справедливо ровно за N-1 разрезов. Однако доказательство Стромкуиста не было конструктивным, то есть он не предъявил конкретный алгоритм.

В рамках новой работы математики занимались именно поиском конкретного алгоритма, то есть последовательности действий разрезающего. В полном объеме им решить задачу не удалось, однако они построили алгоритм, который позволяет примерно делить пирог между тремя людьми всего за два разреза. Кроме этого исследователям удалось доказать важное свойство, что задача принадлежит к классу так называемых PPAD-задач.

Данный класс привлекает пристальное внимание ученых в последнее время. Дело в том, что в нем лежит так называемая задача вычисления равновесия Нэша, названного так в честь Джона Нэша, известного широкой публике по фильму «Игры разума». Равновесие Нэша — такой тип решения игры нескольких участников, при котором ни один не может увеличить выигрыш, изменив свое решение в одностороннем порядке, если остальные участники свои решения не меняют.

Считаешь это интересным? Поделись с друзьями.
Источник: Лента.ру

Просмотров: 975 | верcия для печати
Читайте новости по темам: Ученые, Еда

 
 Комментарии  0  


Другие новости рубрики «Калейдоскоп»

Тюменцы вытолкали попавший в колею автобус
Тюменцы вытолкали попавший в колею автобус  есть видео  8
13.01 / 14:52
Забавное видео обсуждают в социальных сетях жители Тюмени. На видеохостинге Youtube на днях был выложен ролик, как автобус 25-го маршрута, застрявший в колее, выручают прохожие.
Депутат Госдумы предложил считать Змея Горыныча и Соловья-разбойника украинцами
Депутат Госдумы предложил считать Змея Горыныча и Соловья-разбойника украинцами  21
13.01 / 13:51
Депутат Госдумы Александр Сидякин предложил считать Соловья-разбойника и Змея Горыныча персонажами украинского фольклора.
Тюменцы больше не хотят встречать Новый год с Пугачевой
Тюменцы больше не хотят встречать Новый год с Пугачевой  62
11.01 / 13:09
Тюменцы поддерживают запущенную на сайте change.org петицию — телезрители, недовольные содержанием новогоднего эфира, обращаются к главе Первого канала. Константина Эрнста просят провести опрос среди телезрителей чтобы выяснить, что действительно хотят увидеть россияне в следующую новогоднюю ночь.
На мосту Мельникайте висел баннер с неприличной надписью
На мосту Мельникайте висел баннер с неприличной надписью  14
04.01 / 18:32
Необычный баннер с нецензурной надписью вывесили в Тюмени неизвестные «шутники» на мосту по улице Мельникайте. Фотографии странной рекламной конструкции, появились сегодня, 4 января, с городских сообществах социальных сетей.
В ночь на 4 января тюменцы смогут загадать желание на падающую звезду
В ночь на 4 января тюменцы смогут загадать желание на падающую звезду
03.01 / 09:47
Тюменцы, которые по каким-то причинам не успели загадать желание, пока били куранты, смогут исправиться и попросить помощи в исполнении мечты у падающих звезд — в ночь на 4 января ожидается пик метеорного потока Квадрантиды.
Видео со смелым песцом умилило тюменцев
Видео со смелым песцом умилило тюменцев  есть видео  4
12.12.2016 / 12:16
Тюменцы в социальных сетях обсуждают появившийся в интернете видеоролик со смелым песцом, который подошел совсем близко к людям.
Ирада Зейналова рассказала, почему послала тобольского мальчика
Ирада Зейналова рассказала, почему послала тобольского мальчика  есть видео  46
03.12.2016 / 18:25
Телеведущая и журналист Ирада Зейналова, которая не так давно перешла работать с Первого канала на НТВ, рассказала, почему она сорвалась и послала попавшего в кадр тобольского мальчика.
Тюменских бомжей учили противодействовать терроризму
Тюменских бомжей учили противодействовать терроризму  18
29.11.2016 / 17:29
В центре социальной помощи лицам без определенного места жительства и лицам, освободившимся из учреждений УФСИН, прошел очередной просмотр фильма «Антитеррор: как предотвратить теракт?».
Дан Запашный ищет хозяев коту, живущему в тюменском цирке
Дан Запашный ищет хозяев коту, живущему в тюменском цирке  1
29.11.2016 / 11:27
Дрессировщик Дан Запашный из знаменитой цирковой династии обратился к жителям Тюмени в соцсетях. Он хочет найти хозяина коту, который временно проживает в цирке.
Арт-объект или безвкусица? Тюменцы обсуждают «бутылочные елки»
Арт-объект или безвкусица? Тюменцы обсуждают «бутылочные елки»  12
27.11.2016 / 14:24
Необычные новогодние деревья удивили тюменцев. В одном из тюменских пабликов появились фотографии елочек, собранных из зеленых пластиковых бутылок.

Все новости из рубрики «Калейдоскоп»

Реклама:










Создание и разработка сайтов в Тюмени

Архив

Интервью

Новости от Нашгород.ру

Северное волокно
© 2002—2017, OOO «Наш Город РУ», Тюмень, Все права защищены © При использовании материалов ссылка обязательна.
Свидетельство о регистрации СМИ Эл № ФС 77–20303 от 29 декабря 2004 выдано Федеральной службой по надзору
за соблюдением законодательства в сфере массовых коммуникаций и охране культурного наследия. © Разработка — студия «Автограф»