Задача
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) от всей добычи.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь