Задача

Раздел

Темы

Сложность

0
Голосов еще нет

Автор

10.12.2012, 18:48 (Дмитрий Сироткин)
26.05.2015, 17:25


(0)
Три дона Вито Корлеоне, Филипп Татталья и Эмилио Бардзини распределяют между собой, кто что будет крышевать. Под их совместным контролем есть есть 3 доходных бизнеса - профсоюзный, размером в 1 млрд долларов, алкогольный, размером в 2 млрд долларов и игорный, размером в 3 млрд долларов. Каждый из донов имеет различные знакомства в органах власти, и поэтому они по-разному оценивают ценность каждого доллара в разных бизнесах (поскольку учитывают риск). Из-за этого, Вито, с учётом риска, оценивает каждый доллар стоимости профсоюзного бизнеса в два раза дороже номинала, а каждый доллар стоимости алкогольного бизнеса в два раза дешевле номинала. Татталья же наоборот - оценивает каждый доллар стоимости профсоюзного бизнеса в два раза дешевле номинала, а каждый каждый доллар стоимости алкогольного бизнеса в два раза дороже номинала. Бардзини оценивает каждый доллар в любом из бизнесов по номиналу. Доны распределяют бизнесы между собой так - Корлеоне делит бизнесы на 3 части , Татталья первый выбирает себе часть , а Бардзини - выбирает из двух оставшихся. Если дону безразлично, что выбрать, то за него выбирает Вито. В конце Корлеоне забирает остаток. Бизнесы он может делить в любом отношении.

a) Помогите Корлеоне так поделить бюджет, чтобы получить максимальную полезность.

б) К Бардзини приехал друг дон Вёрджил «Турок» Соллоццо и требует включить себя в делёж. Его предпочтения - такие же, как у Бардзини. Он выбирает долю после Бардзини, но до Корлеоне. Как теперь должен Вито разделить бизнесы?

в) Пусть у нас есть есть n выбирающих донов и один делящий Вито Корлеоне (Вито выбирает последним). У каждого из донов есть своя оценка полезности каждого доллара в каждом из бизнесов (в пределах одного бизнеса, полезность каждого доллара всегда одинакова). Корлеоне составляет список донов в порядке убывания полученной полезности. Существует ли такой набор бизнесов и их стоимостей, чтобы Корлеоне всегда смог разделить его так, чтобы доны встали в этом списке в любом угодном ему порядке:

в1) При n=1?
в2) При n=2?
в3) При n=3?
в4) При любом n?

Комментарии

Условие задачи было отредактировано. Приношу свои извинения всем, кто её решал до этого в неотредактированном варианте. Смысл задачи не изменился.
Да, есть. Она уже исправлена.
К предыдущей задаче был прислан комментарий с решением. Приношу извинения автору решения за то, что оно стёрлось вместе с предыдущей редакцией задачи. Не могли бы Вы его прислать, оно, кажется было почти правильное.
Пришлю либо поздно, либо завтра. Только с театра пришел и надо уроки делать.
А что там нужно поправить?
Я смог сделать дону Корлеоне большую полезность, чем получилось у тебя. Увы, само твоё решение я не смогу просмотреть(, так что не смогу оценить есть ли у тебя ошибка, а если есть, то где.
Да, это безусловно правильное решение. Но в вычислениях должна быть ошибка.

Посмотри, что будет при таком делении:

1 кусок - 1P+1.3G
2 кусок - 1.2A
3 кусок - 1.6G+0.8A

Моя тоже)
Не всегда. У меня в загашнике уже полгода пылится моя же задача на индекс Джини. Так и не решил)
Не буду спорить
Опять я не так объяснил.(
Ну в смысле на самой олимпиаде не так прочитать и решать при своих, не так прочитанных, условиях.
Хотя да, неправильное прочтение не всегда упрощает задачу.
О, теперь понятно