Деление пирога – не такая простая проблема, как может показаться на первый взгляд.
Дело вообще нешуточное: разве в ином случае принялись бы за его решение математики? A вeдь oни прeдстaвили aлгoритм чeстнoгo деления этого мучного изделия между тремя людьми.
Причем, всего за два надреза. Вообще, эта задачка терзает ученых уже никак не один год. Ее сложность отчасти заключена в том, что у каждого из претендентов на лакомый кусочек свои критерии сравнения: кто-то хочет развести больше крема, кто-то наоборот его не любит и т.д.
В 1980 году заокеанский математик Уолтер Стромкуист уже доказал, что какие бы пожелания не выдвигали участники дележки, все их капризы можно удовлетворить за количество разрезов, что на единицу меньше количества претендентов. Только алгоритма ученый не представил. Теперь эта недоработка устранена.
Специалисты, работавшие над проблемой, отнесли ее к числу PPAD-задач, одной из которых является популярная задача вычисления равновесия Нэша. Равновесие Нэша — вид решения игры нескольких участников, при котором ни один из них не может увеличить выигрыш, изменив свое собственное решение, если другие участники свои решения не меняют.
