x, y, z

Задача о деливших добычу завистливых разбойниках

Сергей Дориченко

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

Общая постановка задачи. $N$ жадных (завистливых) разбойников делят добычу. Мы считаем, что каждое подмножество сокровищ каждый разбойник оценивает по своему разумению. Оценка всегда неотрицательна, и если часть сокровищ разбита на две непересекающиеся части $A=A_1 \cup A_2$, $A_1 \cap A_2 = \varnothing$, то оценка части $A$ равна сумме оценок частей $A_1$ и $A_2$. Добыча считается безгранично делимой, т. е. каждый набор сокровищ может быть разделен на любое число частей, равных с точки зрения данного разбойника. Как разделить добычу?

Например, если разбойников два, то один делит на две равные, по его мнению, части, а другой выбирает.

Сергей Александрович Дориченко, главный редактор журнала «Квантик» и зав.отделом математики журнала «Квант», учитель математики.
Комментарии: 0