Условие
n разбойников делят добычу. У каждого из них свое мнение о
ценности той или иной доли добычи, и
каждый из них хочет получить не меньше,
чем 1/n долю добычи (со своей точки зрения).
Придумайте, как разделить добычу между разбойниками.
Подсказка
Воспользуйтесь индукцией по числу разбойников.
Решение
Для двух разбойников задача решается несложно - один делит добычу на
две равные по его мнению доли, а другой выбирает из них наибольшую
на его взгляд долю.
Будем решать задачу при помощи
индукции по числу разбойников,
т.е. предположим,
что k разбойников уже имеют способ разделить добычу безобидно.
Будем делить добычу между k+1 разбойниками.
Разделим всю добычу между k разбойниками и затем пусть каждый из них
разделит свою долю на k+1 равных по его мнению частей.
Пусть теперь последний разбойник выберет по одной из этих частей
у каждого из k разбойников.
Последний разбойник взял (по его мнению) не менее, чем по 1/(k+1)
доле у каждого из k разбойников, т.е. всего он получил не менее
1/(k+1) от всей добычи.
Каждый из первых k разбойников также получил не менее, чем
(1/k)*(k/(k+1))=1/(k+1) от всей добычи.
Источники и прецеденты использования
