Тюменцы в Перми украли кошку?  есть видео  12
21.03 / 15:56
    
24
марта
27.07.2009 / 19:51

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

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

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

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

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

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

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

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

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


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

Тюменцы в Перми украли кошку?
Тюменцы в Перми украли кошку?  есть видео  12
21.03 / 15:56
Видео, где двое молодых людей выходят из подъезда с кошкой и садятся в автомобиль, разместила в соцсетях жительница Перми. Женщина утверждает, что домашнее животное украли, а у автомобиля злоумышленников — тюменские номера.
Тюменская область оказалась на вершине рейтинга по «индексу шаурмы»
Тюменская область оказалась на вершине рейтинга по «индексу шаурмы»  11
11.03 / 15:47
Комитет гражданских инициатив совместно с форумом разработчиков Open Data Day подготовил «рейтинг шаурмы». Тюменской области в нем присудили четвертое место.
РПЦ решила отмечать в России День святого Патрика
РПЦ решила отмечать в России День святого Патрика  12
10.03 / 16:19
С этого года по решению Священного Синода в России будут отмечать 30 марта День святого Патрика — покровителя Ирландии. Тюменский священник Григорий Мансуров рассказал, что признание древних святых, живших и служивших еще до разделения христианских церквей — самая обычная практика. И никакой сенсации в этом нет.
Андрей Макаревич введет моду на отказ от выпускных?
Андрей Макаревич введет моду на отказ от выпускных?  89
02.03 / 15:24
В интернете после заявления известного музыканта, лидера группы «Машина времени» Андрея Макаревича об отказе оплачивать расходы на выпускной своей дочери разгорелись бурные обсуждения.
«Зову тебя Россиею»: тоболяки отличились с именем для дочери
«Зову тебя Россиею»: тоболяки отличились с именем для дочери  29
28.02 / 15:19
Одна тобольская пара решила, что Машей или Дашей в семье никого не удивишь. Свою новорожденную дочку родители назвали Россией.
26 февраля жители Земли увидят уникальное солнечное затмение
26 февраля жители Земли увидят уникальное солнечное затмение
24.02 / 09:52
Эффектное кольцеобразное солнечное затмение увидят жители Земли в воскресенье, 26 февраля. Правда в родном городе тюменцы не смогут понаблюдать за уникальным астрономическим явлением.
Собака-герой из соцсетей добралась до Тюмени
Собака-герой из соцсетей добралась до Тюмени  1
20.02 / 15:09
Собака, спасающая зажатых дверями автобуса школьников, добралась и до Тюмени. О трогательном случае сообщил пользователь одного из тюменских пабликов ВКонтакте.
В Тюменской области прокурор нашел рецепт взрывчатки в Minecraft
В Тюменской области прокурор нашел рецепт взрывчатки в Minecraft  35
07.02 / 14:46
Популярную игру Minecraft едва не запретили в России по решению Заводоуковского районного суда Тюменской области за рецепт создания динамита.
Тюменцы вытолкали попавший в колею автобус
Тюменцы вытолкали попавший в колею автобус  есть видео  8
13.01 / 14:52
Забавное видео обсуждают в социальных сетях жители Тюмени. На видеохостинге Youtube на днях был выложен ролик, как автобус 25-го маршрута, застрявший в колее, выручают прохожие.
Депутат Госдумы предложил считать Змея Горыныча и Соловья-разбойника украинцами
Депутат Госдумы предложил считать Змея Горыныча и Соловья-разбойника украинцами  21
13.01 / 13:51
Депутат Госдумы Александр Сидякин предложил считать Соловья-разбойника и Змея Горыныча персонажами украинского фольклора.

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

Реклама:










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

Архив

Интервью

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

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