Владелец охотничего домика сдает его на следующих условиях:
Каждый клиент может один раз в году, в произвольный день, может приехать в него на сутки. Если одновременно в домике оказывается несколько человек, то хозяин, в качестве компенсации за причиненные неудобства, не берет с них платы. Т.к. хозяин является невезучим (по Pushkin-у) человеком, то 29 февраля он отмечает свое день рождения и никого не принимает (о чем клиентам известно заранее). Со всех клиентов он берет одну и ту же плату.
Вопрос:
Если клиенты случайным образом выбирают день для приезда, то сколько клиентов должен набрать хозяин, чтобы максимизировать свой доход?
Здравствуйте, MichaelP, Вы писали:
MP>Вопрос: MP>Если клиенты случайным образом выбирают день для приезда, то сколько клиентов должен набрать хозяин, чтобы максимизировать свой доход?
следует,
что для больших M и N среднее количество одиночек равно M*exp(-M/N)
Эта функция имеет только один максимум при M=N и равный N/e=365*0.37=135
Таким образом хозяин может получить плату максимум за 135 дней.
Я не вижу второго решения ... если токо хохма какая
P>что для больших M и N среднее количество одиночек равно M*exp(-M/N) P>Эта функция имеет только один максимум при M=N и равный N/e=365*0.37=135 P>Таким образом хозяин может получить плату максимум за 135 дней. P>Я не вижу второго решения ... если токо хохма какая
Это не хохма. Просто из приведенного решения надо взять ТОЧНЫЕ формулы. Не так уж и сложно из них найти максимум. И станет очевидно, что он достигается в ДВУХ точках.
Подсказка: Во сколько раз увеличится(уменьшится) доход при увеличении числа клиентов на единицу?
Написал простенькую программку, гоняет каждого посетителя 100'000 раз Random'ом от 1 до 365,
получилось 183*(плата_за_проживание) максимум при 304 посетителях.
Здравствуйте, MichaelP, Вы писали:
MP>Вот задачку придумал (спасибо mihoshi).
MP>Владелец охотничего домика сдает его на следующих условиях: MP>Каждый клиент может один раз в году, в произвольный день, может приехать в него на сутки. Если одновременно в домике оказывается несколько человек, то хозяин, в качестве компенсации за причиненные неудобства, не берет с них платы. Т.к. хозяин является невезучим (по Pushkin-у) человеком, то 29 февраля он отмечает свое день рождения и никого не принимает (о чем клиентам известно заранее). Со всех клиентов он берет одну и ту же плату.
MP>Вопрос: MP>Если клиенты случайным образом выбирают день для приезда, то сколько клиентов должен набрать хозяин, чтобы максимизировать свой доход?
Симпатичная задачка...
Хм. Во-первых, можно взять "мою" формулу и найти ее максимум по кол-ву уникальных.
N=365
max(M((N-1)/N)^(M-1))
M((N-1)/N)^(M-1) = M(364/365)^M
Производная: 1 * (364/365)^M + M * (ln(364/365)(364/365)^M) = 0
Кстати, еще можно посчитать, сколько должно быть человек, чтобы добавление нового уменьшало матожидание уникадбных.
Т.е. вероятность, что новый чел займет неиспользуемый "слот" меньше, чем вероятность, что он займет один слот с уникальным. К сожалению, формулы при этом получаются очень нехорошие.
Здравствуйте, Orangey, Вы писали:
O> Написал простенькую программку, гоняет каждого посетителя 100'000 раз Random'ом от 1 до 365, O>получилось 183*(плата_за_проживание) максимум при 304 посетителях.
Ошибка в программе.
У меня получилось max при ~365 с платой ~135 — как у Pushkin'a
С помощью программки можно решить другую задачу:
Если в день 1 посетитель — то плату брать, если больше одного — то наоборот, выплачивать каждому за неудобства.
Так вот, получается, что при > 250 — хозяин становится в убытке.
Здравствуйте, mrhru, Вы писали:
M>С помощью программки можно решить другую задачу: M>Если в день 1 посетитель — то плату брать, если больше одного — то наоборот, выплачивать каждому за неудобства. M>Так вот, получается, что при > 250 — хозяин становится в убытке.
Число уникальных M*exp(-M/N)
Оставшееся число M*(1-exp)
Деньги, пришедшие к хозяину равны разности того и другого
Здравствуйте, Pushkin, Вы писали:
MP>>Подсказка: Во сколько раз увеличится(уменьшится) доход при увеличении числа клиентов на единицу?
P>Действительно Ещё 364. Точная максимальная средняя плата 134.46 дня
P>Но всё равно, мне кажется, что в таким образом поставленной задаче изящней сразу переходить к приближению N>>1.
На практике да. Но тогда выпадает факт существования двух решений.
Честно говоря, простота формулы изменения дохода при увеличении числа клиентов на 1 наводит меня на мысль, что существует более изящное решение.
Здравствуйте, MichaelP, Вы писали:
MP>Честно говоря, простота формулы изменения дохода при увеличении числа клиентов на 1 наводит меня на мысль, что существует более изящное решение.
MP>И я надеялся, что кто-нибудь его придумает...
Ты это имеешь в виду?
(M+1)/M * (N-1)/N = 1 при M=364
> 1 при M<364
< 1 при M>364
Здравствуйте, mihoshi, Вы писали:
M>Ладно, ответ — 364 или 365. M>Но как это найти без всех этих выкладок? M>Кстати, еще можно посчитать, сколько должно быть человек, чтобы добавление нового уменьшало матожидание уникадбных. M>К сожалению, формулы при этом получаются очень нехорошие.
Здравствуйте, MichaelP, Вы писали:
MP>Здравствуйте, Pushkin, Вы писали:
MP>Да. Мне казалось, что эту формулу можно получить непосредственно из какого-либо анализа добавления одного клиента.
Да, конечно, она сразу следует из формулы mihoshi M*(1-1/N)^(M-1)
Здравствуйте, Pushkin, Вы писали:
MP>>Да. Мне казалось, что эту формулу можно получить непосредственно из какого-либо анализа добавления одного клиента.
P>Да, конечно, она сразу следует из формулы mihoshi M*(1-1/N)^(M-1)
Из формулы следует. Но ИМХО было бы красивее получить эту формулу сразу, не определяя сначала матожидание дохода... Я поэтому в задачу и не вставил нахождение величины максимального дохода.
Здравствуйте, MichaelP, Вы писали:
MP>Из формулы следует. Но ИМХО было бы красивее получить эту формулу сразу, не определяя сначала матожидание дохода...
Не факт, что это выйдет проще.
Я например, не могу...
А вывод формулы mihoshi вполне прозрачен.
MP>Я поэтому в задачу и не вставил нахождение величины максимального дохода.
Красивое утверждение, независимое от "длины сезона" — хозяин может получить максимум за 37% дней
у тебя остаётся на втором плане.
Здравствуйте, Pushkin, Вы писали:
P>Красивое утверждение, независимое от "длины сезона" — P>хозяин может получить максимум за 37% дней P>у тебя остаётся на втором плане.
Кстати, можно еще один вопрос придумать: Сколько дней в году домик будет простаивать?
Правда, оно слегка разное для 364 и 365.
Хотя, как мне кажется, самое интересное это то, как из практической задачи определения числа слов с совпадающим идентификатором, если в качестве идентификатора использовать хэш от слова, через красивое решение mihoshi, получилась вполне симпатичная и новая задачка.
Если эту цепочку развернуть в обратную сторону, то это будет хорошим ответом тем, кто утверждает, что задачи в этом форуме не имеют никакого отношения к реальному программированию (Вот сколько пафосу напустил ).
Здравствуйте, MichaelP, Вы писали:
P>>Красивое утверждение, независимое от "длины сезона" — P>>хозяин может получить максимум за 37% дней P>>у тебя остаётся на втором плане.
Вот мой вариант задачи.
Некто решил открыть гостиницу "Приют зачарованных охотников".
Причём гостиница эта должна была брать $100 с человека только за те дни, когда он там жил один.
(Если человек жил один всего пол-дня, то должен платить только $50 и т д)
Если эту гостиницу поставить в глухом лесу, то никто туда не зайдёт и она прогорит.
А если на людном месте, то там будет всегда много постояльцев, и она тоже прогорит.
Каков будет средний доход гостиницы в день при наиболее удачном расположении?
Здравствуйте, Pushkin, Вы писали:
P>Вот мой вариант задачи. P>Некто решил открыть гостиницу "Приют зачарованных охотников". P>Причём гостиница эта должна была брать $100 с человека только за те дни, когда он там жил один. P>(Если человек жил один всего пол-дня, то должен платить только $50 и т д) P>Если эту гостиницу поставить в глухом лесу, то никто туда не зайдёт и она прогорит. P>А если на людном месте, то там будет всегда много постояльцев, и она тоже прогорит. P>Каков будет средний доход гостиницы в день при наиболее удачном расположении?
Самое удачное, это если он найдет одного постояльца и заберется с ним в самую глушь
