Сотовый монополист «Фибоначчи-телеком» решил порадовать всех своих абонентов новой обязательной услугой – тамагочи. В ближайшую полночь после подключения этой услуги в вашем мобильном телефоне поселяется пара кроликов, которым на тот момент уже исполнился один день от роду (точнее говоря – здесь и далее, – одни сутки). Всего же мобильные кролики живут два дня, и в каждый из этих дней каждая пара кроликов производит на свет новую пару.

Штука эта забавная, но не бесплатная: в момент поселения первой пары с вашего счёта снимается 1000 рублей (плата за подключение услуги), а также, начиная с этого момента, каждую полночь снимается столько рублей, сколько пар кроликов находятся в вашем телефоне.
Как выясняется, кролики плодятся довольно быстро, и, чтобы вконец не разорить своих абонентов, «Фибоначчи-телеком» предлагает при подключении выбрать любой из бесконечного множества тарифов, отличающихся параметром k, а именно: каждые k дней услуга подключается заново, т.е. все расплодившиеся кролики покидают ваш телефон, вместо них поселяется пара кроликов в возрасте одного дня, ну и, конечно же, с вашего счёта снимается 1000 рублей.
Определите, какой тариф из множества {1,2,3,…} вам следует выбрать, если вы собираетесь пользоваться этим тарифом всю жизнь, а потом телефон будет передаваться по наследству, и еще вы верите в то, что ставка по депозитам до скончания веков будет равна 0,1% в день.

Комментарии

А ставка по депозитам имеет какое-то значение?
Она нужна для сопоставления платежей во времени: заплатить 1 рубль завтра для вас все равно что заплатить 1/(1+0,001) рублей сегодня.
Вроде бы безразлично, выбрать первый или второй тариф.
при первом тарифе вам придётся платить 1000 каждый день, а при втором - каждые два дня.
Хо-хо, я даже понял откуда были взяты кролики, вики - хорошая штука.=)
Наиболее приемлемым будет вариант с наименьшей стоимостью? (то есть самый дешёвый тариф?) Я просто хотел уточнить, что именно нужно искать
Наилучший тариф - с наименьшей суммой всех дисконтированных платежей.
Например, вам предлагают заплатить за что-то либо 1000 рублей сегодня, либо 1100 через год. Предположим, что банковская ставка - 20% в год. Второй способ лучше, потому что 1000 рублей сегодня вы можете положить в банк, и через год забрать 1200, отдать 1100 и 100 рублей у вас еще останется.
В общем случае вы выбираете второй вариант, если
1000*(1+r)>1100, или, по-другому,
1000>1100/(1+r)
Если дневная ставка равна 0,1%, то за год набежит (1+0,1%)^365 -1 = 1,001^365 - 1 = 0,44 = 44%
что лучшим тарифом будет тот, при котором ежедневные затраты будут минимальны
а что такое ежедневные затраты? вы каждый день тратите разную сумму, потому что количество пар кроликов изменяется
Еще вопрос, деньги на телефоне (наш баланс), они были положены в самый первый день (то есть сумма изначальная на счету, только её и расходуем,и предполагая что её хватит на всё), или их докладываем?
Так как на деньги на телефонном счету проценты не начисляются, то выгодно докладывать перед каждой полночью ровно столько, сколько в эту полночь снимется. То есть лишнего на счёте не держим, но и в минус уходить запрещено.
1)Не могу разобраться в численности кроликов :)
Т.е. в первый день - 1 пара, на второй день 1 пара, на третий день - 2 пары, на четвертый - 3 пары, на пятый - 4. Так чтоли?

2)Правильно ли я понял, что платеж n-ого дня нужно делить на (1+0,001)^n?

1) на пятый - пять, остальное верно
2) учтите, что все платежи происходят в начале дня, поэтому, если вы делите первый платеж на 1,001, то вы приводите его к моменту на день раньше, чем он. Если же вы хотите привести все платежи к моменту первого платежа, то нужно делить на 1,001^(n-1)
1 день: 1000р
2 день: 1/(1+0,001)
3 день: 2/(1+0,001)^2
4 день: 3/(1+0,001)^3
Пока не пойму закономерность, с которой увеличивается количество пар.
Численность кроликов увеличивается по последовательности Фибоначчи,$A_n=A_{n-1}+A_{n-2}$, А - численность кроликов на n-ый день, $A_n_1=1,A_n_2=2,A_n_3=3, A_n_4=5$, итд.
На 5ый день - 8 кроликов, на 6й - 13, на 7й - 21,
далее идут числа 34,55,89 итд)
Неправильно: во второй день одна пара, как и в первый: первая пара родила новую пару, а сама умерла.
http://ru.wikipedia.org/wiki/Последовательность_Фибоначчи
Хех, так у нас же тогда сумма платежей - сумма геометрической прогрессии с множителем 1,618/1,001
такая сумма, как вы понимаете, бесконечна. Она соответствует тарифу "$k=\infty$" - когда мы никогда не инициализируем кроликов. Такого, впрочем, в списке тарифов нет.
Почему же бесконечна? Да, это не бесконечно убывающая прогрессия, но ведь нам и надо найти такое количество дней, через которое уже уплаченная сумма превысит 1000. Тогда мы и инициализируем наших кроликов!
Навскидку k где-то 14-15.
Ок, теперь я вас понял.
Что касается момента инициализации, то будьте аккуратны. Вы должны будете доказать, что выгодно инициализировать именно в выбранный вами день, а не, скажем, днём ранее, когда вы платите 1000 чуть пораньше, но зато кормёжка кроликов в тот день обходится значительно дешевле.
хм, а я считал по "midnight"ам)
в первую полночь - 1 пара, во вторую - 2, в третью - 3, в четвертую - 5, в 5ую - 8, и т.д.
Нет, вторая пара рождается сразу после второго midnight'а :)
1,618 - случайно не число $\varphi=\frac{{\sqrt5+1}}{2}$, или мне опять кажется?
Тсс!, не говорите Лёше: мы нарушили его монополию.
Ужас, похоже все-таки золотая середина подбирается к экономике;)
Золотое сечение. Золотая середина - немножко другое.
Сути это не меняет, это ведь та же последовательность, сдвинутая на 1 "n" влево=)
Не та же. Почитай про числа Фибоначчи: первый множитель - 1, второй - 2, последующие начинают "стягиваться" к 1,618. Если мы будем считать со второго члена последовательности - среднее геометрическое не будет равно 1,618.
Свойства последовательности Фибоначчи не зависят от того, с какого члена начинать; но в нашей задаче все-таки должна быть только одна правильная последовательность; мне кажется, вот такая: 1,1,2,3,... - количество пар кроликов в начале первых, вторых и т.д. суток. Если кто-то считает по-другому - пишите!
(1,618/1,001)^k < 1000/(1,001)^(k+1)
сократим на (1,001)^k
получаем
(1,618)^k < 1000/1,001
прологарифмируем, воспользуемся свойством логарифмов:
k < log(1,618)999
k < 14,3535
т.е. 14 день - последний, когда суммарные затраты на кормежку кроликов за все предыдущие дни не превышают 1000.
Ответ: k=15
Почему оптимальным является именно "последний день, когда суммарные затраты на кормежку кроликов за все предыдущие дни не превышают 1000." И как вы эти затраты посчитали?
Ой, это я опять по ошибке посчитал лишь последний день. Просто сплю уже на ходу.

А оптимальным является не k, а (k+1) день, т.к. если дальше продолжить выращивание кроликов - затраты превысят 1000, и благоразумнее будет заплатить 1000 и начать все по новой.

А все-таки оно и правильно - считать только последний день. Зачем нам сумма? :) Пуская мы и стремимся к минимуму суммы платежей - она все равно будет достигнута, если мы не дадим дневному платежу достигнуть дисконтированной 1000.
Возможно к=13
Я рассуждал так, что мы позволим плодиться кроликам до тех пор, пока дисконтированная стоимость всех "съемов" со счета - это как бы аналог стоимости "позьзования кроликами" , пока эта стоимость не превысит диск. стоимость подключения новой услуги, то есть 1000+1. Почему именно так? Потому что далее нет смысла их эксплуатировать-выгоднее купить новых. Произойдет это в 13ю полночь. В неё же выгодно и обнулить сразу всех. Если это подразумевает то,что 13-я полночь-это чрез 13дней то к=13. Если подразумевается что после неё наступит 14й день, то к=14 (13или 14 смотря как смотреть)

Я исходил из того,что:
1. В тот день,когда кроику исполняется 2дня, он погибает немного раньше полночи, и деньги за него не успевают снять :) (то есть если в данном дне у вас 1кролик с возрастом 2дня, то в полночь этого дня за него не снимут деньги т.к к моменту "съема" он умерт :(

Кстати в моем решении надо заменить степень k на k-1:
(1,618^(k-1))/1,001^k < 1000/(1,001)^(k+1)
Теперь у меня получился k < 15,35, т.е. искомое число - 16.
а если так:
Г.п.:1,1,2,3,5,8,13,21 и т.д
первый член не = 0, т.к.сказано, что кролики погибают только спустя 2 дня и тогда с математической точки зрения имееют смысл вычисления
у этой г.п.q=1,618(той самой золотой пропорции, о которой говорил макс), тогда
по формуле суммы г.п. мы получим, что
q в степени n>619
1.618в степени n>619
тогда n - будет количество дней, через сколько надо будет обновить кроликов.
вот единственное надо будет учесть то, какую прибыль получает держатель кроликов по депозитам и добавить еще это условие в нер-во, т.е. прибавить его к левой части.
ничего не понимаю в численности.
в первый день 1 пара произведёт ещё пару и того их 2
потом во 2 день - выживет одна пара + 1 пара потомства
3ий= 2 пары + 2 пары потомства.
4ый 3 пары (одна старая отбросит копыта. простите, лапки) +3 пары потомства.
и далее (сумма двух предыдущих)
т.е.
1д=2
2д=2
3д=4
4д=6
5=...
ах нет. простите, не так. если смотреть на полночь, то действительно сначала будет одна пара затем одна и потом две на третью полночь.
Может нас уже рассудят? :)
Короче, большинством голосов утверждаем последовательность 1,1,2,3,5,... - и так до обновления кроликов (это без учёта стоимости подключения услуги), а потом сначала.
Теперь с учётом стоимости обновления:
Если k=1, то: 1001,1001,1001,...
k=2: 1001,1,1001,1,...
k=3: 1001,1,2,1001,1,2,...
и так далее.
Из всех возможных k нужно выбрать такое, чтобы дисконтированная стоимость соответствующей этому k последовательности платежей была наименьшей. Предъявив "оптимальное" k, не забудьте так или иначе доказать, что ни при каком другом k дисконтированная стоимость соответствующей последовательности платежей не будет меньше вашей.
Кто не понимает, почему нужно придерживаться именно этой схемы - пишите, что именно вам не понятно.
На этой неделе у меня напряжённая учёба, поэтому заранее прошу прощения, если буду отвечать с задержкой.
Общайтесь друг с другом:)
Гриша
по-моему k=20.

нужно решить чтото вроде

http://impj.narod.ru/t5001.jpg

А можете пояснить решение?
Пусть k - порядковый номер дня, в который затраты на кормежку кроликов не превышают стоимости их обновления. Численность кроликов возрастает согласно последовательности Фибоначчи, для которой выполняется закон N=(N-1)*1,618. Тогда затраты на кормежку возрастают согласно геометрической прогрессии с множителем 1,618, и затраты в день "k" будут равны 1*1,618^(k-1). Не забываем продисконтировать - делим на (1,001)^k.
Стоимость обновления в день "k" с учетом изменения стоимости "платежа завтра" составит 1000/(1,001)^(k).

(1,618^(k–1))/(1,001)^k < 1000/(1,001)^k
сокращаем знаменатели
1,618^k < 1618
k < log(1,618)1618
k < 15,35
Следовательно последний день, когда затраты на кормежку кроликов не превышают стоимости их обновления - 15. А на следующий день выгоднее будет обновить тариф.
Ответ: 16.

Выслушаю вашу критику.

1) Последовательность 1,1,2,3,5,... не является геометрической прогрессией.
1,618 (приближённо) - это лишь предел $x_{n+1}\over{x_n}$ при $n\to +\infty$. Отсюда не следует, что для любого n ${x_{n+1}\over {x_n}}=1,618$.
Если честно посчитать 16-й член последовательности, то получится 987<1000.

2) В чём смысл дисконтировать платежи, совершаемые в один и тот же момент? Понятно, что коэффициенты дисконтирования сократятся, и поэтому не важно, сравнивать дисконтированные или не дисконтированные платежи.
Дисконировать нужно тогда, когда платежи в одном потоке относятся к разным моментам времени.

3) Если вы нашли период, начиная с которого затраты на кормёжку кроликов превышают 1001, то в этом периоде выгоднее обновить кроликов, чем не обновить (для доказательства этого сравните последовательности платежей, начиная с этого момента, в двух этих случаях). Но отсюда не следует, что этот период - оптимальный для обновления кроликов, потому что вполне возможно, что еще лучше было обновить их, скажем, днём раньше: тогда бы вам не пришлось платить довольно большой, хоть и не превышающий 1001, платёж в этот предыдущий день. Но у обновления днём раньше есть минус: вам придётся заплатить 1000 на день раньше. Выбрать оптимальный день обновления помогает дисконтирование.

Все теперь окончательно убедился, что находить нужно сумму дисконтированных платежей. А задать её математически у меня не выходит.
Через золотое сечение можно выразить k-тый член последовательности Фибоначчи, но проблема в том, что каждый платеж надо дисконтировать :)
На олимпиаде я пообещал, что выложу решение на сайте, но мне всё-таки хочется, чтобы вы сначала решили задачу сами. Тем более что на самом деле в ней нет ничего суперсложного. Кто плохо знаком с дисконтированием - прочитайте мои комментарии к этой задаче, в них вроде есть всё необходимое.
Подсказка: последовательность Фибоначчи тут только для красоты, при решении из всех её свойств используется только возрастание членов.
Выбирать k> 16 невыгодно, т.к. тогда сумма очередного взноса будет > 1001 - и дешевле будет просто начать заново с 1001.
У нас остается конечное число состояний и легко проверить, что оптимум достигается при k=11 PV(первый день)~ 112495.
Всё верно, поздравляю!
Задача получилась вычислительная. Если хотите поупражняться в аналитических выкладках, вот вам дополнительное задание.
Представьте, что вместо последовательности Фибоначчи дана последовательность, которая приближается к 1000 довольно медленно. Например, арифметическая прогрессия 1,10,11,21,…; оптимальное k в этом случае равно 14. А теперь представьте, что под рукой у вас только калькулятор, а компьютера нет.
Если 14 раз посчитать NPV на калькуляторе еще можно, то на сотню таких расчётов (пока доберётесь до 1001) терпения явно не хватит. Нужно доказать, что k=14 оптимально, не перебирая все варианты, при которых ежедневные затраты на кроликов не превышают 1001.
Арифметическая прогрессия лишь пример; может быть дана любая возрастающая последовательность. Например, такая: с 1-го по 19-й члены задаются формулой $x_k=1+10(k-1)$, с 20-го по 100-й члены просто даны (что-нибудь типа 200, 203, 204, 208, ..., 1000), а начиная со 101-го опять $x_k=1+10(k-1)$. Докажите, что k=14 оптимально.
Насколько я представляю эту задачу, нужно доказать, что после того, как увеличение k на единицу в первый раз не привело к снижению PV, остальные увеличения будут и дальше увеличивать PV. А там надо еще подумать.