Ирада Зейналова рассказала, почему послала тобольского мальчика  есть видео  6
Сегодня в 18:25
    
3
декабря
27.07.2009 / 19:51

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

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

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

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

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

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

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

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

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


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

Ирада Зейналова рассказала, почему послала тобольского мальчика
Ирада Зейналова рассказала, почему послала тобольского мальчика  есть видео  6
Сегодня в 18:25
Телеведущая и журналист Ирада Зейналова, которая не так давно перешла работать с Первого канала на НТВ, рассказала, почему она сорвалась и послала попавшего в кадр тобольского мальчика.
Тюменских бомжей учили противодействовать терроризму
Тюменских бомжей учили противодействовать терроризму  19
29.11 / 17:29
В центре социальной помощи лицам без определенного места жительства и лицам, освободившимся из учреждений УФСИН, прошел очередной просмотр фильма «Антитеррор: как предотвратить теракт?».
Дан Запашный ищет хозяев коту, живущему в тюменском цирке
Дан Запашный ищет хозяев коту, живущему в тюменском цирке  1
29.11 / 11:27
Дрессировщик Дан Запашный из знаменитой цирковой династии обратился к жителям Тюмени в соцсетях. Он хочет найти хозяина коту, который временно проживает в цирке.
Арт-объект или безвкусица? Тюменцы обсуждают «бутылочные елки»
Арт-объект или безвкусица? Тюменцы обсуждают «бутылочные елки»  12
27.11 / 14:24
Необычные новогодние деревья удивили тюменцев. В одном из тюменских пабликов появились фотографии елочек, собранных из зеленых пластиковых бутылок.
На книжный магазин подали в суд за сказку «Конек-Горбунок»
На книжный магазин подали в суд за сказку «Конек-Горбунок»  85
21.11 / 11:26
На родине Петра Ершова внимание местного Роспотребнадзора привлекла известная сказка «Конек-Горбунок». Одному из книжных магазинов Ишима и его владелице грозит штраф за распространение информации, «которая может причинить вред здоровью или развитию детей».
Легковушка буксирует тяжелый погрузчик: тюменцы обсуждают забавное видео
Легковушка буксирует тяжелый погрузчик: тюменцы обсуждают забавное видео  есть видео  19
20.11 / 14:36
«Мал клоп, да силен» — тюменцы обсуждают короткое видео, опубликованное в соцсетях накануне, 19 ноября, короткое видео. На одной из улиц города легковая машина Toyota Vitz буксирует многотонный погрузчик.
Тюменка ополчилась на «уродку» из букваря
Тюменка ополчилась на «уродку» из букваря  65
24.10 / 14:05
Детское стихотворение поэта Саши Черного, включенное в школьный букварь, возмутило жительницу Тюмени. Недовольная рифмой тюменка готова даже обратиться в правоохранительные органы.
«Разделись чуть ли не до трусов»: туристам не дали снять клип в Тюремном замке
«Разделись чуть ли не до трусов»: туристам не дали снять клип в Тюремном замке  12
19.10 / 12:45
Забавный случай на днях произошел в Тюремном замке Тобольска. Трое молодых людей из Екатеринбурга решили снять видео на фоне стен музейного комплекса, но взгляды на творчество туристов и сотрудников учреждения разошлись.
Тюремные сухари из Тобольска признаны лучшим сувениром
Тюремные сухари из Тобольска признаны лучшим сувениром  4
18.10 / 13:37
Призером всероссийского конкурса «Туристический сувенир» стал тобольский историко-архитектурный музей-заповедник. Сухари из тюремной чайной «По кругу», подушка «Таблица Дмитрия Менделеева» и другие сувениры вошли в число победителей, завоевав четыре вторых места.
Тюменцы считают жителей Италии и Испании самыми красивыми из иностранцев
Тюменцы считают жителей Италии и Испании самыми красивыми из иностранцев  есть опрос  9
17.10 / 08:49
Тюменцы считают, что самые привлекательные в мире люди живут в России. Если же говорить об иностранцах, то наши земляки отдают должное красоте жителей Италии и Испании.

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

Реклама:










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

Архив

Интервью

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

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