Об упорных червяках и математике

← →
McSimm © (2009-11-04 01:04) [0]

Есть такая задачка, уже не помню откуда взял.
На идеальной растяжимой ленте длиной один километр на одном ее конце находится идеальный упорный червяк и ползет к другому ее концу с скоростью один миллиметр в секунду. При этом ленту растягивают со скоростью один километр в секунду (каждую секунду лента становится на один км. длиннее). В задаче спрашивалось доползет ли червяк до другого конца ленты.

С вопросом взлетит / не взлетит я разобрался сразу, это несложно.
Но мне стало интересно за какое именно время доползет и я тут столкнулся с недостаточным знанием математики - нормального аналитического решения я не нашел.
Немного пошаманив, я получил решение - 10 в степени 45000, но не совсем математическим путем - я потом расскажу как я решал, но не хочется сразу давать направление, возможно не лучшее.
Можете предложить свой вариант и проверить мой ответ ?

← →
DVM © (2009-11-04 01:09) [1]

Это задача из теории рядов. Ряд расходящийся червяк не доползет.

← →
antonn © (2009-11-04 01:09) [2]

боюсь что оффтопик, но это уже было, могу даже в клиенте покопаться :(
некоторые будут читерить :)

← →
@!!ex © (2009-11-04 01:12) [3]

> [1] DVM © (04.11.09 01:09)

Это почему?
Задачку невнимательно прочитал. Читай внимательнее. лента то становится длиннее, но каждый раз все больше растягивается позади червяка.

← →
DVM © (2009-11-04 01:14) [4]

Давным давно, еще в школе я читал рассказ в каком то сборнике советской фантастики там как раз экспериментальным путем проверяли подобную вещь. Допрыгает или нет лягушка до конца пути если с каждым прыжком путь будет увеличиваться в 2 раза.

Собственно лягушка движется вперед - значит допрыгает, говорили одни
Но с каждым прыжком путь ее удлиняется говорили другие.

Лягушка могла собственно допрыгать если путь был около полутора первоначальных ее прыжков.

← →
DVM © (2009-11-04 01:15) [5]

> @!!ex © (04.11.09 01:12) [3]

да нет все я вроде верно прочитал

← →
antonn © (2009-11-04 01:18) [6]

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

← →
McSimm © (2009-11-04 01:19) [7]

доползет, но не о том вопрос, а о том, как посчитать за сколько ? Я не встречал таких расчетов.
лягушка тут не совсем аналогия, т.к. лента увеличивается всего на км/сек.

← →
DVM © (2009-11-04 01:20) [8]

как он может доползти если длина ленты увеличивается быстрее чем он ползет?

← →
DVM © (2009-11-04 01:23) [9]

> т.к. лента увеличивается всего на км/сек.

цель отдаляется на 1км-1мм в секунду. Как цель может быть достигнута при таких условиях?

← →
antonn © (2009-11-04 01:24) [10]

> DVM © (04.11.09 01:20) [8]
>
> как он может доползти если длина ленты увеличивается быстрее
> чем он ползет?

увеличивается вся лента, а червяку важна только оставшаяся часть, по началу да, будет далеко, но настанет момент когда общее увеличение всей ленты будет меньше одного миллиметра за шаг на оставшийся путь, и вот тут червяк воспрянет и победит :)

← →
DVM © (2009-11-04 01:27) [11]

> увеличивается вся лента, а червяку важна только оставшаяся
> часть,

аа, понял. А математическое решение несложно наваять имхо.

← →
antonn © (2009-11-04 01:29) [12]

Хм, в клиенте не нашел задачки, но точно помню - она тут была.
Давайте позовем Бориса :)

← →
McSimm © (2009-11-04 01:33) [13]

> точно помню - она тут была

с численным расчетом или взлетит / не взлетит ?

← →
Игорь Шевченко © (2009-11-04 01:34) [14]

Вообще-то это Гарднер

← →
antonn © (2009-11-04 01:36) [15]

Чего не помню - того не помню. Возможно это даже было в темах "задач про Васю Пупкина" от MBo. И вроде были сравнения с каплей росы на удлиняющейся тонкой резинке, что то такое...
Просто в то время я задачи нигде не смотрел кроме как тут, вот и засело :)

← →
McSimm © (2009-11-04 01:36) [16]

да, вероятнее всего от него. не помню.

← →
Игорь Шевченко © (2009-11-04 01:37) [17]

"Независимо от параметров задачи (начальной длины ленты, скорости червяка, длины отрезка, на который увеличивается с каждой секундой длина ленты) червяк всегда доползает до конца за конечное (хотя и очень большое) время"

← →
McSimm © (2009-11-04 01:39) [18]

10 в степени 45000 вполне подходит под "хотя и очень большое" :)
мне это число понравилось еще и тем, что не обязательно указывать единицы измерения - просто не важно секунды, часы или годы :)

← →
Styx (2009-11-04 01:43) [19]

http://golovolomka.hobby.ru/books/gardner/gotcha/ch6/06.html

← →
DVM © (2009-11-04 01:44) [20]

вот мат выкладки (не мои, я ряды напрочь забыл). Только здесь принято что червяк ползет 1 см в сек а не мм, но сути это не меняет.

Длина жгута в конце k-й секунды: L=k+1 км. Пройденное расстояние червяком в конце k-й секунды: ((((2+1)*3/2+1)*4/3+1)+5/4+...+1)*(k+1)/k сантиметров. Можно проверить для любого момента времени. Выражение пройденного червем расстояния можно преобразовать в: (k+1)(1+1/2+1/3+1/4...1/k). Сумма первых четырех членов гармонического ряда равна ln(k)+Ce. Где Ce - постоянная, равная примерно 0,577. Составляем уравнение:
(k+1)*(ln(k)+Ce)=10^4(k+1)
10^4 - приведение километров к сантиметрам. Сокращаем на k - получаем результат:
k = e^(10^4-Ce) секунд. Длина жгута получается на единицу больше.

В конце каждой секунды жгут растягивается на 1 км. Значит в зависимости от времени относительное удлиннение жгута составляет (k+1)/k (в конце первой секунды - в два раза, в конце второй - в 3/2 раза, в конце третьей в 4/3 раза). В то же время относительное перемещение червяка по жгуту еще и зависит от положения самого червяка на жгуте.Чем ближе он к краю - тем на большее расстояние переносится следующим растяжением жгута. То-есть попробуем составить таблицу по времени перемещения червяка:
1с - 1 см + 1см (дополнительное перемещение за счет жгута)
2с - (2см (предыдущие)+1см )*3/2 (коэффициент за счет удлиннения жгута)
3с - (3*3/2см (предыдущие)+1см )*4/3 (опять же коэффициент за счет удлиннения)
И т.д. Так и получаем сумму...

← →
Суслик_ (2009-11-04 01:47) [21]

я тоже дошел до этого, но там факториалы жуткие, по идее доползти должен

← →
Германн © (2009-11-04 01:52) [22]

> antonn © (04.11.09 01:29) [12]
>
> Хм, в клиенте не нашел задачки, но точно помню - она тут
> была.
> Давайте позовем Бориса :)

Ну да. В пол-второго ночи по Москве звать Бориса - это самое то! :)

← →
cwl © (2009-11-04 01:53) [23]

получился диффур .. осталось решить %>

← →
McSimm © (2009-11-04 01:57) [24]

у меня интегральное уравнение было, а не дифур - не решил.

решил через гармонический ряд, только не аналитически, а последовательным приближением, с использованием выч.средств.

> Styx (04.11.09 01:43) [19]

я там так и не понял как они свои оценки получили 2^200000 и e^100000

← →
Суслик_ (2009-11-04 01:59) [25]

> <Цитата>
>
> McSimm © (04.11.09 01:57) [24]
>
> у меня интегральное уравнение было, а не дифур - не решил.
>
>
> решил через гармонический ряд, только не аналитически, а
> последовательным приближением, с использованием выч.средств.
>

бинго коллега, сижу вот, читаю - как это аналитически решить ? http://ru.wikipedia.org/wiki/%D0%93%D0%B0%D1%80%D0%BC%D0%BE%D0%BD%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D1%80%D1%8F%D0%B4

вообще у меня получилось - надо найти N в уравнении

N * 1000000 = (N+1) * (Ln N + 0,5772)

Ясно решается, но только подбором (я иначе не умею)

← →
cwl © (2009-11-04 02:02) [26]

моя мысль:
ось х c началом в том конце ленты, где червяка нет.
начальные условия: длина ленты = L (1 км)
положение червяка на оси х = l
v = 1 км/с
u = 1 мм/с
_______________________________________________
за dt произойдет следующее:
лента между 0 и положением червяка (l) удлинится на l*v*dt/(L+v*t)
тогда l + l*v*dt/(L+v*t) - u*dt = l^
// где l^ - координата червяка в момент t+dt

получается dl/dt = l*v/(L+v*t) - u

пока не решается - нелинейное, однако

← →
Inovet © (2009-11-04 02:07) [27]

Vw - скорость червя, Vt - скорость ленты, S0 - начальное расстояние

В системе координат червя
S(t) = Vt * t * S0 / (S0 - (Vt - Vw) * t)
осталось решить
Vt * t * S0 / (S0 - (Vt - Vw) * t) = 0
Так вроде, если не соврал, поскольку сижу в наушниках с третьей кружкой слабого зелёного чая.:)

← →
Inovet © (2009-11-04 02:08) [28]

> [24] McSimm © (04.11.09 01:57)
> решил через гармонический ряд

Да там линейно же.

← →
McSimm © (2009-11-04 02:08) [29]

e^100000 ~ 2.8*10^43429
почти правильно :)) подумаешь, ошибся в 3.5*10^1570 раз всего :)

какое там количество молекул во вселенной? что-то около 10^99 ?

← →
Inovet © (2009-11-04 02:09) [30]

> [28] Inovet © (04.11.09 02:08)
> > [24] McSimm © (04.11.09 01:57)
> > решил через гармонический ряд
>
> Да там линейно же.

Всмысле непрерывно.:)

← →
McSimm © (2009-11-04 02:11) [31]

непрерывно у меня не получилось

← →
cwl © (2009-11-04 02:12) [32]

Inovet © (04.11.09 02:07) [27]
> Vt * t * S0 / (S0 - (Vt - Vw) * t)
лента ведь удлиняется

← →
McSimm © (2009-11-04 02:21) [33]

можно перейти в другую систему отсчета, в которой лента имеет постоянную длину 1, а червяк ползет с постоянно уменьшющейся скоростью 1/t

← →
Inovet © (2009-11-04 02:24) [34]

> [32] cwl © (04.11.09 02:12)
> Inovet © (04.11.09 02:07) [27]
> > Vt * t * S0 / (S0 - (Vt - Vw) * t)
> лента ведь удлиняется

Не хочу сейчас уравнение выводить, но где-то в этом направлении.

← →
Германн © (2009-11-04 02:27) [35]

> Inovet © (04.11.09 02:24) [34]

Значит нужно выключить комп и идти спать.

← →
Inovet © (2009-11-04 02:33) [36]

> [35] Германн © (04.11.09 02:27)
>
> > Inovet © (04.11.09 02:24) [34]
>
> Значит нужно выключить комп и идти спать.

Не, в голове просто другое, а прерывать жалко.

← →
Inovet © (2009-11-04 02:48) [37]

> [27] Inovet © (04.11.09 02:07)
> осталось решить
> Vt * t * S0 / (S0 - (Vt - Vw) * t) = 0
> Так вроде, если не соврал

Решил t = 0.:)))

← →
TIF © (2009-11-04 03:18) [38]

> Давным давно, еще в школе я читал рассказ в каком то сборнике
> советской фантастики там как раз экспериментальным путем
> проверяли подобную вещь. Допрыгает или нет лягушка до конца
> пути если с каждым прыжком путь будет увеличиваться в 2
> раза.

Филип Кинред Дик. О неутомимой лягушке
http://lib.ru/INOFANT/DICKP/lyagushka.txt
?
К его столу подошел студент. - Профессор Харди... Харди поднял голову. - Да? Что случилось? - Там в коридоре вас ждет какой-то человек, закутанный в одеяло. Он чем-то расстроен. - Ладно, - сказал Харди, вздохнул и встал. У дверей он остановился, снова глубоко вздохнул, потом сжал губы и вышел в коридор. За дверями, завернутый в красное шерстяное одеяло, его ждал Гроут. Лицо его горело от возбуждения. Харди посмотрел на него виноватым взглядом. - Мы так и не выяснили! - закричал Гроут. - Что? - пробормотал Харди. - Послушайте, э-э-э, Гроут... - Мы так и не выяснили, доберется ли лягушка до конца трубы. Мы с ней провалились между атомами. Нам придется придумать какой-то другой метод проверки парадокса. "Камера" для этого не годится. - Да, пожалуй, - произнес Харди. - Но, послушайте, Гроут... - Об этом позже, - сказал Гроут. - Я найду вас сегодня вечером. А сейчас мне надо на лекцию. И он, поддерживая одеяло руками, торопливо зашагал по коридору.

← →
oldman © (2009-11-04 11:35) [39]

1 км = 1000000 мм
через секунду длина ленты стала 2000000 мм
червяк прополз 1, оставалось 999999
теперь остается 1999998
еще через секунду остается 2999996

ряд расходится

не взлетит!

ЗЫ: через минут длина ленты будет 60 км, через час 3600 км и т.д.
за минуту червяк проползет 60 мм, за час 3,6 м и т.д.
остатки сзади несравнимы с бездной впереди...

не взлетит!

← →
Anatoly Podgoretsky © (2009-11-04 11:36) [40]

> McSimm (04.11.2009 01:04:00) [0]

А в какую сторону длина растет?

← →
McSimm © (2009-11-04 11:39) [41]

> Anatoly Podgoretsky © (04.11.09 11:36) [40]
>
> > McSimm (04.11.2009 01:04:00) [0]
>
> А в какую сторону длина растет?

относительно чего ? :)
каждую секунду длина ленты увеличивается на один км. растяжение равномерно по всей длине

← →
Anatoly Podgoretsky © (2009-11-04 11:41) [42]

То есть в обе стороны, ну тогда просто долго придется прыгать.

← →
McSimm © (2009-11-04 11:42) [43]

> oldman © (04.11.09 11:35) [39]
> не взлетит!
> остатки сзади несравнимы с бездной впереди...

это эмоции, а не математика.
у нашего червяка запас времени не ограничен

← →
oldman © (2009-11-04 11:56) [44]

> McSimm © (04.11.09 11:42) [43]
> у нашего червяка запас времени не ограничен

У ленты тоже. Если она через час будет длиной 3600 км, сколько она будет через год? Через век?

"Либо я умру, либо эмир, либо ишак" (Х.Насреддин ©)

← →
McSimm © (2009-11-04 12:00) [45]

к моменту, когда червяк доползет, умрут все эмиры и ишаки. Но на результат задачи это не влияет :)
доползет

← →
Суслик_ (2009-11-04 12:04) [46]

> oldman © (04.11.09 11:56) [44]
>
>
> > McSimm © (04.11.09 11:42) [43]
> > у нашего червяка запас времени не ограничен
>
>
> У ленты тоже. Если она через час будет длиной 3600 км, сколько
> она будет через год? Через век?

построй модель )

М - миллион (для краткости)

На шаге 0 осталось пройти M
На шаге 1 осталось пройти (M-1)*(1+1)/ 1
2 ((M-1)*(1+1)/1-1))*(2+1)/2
3 (((M-1)*(1+1)/1-1))*(2+1)/2-1)*(3+1)/3
и т.д.

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

(сумма гармонического ряда оценивается примерно логарифмом)
Т.е. дойдет он до конца.

← →
DVM © (2009-11-04 12:20) [47]

> TIF © (04.11.09 03:18) [38]

оно, сборник зарубежной фантастики это вероятно был.

← →
Anatoly Podgoretsky © (2009-11-04 13:06) [48]

> McSimm (04.11.2009 11:42:43) [43]

У нас очень УПОРНЫЙ червяк

← →
Anatoly Podgoretsky © (2009-11-04 13:07) [49]

> oldman (04.11.2009 11:56:44) [44]

Червяк даже если и не будет двигаться, то через некоторое время будет уже на половине пути, а он гад движется, постоянно меняя соотношение пройденого к оставшему в свою пользу.

← →
McSimm © (2009-11-04 13:13) [50]

> Червяк даже если и не будет двигаться, то через некоторое
> время будет уже на половине пути,

нет, если он не двигается, то отношение пройденного пути к оставшемуся неизменно. лента-то однородная

← →
Jeer © (2009-11-05 09:27) [51]

> нет, если он не двигается, то отношение пройденного пути
> к оставшемуся неизменно. лента-то однородная
>

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

← →
Inovet © (2009-11-05 09:36) [52]

> [51] Jeer © (05.11.09 09:27)

А если червяк растягивается вместе с лентой, обретает больше сил и ползёт быстрее, то всё совсем просто.:)

Предлагаю уточнить сделующие моменты в условии, подразумевающие написанные не очень почто, по-моему:

1) Червяк имеет пренебрежимо малую длину, верно?

2) "При этом ленту растягивают со скоростью один километр в секунду (каждую секунду лента становится на один км. длиннее)"
Тут не понятно: лента постоянно растягивается со скоростью км/сек, или раз в секунду ее длина одномоментно увеличивается на 1 км? На результат влияет, однако.

> Inovet © (05.11.09 09:36) [52]
> А если червяк растягивается вместе с лентой, обретает больше
> сил и ползёт быстрее, то всё совсем просто.:)

А если еще он догоняет червячиху на дальнем конце ленты ? :)

> 1) Червяк имеет пренебрежимо малую длину, верно?

Не принципиально, можно говорить о кончике языка червяка, как о отсчетной точке :)

> 2) "При этом ленту растягивают со скоростью один километр
> в секунду (каждую секунду лента становится на один км. длиннее)"
> Тут не понятно: лента постоянно растягивается со скоростью
> км/сек, или раз в секунду ее длина одномоментно увеличивается
> на 1 км? На результат влияет, однако.
>

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

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

Это неправильная логика. Пропорция может постоянно меняться в его пользу, но само по себе это еще ничего не доказывает, т.к. ничего не говорит о скорости роста оставшегося пути.

Например если лента каждую секунду растягивается вдвое, то отношение отставшегося к пройденному тоже уменьшается, но ни дойти, ни вернуться он, пожалуй, не сможет.

Если

> Пропорция может постоянно меняться в его пользу,

то рано или поздно будет 100% пройденного пути.

да ну? :)

> Jeer © (05.11.09 10:54) [54]
> Не принципиально, можно говорить о кончике языка червяка, как о отсчетной точке :)
> Переход от непрерывной модели к дискретной качественно не должен влиять на результат.

McSimm изначально завел ветку не на тему "взлетит/не взлетит", а на тему конкретной цифири. Тогда это важно.

> не на тему "взлетит/не взлетит", а на тему конкретной цифири.
> Тогда это важно.

Непрерывную модель я даже не знаю как подступиться. Ряды дают результат. А как-то можно показать, что дискретная модель неадекватна ?

Ну можно принять длину ленты за единицу.
И расчитать относительную скорость червяка.
V=1/(1000000*t)

А тут уже все зависит от того сходится или расходится ряд:
1, 1/2, 1/3, 1/4, 1/5 .....

Червяк имеет скорость V=1 мм/сек, длина ленты L= 1км, происходит ежесекундное растяжение ленты на длину K=1 км, т.е. в два раза

Рассмотрим дискретную модель
За каждую секунду червяк преодолевает некоторый относительный путь.
Когда относительный путь червяка станет больше 1, значит от преодолел ленту.

За первую секунду отн. путь равен V/L, за вторую V/2*L, за третью V/3*L и тд, т.е.

S = (V/L)*(1/1 + 1/2 + 1/3 +..+ 1/n)
Где n - дискретное время, например, 1 сек.
След-но, находя n при S>=1, мы определяем время, за которое червяк достигнет конца расширяющейся ленты.
При заданных числовых значениях имеем
S = 1*10^-6 * sum(1/k) >=1
следовательно сумма ряда должна быть более 1 млн, чтобы червяк допрыгал

Ряд в скобках не, что иное как ряд из т.н. гармонических чисел H(n) = sum(1/k), 1<=k<=n
Можно вычислять рекурсивно как:
H(n) = H(n-1) + 1/n
или:
H(n) = g + a(n+1)
где g = 0.57721... - постоянная Эйлера
a(n+1) - дигамма-функция

> происходит ежесекундное растяжение ленты на длину K=1 км,

Поправка

> все это уже было в теме не раз.

Ну, значит читал/смотрел по диагонали.
От моих комментариев хуже не стало

> Ну, значит читал/смотрел по диагонали.
> От моих комментариев хуже не стало

Аналогично

> KSergey © (05.11.09 12:15) [59]
> McSimm изначально завел ветку не на тему "взлетит/не взлетит",
> а на тему конкретной цифири. Тогда это важно.

Имеется (не мое) доказательство, что если
H(n-1) < V/L <= H(n) и n - целое положительное число, такое, что H(n-1) <= a <= H(n), то
exp(a-g) < n <= exp(a-g)

(обозначения см.выше в моих постах)

Вот и оценка числа n :)

Грубо n ~ e^(L/V)

Вот другое дело, если закон изменения длины ленты не есть арифм.сумма - тогда вопрос только к пределу ряда и его сходимости.

> то
> exp(a-g) < n <= exp(a-g)

наверное опечатка, exp(a+g) справа ?

угу :)

Вскольз просмотрел тему, но "диффура" не увидел. :)
Вот с дифуром:

Скорость точки жгута, на расстоянии x от неподвижного конца:
u(x,t) = u0*x/(s0+u0*t) где u0 - скорость конца жгута, s0 - начальная длина жгута, t - время от начала растягивания.

Отсюда скорость червя относительно "универсума":

dx/dt = u(x,t)-v где v- скорость червя ("минус" - потому-что он ползет к началу).

Решаем диффур с условием x(0)=s0,
получаем:
x(t) = ((v*ln(s0)+u0)/u0-v*ln(s0+u0*t)/u0)*(s0+u0*t)

откуда находим время до прибытия червя (из x(T)=0)):
T = s0*(exp(u0/v)-1)/u0;

Для данных, указанных в задаче:
s0 = 1000; u0 = 1000; v=10^(-3)

И
T = exp(1000000)-1

cwl © (04.11.09 2:02) [26]

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

Прошу прощения: в [72], + метод неопределенных коэфициентов
Но все равно просто

Дифура была, только ее не решили. Вот более полно расписанное решение, которое я когда-то делал:

http://mu.webest.net/pdf/spider.pdf

Об упорных червяках и математике Найти похожие ветки