Задача

Темы

Сложность

10
Средняя: 10 (1 оценка)

Автор

07.02.2010, 03:31 (Григорий Хацевич)
08.03.2016, 13:55


(0)
Жили-были n зайцев. Узнали они как-то о существовании хорошего учебника по экономике и решили попросить знакомого деда Мазая, чтобы он купил учебник и прочитал его вслух (сами они читать не умеют, но слушают очень чутко, благо уши длинные). Учебник продаётся в лесном магазине за $C$ рублей. i-й заяц получает от учебника полезность, эквивалентную $u_i$ рублям. Известно, что любое $u_i>0$. Дед Мазай был бы рад купить учебник, пусть даже за свой счёт, но только в том случае, если это будет общественно эффективным, то есть $\sum\limits_{i=1}^n u_i>C$. Проблема в том, что $u_i$ – частная информация i-го зайца (все остальные зайцы и дед Мазай знают лишь то, что $u_i>0$). Если просто спросить "Чему равно твоё $u_i$?", то все назовут не настоящее своё $u_i$, а какое-нибудь несусветно большое число (обозначим то, что они называют, $v_i$) – чтобы сделать побольше вероятность того, что $\sum\limits_{i=1}^n v_i>C$, и учебник, таким образом, будет куплен; всё равно ведь платит дед. Если же, к примеру, объявить, что затраты на покупку учебника будут разделены пропорционально названным $v_i$, то у каждого зайца будет стимул занизить свою полезность, чтобы заплатить поменьше, так что в итоге сумма названных полезностей $\sum\limits_{i=1}^n v_i$ может оказаться меньше $C$ (и учебник, таким образом, не будет куплен), даже если сумма истинных полезностей $\sum\limits_{i=1}^n u_i$ больше $C$.

Дед Мазай придумал следующий механизм, который, как ему кажется, заставит каждого зайца сообщить свою истинную полезность. Каждый заяц называет $v_i$ (он может назвать любое число больше 0); учебник покупается, если $\sum\limits_{i=1}^n v_i>C$. Назовём i-го зайца решающим, если исключение его из рассмотрения приводит к тому, что меняется решение о покупке учебника. Так вот, каждый решающий заяц i платит деду $P_i=C-\sum\limits_{j\neq i} v_j$, где $\sum\limits_{j\neq i} v_j$ – сумма по всем зайцам (не только решающим), кроме i-го. Не решающие зайцы ничего не платят.

а) Всегда ли существует хоть один решающий заяц?
б) Могут ли все зайцы быть решающими?
в) Верно ли, что для любого решающего зайца $0\le P_i\le v_i$?
г) Прав ли дед в том, что любой заяц назовёт $v_i=u_i$?
д) Может ли быть так, что собранных денег не хватит, чтобы купить учебник?
е) Может ли быть так, что собранных денег будет больше, чем стоимость учебника?

Комментарии

А заяц будет платить если его U < P ?
Ну давай считать, что если уж заяц участвует в системе (назвал $v_i$), то он обязуется заплатить $P_i$, если окажется решающим.
в) неверно , т.к. если Pi=vi , то ...для всех зайцев ∑vi=C , а такого быть не может => Pi < vi

А зайцы могут друг с другом договориться ?

почему это "такого быть не может"? И вообще, чтобы доказать, что в) неверно, нужно доказать, что существует заяц, у которого $P_i<0$ или $P_i>v_i$. Разве не так?

Будем считать, что зайцы друг с другом не разговаривают.

Интересная задача...
Вероятно
в пункте а) ответ нет, например если $ \sum\limits_{i=1}^n v_i < C$ То при любом количестве рассматриваемых зайцев учебник не будет куплен, если конечно нет зайцев которые характеризуют учебник как антиблаго.
В пункте б) ответ да, например если $v$ каждого зайца равны $v' ~|~ v'>1$, $C=n\codt v'+1$, тогда каждый заяц может быть решающим.
а чем тебе мешают зайцы, которые "характеризуют учебник как антиблаго"? впрочем, их нет по условию.
б) я бы сказал, $C=nv'-1$
а)Если они вносят отрицательную полезность, то исключив их, мы увеличим их общую псевдополезность , такой заяц, например, может стать решающим.
б)Ну да, я это имел в виду)

Можно идти дальше?)

а) Ух ты, действительно.

Полный вперёд!

Значит антиблаг нет, пока решаю на этом основании.
В)
$ \sum\limits_{i=1}^n v_i = \sum\limits_{j\neq i} v_j + v_i $
Если есть решающий заяц, то, учитывая его, покупка совершается, то есть:
$\sum\limits_{j\neq i} v_j + v_i>C$

А без него покупка не совершается, то есть:
$\sum\limits_{j\neq i} v_j \le C$

Выражая из каждого неравенства $P_i = C - \sum\limits_{j\neq i} v_j$
Получим
$\begin{cases}P_i\ge 0 \\P_i

Нигде не ошибся, $ 0\le P_i< v_i $. Отсюда следует, что $ 0\le P_i\le v_i $.
Строгость/нестрогость зависит от того, куда отнести пограничный случай $ \sum\limits_{i=1}^n v_i=C $ (покупать ли учебник). Для определённости я отнёс его к "не покупать", но это не принципиально, поэтому в пункте в) я не стал мелочиться, и написал утверждение, которое было бы верно и при других вариантах.

А то, что антиблаг нет, повторюсь, написано в условии: "Будем считать, что любое $u_i>0$"

Ну отлично.)
Да, мне внимательности мне не занимать) - вот так я на округе вместо данного условия задачи про полезности, половину прочитал, половину, как оказалось, сам придумал)
Остальные пункты похоже "со звездочкой", а утро - как известно - вечера мудренее, а еще мудренее - вечер следующего дня)
Приятных сновидений!
...
Я имею в виду , что по условию ∑vi >C , чтобы учебник был куплен , а если сумма всех мнимых полезностей меньше или равна С , то и решающих зайцев не существует , так как учебник все равно не будет куплен
Но ты просуммировал только по решающим зайцам, а вдруг есть хоть один нерешающий заяц, и тогда всё ок? В любом случае, логика мне не понятна: даже если ты докажешь, что не может быть, чтобы у каждого решающего зайца было $P_i=v_i$, как из этого следует неверность утверждения в? Совет: когда пишешь выражение с индексом i, делай так, чтобы было понятно, имеется в виду утверждение "существует такое i, что ..." или же "для любого i верно, что ...", причём ещё должно быть понятно, какому множеству принадлежит обсуждаемое i: множеству решающих зайцев или множеству всех зайцев.
я всегда имел в виду всех зайцев , не только решающих, во всех индексах i

P.S. : если подскажете мне , где можно нормально писать формулы и выражения , то я мог бы объснять весь ход своих мыслей подробнее)) а так получается и долго писать решение , и непонятно

Если вдруг буду брать множество только решающих зайцев , обязательно скажу
В меню выбери "Добавить задачу" - "Как правильно?" - там написано, как писать формулы
спасибо
У меня то же , что и у Тимура в в) ..... если без этих антиблаг решать
г) вряд ли

если , к примеру есть такой заяц-полиглот , для которого ui > C , то он вполне мог бы занизить свою полезность до vi = C или может быть еще ниже , если исключить вероятность появления антизайцев

ОК, уточню вопрос пункта г. Верно ли, что никакая другая стратегия не может дать зайцу больше, чем стратегия $v_i=u_i$?
И еще одна мысль про антизайцев( т.е. зайцев с vi < 0) :
Если такой заяц окажется решающим , то ∑vi < (=) C => не принимается решение о покупке учебника => никакой заяц ничего не платит => Pi не может быть меньше нуля
Давайте с обычными зайцами разберемся, потом с остальными.
Ага, поддерживаю. Но вообще, решающий антизаяц "заплатит" отрицательную величину.
нет , я все таки думаю , что он ничего не заплатит .
Вроде , если учебник не покупают , то и деньги не собирают ни с кого , я прав?
Заяц максимизирует величину $u_i-P_i$ - из этого вероятно нужно исходить в пункте г) ?
ну да, если доопределить $P_i=0$ для нерешающих зайцев
Точнее, $u_i$ заяц получит лишь в том случае, если учебник будет куплен. Выбирая $v_i$, заяц думает, как его выбор повлияет на факт покупки учебника и на величину $P_i$, которую ему придётся заплатить.
Даю подсказку. Пусть некоторый заяц так и сделал: назвал $v_i=u_i$. В зависимости от того, что сказали другие зайцы, будет сформирован его выигрыш (полезность от учебника в случае его покупки за вычетом платы в случае, если придётся платить). Зафиксируем всё, что сказали остальные, и выясним, смог ли бы наш заяц хоть в каком-нибудь случае получить больший выигрыш, назови он какое-нибудь другое $v_i$.