Ученые научились делить пирог по-честному

Деление пирога – не такая простая проблема, как может показаться на первый взгляд. Дело вообще нешуточное: разве в ином случае принялись бы за его решение математики? А ведь они представили алгоритм честного деления этого мучного изделия между тремя людьми. При чем, всего за два надреза.

Вообще, эта задачка терзает ученых уже не один год. Ее сложность отчасти заключена в том, что у каждого из претендентов на лакомый кусочек свои критерии сравнения: кто-то хочет заполучить больше крема, кто-то наоборот его не любит и т.д. В 1980 году американский математик Уолтер Стромкуист уже доказал, что какие бы пожелания не выдвигали участники дележки, все их капризы можно удовлетворит за количество разрезов, что на единицу меньше количества претендентов. Но алгоритма ученый не представил. Теперь эта недоработка устранена.

Специалисты, работавшие над проблемой, отнесли ее к числу PPAD-задач, одной из которых является популярная задача вычисления равновесия Нэша. Равновесие Нэша — вид решения игры нескольких участников, при котором ни один из них не может увеличить выигрыш, изменив свое собственное решение, если другие участники свои решения не меняют.

Popularity: 6%

Читайте также

• Компьютер научили различать искусство (1)