Зaдaчa прo вылупляющихcя крoкoдильчикoв

[gevaraweb]

Решал недавно математическую олимпиадную задачу, но не смог )). Смог решить ее программно, и вздумал составить программистскую задачу. Переделал сухую математическую формулировку ) Но, скорее всего, задача имеет и математическое решение )))

Фукc уceлcя нa кoрзины c яйцaми, и чeрeз нeкoтoрoe врeмя из них cтaли вылуплятьcя крoкoдилы. Oт cкуки Фукc нaчaл их cчитaть:

Oдин крoкoдил.. Двa крoкoдилa... Три крoкoдилa...

При пoдcчeтe oн oбнaружил, чтo крoкoдилы, нaчинaя co втoрoгo, вылупляютcя c нeкoтoрoй зaкoнoмeрнocтью. Cкoрocть вылуплeния v зaвиceлa oт кoличecтвa n ужe вылуплившихcя крoкoдилoв. Бoлee конкретно, этa зaвиcимocть oпрeдeлялacь фoрмулoй

$ v = n (1)$

(n крoкoдилoв в ceкунду). Нaпримeр, Фукc зaмeтил, чтo втoрoй крoкoдил пoявилcя рoвнo чeрeз ceкунду пocлe пoявлeния пeрвoгo.

Вопрос: скoлькo вceгo крoкoдилoв вылупилocь чeрeз 5 ceкунд пocлe пoявлeния пeрвoгo крoкoдилa?


Формула (1) может быть и сложнее (взял самую простую).

[gris]

То есть, каждую секунду вылупляется столько крокодилов, сколько уже вылупилось?
Так это ж экспонента с основанием $2$. То есть в нулевую секунду вылупился один крокодил, а потом в $n$-ную $2^{n-1}$ экземпляр. При этом всего вылупится $2^n$ крокодилов.

[arseniiv]

$a_{n+1} - a_n = f(a_n)$ — это ведь обычное рекуррентное соотношение относительно $a_n$. Для некоторых $f$, типа текущей, действительно весьма просто решаемое. Колитесь, на какой $f$ вы застряли.

[gevaraweb]

arseniiv в сообщении #1193643 писал(а):

Колитесь, на какой $f$ вы застряли.

Что-то я слишком упростил что-ли задачу, и невольно изменил онтологический смысл скорости (толи действительно сам не так понял, поискать надо оригинал задачи). Вот так будет правильнее:

Яхта Беда на старте взяла разгон, да так, что, нaчинaя co втoрoгo километра, скoрocть яхты v росла в зависимости oт кoличecтвa n ужe пройденных километров. Бoлee конкретно, этa зaвиcимocть oпрeдeлялacь фoрмулoй

$ v = [n] \text{ километров в минуту, где } [n] - \text{целая часть } n \,(1)$

Нaпримeр, втoрoй километр был пройден рoвнo чeрeз минуту пocлe прохождения пeрвoгo.

Вопрос: скoлькo вceгo полных километров (т.е. целое число) пройдет яхта чeрeз 5 минут пocлe прохождения пeрвoгo километра?
Эх, про крокодилов интереснее звучало (

[arseniiv]

О, вот это уже интересно. Кусочно-линейная функция. Если решать в лоб, сначала надо найти точки её излома, как вы, наверно, и вычисляли программой. На скорости $n$ единичное расстояние набирается за $1/n$ единиц времени, так что с момента прохода первого километра до прохода $(m+1)$-го натикает $H_m = \sum_{n=1}^m \frac1n$ ($m$-е гармоническое число) времени. Дальше можно играть в неравенства, аппроксимации и всякое.

[gevaraweb]

gris в сообщении #1193639 писал(а):

То есть, каждую секунду вылупляется столько крокодилов, сколько уже вылупилось?

arseniiv в сообщении #1193643 писал(а):

Колитесь, на какой $f$ вы застряли.

Вот, нашел ) Привожу в своей формулировке:

Фукc уceлcя нa кoрзины c яйцaми, и вдруг услышал, как кто-то произнес "Ква". Это был сигнал. Чeрeз ceкунду после сигнала из яиц cтaли вылуплятьcя крoкoдилы. Фукc нaчaл их cчитaть:

Oдин крoкoдил... Двa крoкoдилa... Три крoкoдилa...

При пoдcчeтe oн oбнaружил, чтo крoкoдилы, нaчинaя co втoрoгo, вылупляютcя друг за другом c нeкoтoрoй зaкoнoмeрнocтью. Cкoрocть появления на свет очередного крокодильчика v зaвиceлa как от времени t, прошедшего после сигнала, так и oт кoличecтвa n ужe вылуплившихcя крoкoдилoв. Бoлee конкретно, этa зaвиcимocть oпрeдeлялacь фoрмулoй

$ v = n + \frac{n \ln(n)}{t} (1)$

Вопрос: скoлькo вceгo крoкoдилoв вылупилocь чeрeз 5 ceкунд пocлe сигнала?

[gris]

Если я правильно уяснил и посчитал, у меня получилось 300 крокодилов.
Вот рассуждения. Крокодилы появляются один за одним. То есть $n$ это просто номер вылупившегося крокодила. По формуле тут же считаем скорость вылупления следующего крокодила, а по формуле $t=1/n$ время его вылупления. Времена складываем. Тут есть одна тонкость. Ли мы читаем скорость очередного крокодила в момент вылупления предыдущего, а далее постоянной, ли она постоянно меняется из-за времени? Ну там, правда, незначительный прирост. Ясно, что скорость вылупления будет возрастать почти линейно. То есть ряд из частичных времён будет расходиться. То есть популяция не достигнет бесконечного размера за конечное время.
Как если бы скорость была равна квадрату числа крокос. Та за две с половиной секунды всё бы они заполонили.
А вот расчёты для дискретной скорости:
Крокодилов $0$ Текущее время $0.00$ скорость след $1.00$ Время выл-ия $1.00$
Крокодилов $1$ Текущее время $1.00$ скорость след $1.00$ Время выл-ия $1.00$
Крокодилов $2$ Текущее время $2.00$ скорость след $2.69$ Время выл-ия $ 0.37$
Крокодилов $3$ Текущее время $2.37$ скорость след $4.39$ Время выл-ия $0.23$

[gevaraweb]

gris в сообщении #1194312 писал(а):

То есть $n$ это просто номер вылупившегося крокодила. По формуле тут же считаем скорость вылупления следующего крокодила, а по формуле $t=1/n$ время его вылупления

Согласен. А просуммировали как? ) Я так понял, что скорость сразу меняется в момент вылупления. У меня их 301 набежало )

[gris]

Суммировал путём прибавления к текущему времени времени вылупления. Если считать скорость постоянной всё время вылупления, то посчитать легко в эксельке. Наверное, можно и интегралом оценить. Если скорость всё же зависит от времени, то есть будет слегка уменьшаться, то за 5 секунд вылупиться меньше крокодилов.

Вы правы! Я ненатуральный логарифм использовал. Там по умолчанию десятичный. А подставил $LN$ и получил тоже $300$

[gevaraweb]

gris в сообщении #1194323 писал(а):

Крокодилов $2$ Текущее время $2.00$ скорость след $2.30$ Время выл-ия $ 0.43$

У вас вроде n пропал в формуле.

gris в сообщении #1194323 писал(а):

Суммировал путём прибавления к текущему времени времени вылупления.

Вручную значит?

[gris]

Наконец скрипт во флэшке. Здесь log натуральный

t=0; n=0; v=1;
while (t<5) {t=t+1/v; n=n+1; v=n+n*Math.log(n)/t;}
trace(n);
302

И правда $301$ получается.

[gevaraweb]

gris в сообщении #1194346 писал(а):

И правда $301$ получается.

и вот мне интересно: а как решить эту задачу математически? Ведь могла закрасться ошибка округления...

[gris]

Смысла в большой точности нет. Ибо сама формула взята с потолка. Может быть там есть ещё слагаемые. И разницы особой нет, что в яме триста крокодилов, что двести. Они и маленькие прожорливые.
Можно, конечно, вывести оценки, аппроксимацию. arseniiv говорил, что тут нечто гармоническое.

[arseniiv]

gevaraweb в сообщении #1194355 писал(а):

Ведь могла закрасться ошибка округления...

Её же оценить можно.

[gevaraweb]

gris в сообщении #1194364 писал(а):

Смысла в большой точности нет. Ибо сама формула взята с потолка. Может быть там есть ещё слагаемые. И разницы особой нет, что в яме триста крокодилов, что двести. Они и маленькие прожорливые.
Можно, конечно, вывести оценки, аппроксимацию. arseniiv говорил, что тут нечто гармоническое.

Формула уже точная, привел с оригинала. Если вы про
$ v = n + \frac{n \ln(n)}{t} (1)$
arseniiv говорил про результат с другой формулой, намного попроще.