«Бессмертный полк» в «Одноклассниках»: более 400 тысяч человек приняли участие  19
11.05 / 12:48
    
24
мая
27.07.2009 / 19:51

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

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

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

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

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

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

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

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

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


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

«Одноклассники» включили песни украинских артистов в список рекомендуемых
«Одноклассники» включили песни украинских артистов в список рекомендуемых  1
18.05 / 08:48
Социальная сеть «Одноклассники» решила поддержать контент украинских артистов и включила их песни и клипы в топ рекомендуемых видеороликов и аудиосборников.
«Бессмертный полк» в «Одноклассниках»: более 400 тысяч человек приняли участие
«Бессмертный полк» в «Одноклассниках»: более 400 тысяч человек приняли участие  19
11.05 / 12:48
Ко Дню Победы социальная сеть «Одноклассники» провела онлайн-акцию «Бессмертный Полк». С помощью специальной формы публикации каждый желающий смог поделиться фотографиями ветеранов Великой Отечественной войны. В акции приняли участие более 400 тысяч человек, в среднем пользователи добавляли около 10 фотографий в секунду.
Голый автостоп тюменки пресекла полиция
Голый автостоп тюменки пресекла полиция  9
11.05 / 12:39
Ранним утром 10 мая тюменские водители, проезжавшие пересечение улиц 50 лет ВЛКСМ и Салтыкова-Щедрина наблюдали незаурядную картину. Девушка «в костюме Евы» разгуливала вдоль дороги и даже пыталась остановить проходившие мимо машины.
По Тюмени гулял голый Гендальф?
По Тюмени гулял голый Гендальф?  12
10.05 / 13:26
Странного гражданина, облаченного только в плед и носки, заметили случайные прохожие в районе улицы Совхозной. Фотографиями необычной прогулки горожане поделились в социальных сетях.
16 мая стартуют продажи новой версии Nokia 3310. А вы бы купили?
16 мая стартуют продажи новой версии Nokia 3310. А вы бы купили?  есть опрос  30
07.05 / 16:36
Продажи обновленной версии телефона Nokia 3310 начнутся в России уже 16 мая. По данным производителей, он будет работать без подзарядки месяц в режиме ожидания и 22 часа в режиме разговора. Интернет-портал NashGorod.ru поинтересовался у экспертов в области телекома и обычных тюменцев, что они думают по поводу судьбы новой версии Nokia 3310 в России. Будет ли этот телефон пользоваться популярностью у наших соотечественников?
В Тюмени отметят День Гарри Поттера
В Тюмени отметят День Гарри Поттера
07.05 / 11:28
Тюменские поклонники книг Джоан Роулинг соберутся, чтобы отметить Международный день Гарри Поттера.
Одноклассники помогут раскрасить черно-белые фотографии к 9 мая
Одноклассники помогут раскрасить черно-белые фотографии к 9 мая
05.05 / 13:03
Ко Дню Победы социальная сеть «Одноклассники» запускает сервис для раскрашивания черно-белых фотографий. Приложение «9 мая. Яркая память» с помощью нейронной сети сделает цветными памятные снимки военных лет.
Тюменка Юлия проводит голодовку у областной администрации. Связано ли это с игуанами?
Тюменка Юлия проводит голодовку у областной администрации. Связано ли это с игуанами?  121
04.05 / 15:33
Тюменская зоозащитница, добивавшаяся лучшей доли для игуан, живущих в магазинах ювелирной сети, вышла сегодня, 4 мая, на голодовку к крыльцу областной администрации.
«ВКонтакте» перезапустила музыкальный сервис
«ВКонтакте» перезапустила музыкальный сервис
28.04 / 14:39
Социальная сеть «ВКонтакте» впервые за десять лет полностью обновила музыкальный раздел на всех платформах.
«Детский Форт Боярд» в Омске: в школу - по забору над лужей
«Детский Форт Боярд» в Омске: в школу — по забору над лужей  есть видео  4
18.04 / 08:39
Видеоролик «Детский Форт Боярд в Омске» разошелся по сети. Интернет-пользователей развеселили ребятишки, которые добираются до школы по забору, рискуя упасть в огромную лужу. Действительно ли в учебное заведение нельзя попасть другим способом — вопрос открытый. Возможно, дети просто так играют.

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

Реклама:




Архив

Интервью

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

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