В мир иной отправился принц Саудовской Аравии  13
08.08 / 17:14
    
19
августа
27.07.2009 / 19:51

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

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

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

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

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

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

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

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

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


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

«Одноклассники» запустили сервис «Настроения»
«Одноклассники» запустили сервис «Настроения»
17.08 / 16:14
Социальная сеть «Одноклассники» запустили новый формат публикаций, с помощью которого пользователи смогут поделиться своим настроением с друзьями и подписчиками. Сервис «Настроения» позволяет установить статус с ярким фоном в ленте своего профиля и дополнить его своим текстом.
Тюменец нашел на дачном участке зуб мамонта (ФОТО)
Тюменец нашел на дачном участке зуб мамонта (ФОТО)  16
15.08 / 17:36
Необычный урожай: тюменец нашел на дачном участке не какую-нибудь свеклу и даже не зарытую соседской собакой кость, а настоящий зуб мамонта.
Популярный видеоблогер запускает в соцсети шоу «Соболев бомбит»
Популярный видеоблогер запускает в соцсети шоу «Соболев бомбит»  8
15.08 / 10:12
В социальной сети «ВКонтакте» прошла премьера шоу «Соболев бомбит». В эфире программы один из самых популярных блогеров России Николай Соболев возит звездных гостей на такси и задает вопросы из школьной программы.
В мир иной отправился принц Саудовской Аравии
В мир иной отправился принц Саудовской Аравии  13
08.08 / 17:14
Королевский двор Саудовской Аравии сообщил о кончине принца.
Лунное затмение смогут наблюдать жители всех регионов России
Лунное затмение смогут наблюдать жители всех регионов России
07.08 / 09:26
Частичное лунное затмение могут увидеть россияне сегодня, 7 августа.
«Фонтан универсальный - в нем и купаются, и нужду справляют»
«Фонтан универсальный — в нем и купаются, и нужду справляют»  17
26.07 / 11:29
Полуголая женщина, устроившая «банный день» в фонтане, возмутила жителей микрорайона «Европейский». Фотографии купания тюменки с ребенком очевидцы выложили в соцсети.
Скончался 20-летний мэр города Талкитна - рыжий Стаббс
Скончался 20-летний мэр города Талкитна — рыжий Стаббс  3
24.07 / 13:54
В США скончался мэр города Талкитна. Неофициально эту должность с 1997 года занимал рыжий кот по прозвищу Стаббс. Хвостатый «чиновник» за свою долгую карьеру пережил покушение и переизбирался на пост.
На тюменском «Курятнике» похвастаются яйцами?
На тюменском «Курятнике» похвастаются яйцами?  10
21.07 / 17:17
Фестиваль яйца «Курятник» предлагают провести молодые предприниматели Тюменского района. На их взгляд, это подходящее и нужное для региона событие.
Крупнейшие паблики «ВКонтакте» запускают первое онлайн реалити-шоу
Крупнейшие паблики «ВКонтакте» запускают первое онлайн реалити-шоу
20.07 / 15:53
Крупнейшие паблики «ВКонтакте» — MDK, Палата № 6, Борщ и Корпорация Зла — запускают первое онлайн реалити-шоу при поддержке vk.com.
В «Одноклассниках» появились счетчики просмотров публикаций
В «Одноклассниках» появились счетчики просмотров публикаций
17.07 / 15:17
Социальная сеть «Одноклассники» открыла пользователям количество просмотров личных постов. Счетчик расположен под каждой публикацией и доступен только ее автору. Ранее в соцсети запустили счетчики просмотров для групп — данные по темам групп видны только их администрации.

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

Реклама:




Архив

Интервью

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

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