В городе Нестриженске есть n лохматых жителей и всего один парикмахер. Житель номер i готов стричься в том и только в том случае, если ему придётся заплатить не больше $v_i$ рублей (при этом, конечно, он предпочёл бы заплатить как можно меньше). Будем считать, что жители упорядочены по убыванию максимальной готовности платить: $v_1>v_2>...>v_n$.
Парикмахер стрижёт с рекордной скоростью и с нулевыми издержками. Ему, как и всем жителям, известен набор $v_i$, и он хотел бы с каждого жителя i собрать ровно $v_i$, тем самым получив максимально возможную прибыль. Однако он не в состоянии по внешнему виду жителя определить его номер и, соответственно, узнать его готовность платить. Конечно, можно поступить стандартным образом, назначив единую цену для всех клиентов. Однако парикмахер, в надежде получить больше, придумал следующую нестандартную схему продаж. Он объявляет n цен: $v_1,v_2,...,v_n$, и житель, придя в парикмахерскую, может подстричься по любой цене из этого списка на свой выбор, при условии что эта цена ещё не была выбрана другим жителем. Парикмахер делает это объявление по радио, после чего все жители бегут в парикмахерскую, чтобы успеть побыстрее.
В дальнейшем предполагается, что парикмахер не знает, в каком порядке жители прибегают к нему.
а) Предположим, что чем больше номер жителя, тем раньше он прибегает в парикмахерскую. Сколько человек подстригутся? Какую прибыль получит парикмахер?
б) Пусть теперь наоборот: чем больше номер жителя, тем позже он прибежит в парикмахерскую. Сколько человек подстригутся? Может ли при этом получиться так, что парикмахер соберёт больше прибыли, чем если бы он назначил единую цену? (Естественно, единая цена была бы выбрана так, чтобы максимизировать прибыль.)
в) Решив пункты а) и б), парикмахер ещё хорошенько поразмышлял и придумал другую нестандартную схему продаж, на этот раз гарантированно (вне зависимости от того, в каком порядке прибегают жители) позволяющую ему с каждого жителя i собрать $v_i$. Опишите эту схему и докажите, что она приведёт именно к такому результату.

Комментарии

а) самый жадный прибежит быстрее всех и выберет самую маленькую цену, а самый щедрый - последний , ему достанется самая большая цена , поэтому парикмахер получит максимальную прибыль
в) называет сначала самую большую цену, прибежит один, потом по убыванию, при этом будет каждый раз оставаться только один нестриженый человек, готовый платить данную сумму.
или заводит одного покупателя в парикмахерскую , запирает за ним дверь (чтобы другие ничего не услышали , не заподозрили дискриминации и не стали возмущаться) и начинает предлагать цены начиная с самой большой и заканчивая самой маленькой и стрижет за первую цену , за которую согласится стричься лохматый человек
Так лохматый человек, не будь дураком, подождёт до самой низкой цены.
А моя версия не противоречит ничему?
тогда уж , они по радио тоже будут ждать самой маленькой суммы
Строго говоря, нужно сформулировать схему продаж полностью, а ты как будто просто написал траекторию, которая реализуется. Сформулируй схему и докажи, что будет именно такая траектория (что жителям выгодно вести себя именно так, а не иначе)
После объявления набора состоящего только из самой высокой цены, найдется ровно один человек готовый заплатить столько, сколько объявлено, соответственно ждать снижения цены он не будет, это верно?
будет ждать , пока не наждется , и должен прийти наконец
Дим, это задача, такие рассуждения тут мне не нравится применять)это либо ясно изначально, либо это надо доказать, хотя для доказательства нужно бы было знать немного больше.
а почему бы не подождать? вдруг у парикмахера сдадут нервы, и он чуть снизит цену?
Тогда, не уверен, что существует "оптимальная" стратегия, которую ты хочешь услышать.
Могу предположить только одно, раз все такие настырные будут ждать, и при этом парикмахер несет нулевые издержки, он будет готов стричь хоть за сколько нибудь, ну а жители, "не будь дураками" пойдут к нему только когда будет озвучена минимальная цена. Прибегут к нему все стричься по-дешевке и дальше неизвестно как развернутся события.
Хотя если уж у нас такой "творческий" подход, то парикмахер может поступить так, озвучивает v_max и v_min, услышав о минимальной цене прибежит каждый, но каждому он будет говорить, что остался только второй вариант, а по условию человек должен выбрать из оставшихся, если он готов столько заплатить , поэтому сначала заплатят v_max, потом объявляет v_{max-1}и v_min и прокручивает снова аферу и т.д.
Используя принцип "не будь дураком" , первый житель не соглашается на максимальную цену , выходит из парикмахерской и узнает , кто же первый заплатил минимальную цену, всем рассказывает , все понимают , что это афера и ждут , пока у парикмахера сдадут нервы)))
ну как же. прибегают все и кричат: "Мой номер n, мой номер n!". И никаких максов не хотят, только мины.
в таком случае он начнет с самой маленькой цены, а когда лохмач скажет ему нет , он ответит : "Ну как хотите , можете идти" , лохмач подумает и скажет , ну ладно , тогда я согласен на столько-то (называет цену чуть больше), а парикмахер ему снова : "до свиданья" - и так до тех пор , пока лохмач действительно не встанет и не уйдет)) , парикмахер его окликнет и предложит последнюю цену
Бред какой-то
Можно еще так : пакрикмахер объявляет самую высокую цену и ждет , когда к нему кто-нибудь придет , люди подождут . подождут пару дней , и первый человек придет , затем он называет вторую повеличине цену и ждет и т.д...
При такой стратегии парикмахера, лохмач, не будь дураком, встанет и уйдёт после первой цены.
тогда пусть ходят лохматые!))
б) если четное число человек , то подстригутся n\2 , если нечетное , то (n\2)+0.5
б) Больше прибыли , чем при единой цене , он не соберет , т.к. при единой цене мог бы собрать бы р*n\2 или р*((n\2)+0.5) (или еще больше , в зависимости от того , какие $v_i$) где p - цена покупателя vn/2, а так он с первого собирает на Р-Vn меньше , со второго на P-V2 меньше и т. д.
25 минут , мой новый личный рекорд!
Решение пункта в) такое. Парикмахер объявляет, что цена за стрижку будет изменяться по последовательности $v_1,v_2,...,v_n$. Как только нашёлся желающий подстричься за $v_1$, цена падает до $v_2$. При этом он должен сделать так, чтобы все поверили, что он действительно никогда не подстрижёт за $v_{i+1}$, пока никто не подстригся за $v_i$. В этом случае жителю с готовностью платить $v_1$ будет выгодно согласиться на цену $v_1$.
Если жители доверяют парикмахеру, он может просто объявить эту схему. Если не доверяют, он может воспользоваться услугами Ребекки Коммитмент-Девайс.
По-моему фактор доверия-недоверия не обговорен в условии, и как теми средствами, что указаны в условии, заставить население не ждать, не понятно - он лишь объявляет сами цены в любой последовательности и любым набором. "Убедить их в серьезности своих намерений" - это для задачи звучит несерьезно. Ну честно, Гриш, как-то не очень красиво выходит)
Смотри, когда обычный монополист объявляет свою монопольную цену, мы тоже неявно предполагаем, что он как бы объявляет, что никому не продаст дешевле, и все в это верят. Ведь иначе можно было бы подойти к нему и сказать "моя готовность платить за первую единицу меньше, чем твоя монопольная цена, но больше, чем предельные издержки. Продай мне по цене ниже монопольной" - и это была бы взаимовыгодная сделка, при условии что остальные (те, кто покупал) по-прежнему будут покупать по монопольной цене; но проблема в том, что, завидев такое, они все прикинутся нищими и перестанут покупать по монопольной цене.

Так и в этой задаче, если предположить, что все верят парикмахеру, что он будет придерживаться своей схемы, то каждый купит по своей цене.

по-моему у меня то же самое , просто он не убеждал никого в своей настойчивости
А в пункте б) не получится, что человек, пришедший н-тым/2 будет последним, кто подстржётся, потому что (н/2)-1 самых богатых разгребут самые дешёвые цены, останется н-тый/2 человек и ещё н/2, у кого резервная цена (цена готовности подстричься) меньше, чем наименьшая цена из списка. Поэтому парикмахер получит достаточно маленькую прибыль.

Интересная задача!
Только у меня по пункту в) вопрос. Получается, что парикмахер называет всем одну и ту же цену (максимальную), до тех пор, пока кто - нибудь не откликнется на его молитвы. А если богатый пройдёт самым первым, и не будет знать, что другим гривачам парикмахер назвал ту же цену и в его парикмахерскую не вернётся? Тогда таким процессом парикмахер наоборот распугает всех посетителей.

Парикмахер объявляет всё всем сразу, и все знают, что в городе есть n жителей, и знают набор готовностей платить.
Хм, Гриш, лови более хитрую схему.
Парикмахер объявляет, набор цен. После этого все в закрытых конвертах приносят ему то, за сколько подстричь, при этом условия таковы: если по какой-то цене более одного предложения, то он не стрижет никого. Нетрудно заметить, что по сути это эквивалентно схеме закрытого аукциона, значит в равновесии каждый назовет свою цену, а доверие-недоверие, тут уже заменяются простой рациональностью.
а почему бы им не назвать не $v_i$, а $v_i-\varepsilon$? Ведь так тоже все цены будут разными, зато купят подешевле.
А с аукционами надо быть аккуратнее. В закрытом аукционе первой цены не является равновесием ситуация, когда каждый сообщает свою готовность платить.
нет, они называют из списка прейскуранта, просто если двое назовут $v_i$, то все останутся нестрижеными.

да, согласен, с аукционом натупил :)

А если графически смотреть, то получится, что парикмахер при абсолютной ценовой дискриминации заберёт себе весь треугольник под спросом?
Ну, на треугольник это похоже, только если смотреть сильно издалека. Тут скорее n прямоугольников рядом стоящих.
=)
То есть поэтому максимальная прибыль больше, чем при назначении единой цены? Мне просто кажется что графиком это видно лучше.
в пункте б прибыль меньше, чем при единой цене. в пункте а - больше, чем при единой цене