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) от всей добычи.
			
Индукция (прочее) Теория алгоритмов (прочее)