Итак, прошло три года. Петя, Витя и Лариса стали студентами. Как-то они собрались в гости к Дум Думычу на его день рождения.
– Давайте решим, наконец, задачку о паучке, порадуем Дум Думыча. – предложила Лариса.
– Если паучок умный, то он может смотреть на бирки, читать, что на них написано, и ориентироваться не на столкновения с мухами, а на бирки. – выдал Петя. Друзья смутно почувствовали, что это хорошая мысль, но с ходу не поняли, что с ней делать.
– Если он умный, – прервала молчание Лариса, – то у него должно работать воображение.
– Пусть вообразит наряду с реальными чёрными дополнительных белых мух. – изрёк Витя. – Пометим их числами 1,2, .. направо от начальной позиции (НП) паучка возле бирки 0, и числами –1, –2,… налево от НП. Пусть в начальный момент белая муха с меткой n находится на расстоянии nH вправо от бирки 0, а белая муха с меткой –n находится на расстоянии nH влево от бирки 0, где Н – расстояние, пробегаемое паучком за 1 с. Если V – скорость паучка (м/с), то Н=V как числовые величины.
– Пусть белая муха с меткой n и аналогично белая муха с меткой –n, – подхватил Петя, – удирает от паучка со скоростью (1–d(n))V, где d(1),d(2),... - какая-нибудь убывающая к нулю последовательность чисел, меньших 1 (например, 1/2, 1/3, 1/4, ... ).
– Тогда, – воскликнула Лариса, – для любой чёрной мухи найдётся такая пара белых мух, симметрично удаляющихся от бирки 0, каждая из которых, во-первых, дальше в начальный момент от бирки 0, чем чёрная муха, а во-вторых, быстрее ползает.
– А это значит, – продолжил Витя, – что, догнав по очереди обеих белых мух, паучок по пути непременно повстречает и ту чёрную муху, для которой мы подобрали эту пару белых. Перед встречей, завидев его, чёрная муха будет от него удирать.
– Таким образом, – заметил Петя, – задача о реальном догоне всех реальных чёрных мух сводится к задаче о воображаемом догоне всех воображаемых белых мух. А для этой задачи Витя в прошлый раз придумал метод челнока.
– Но как паучок поймёт, что вот в данный момент, ни секундой раньше, ни секундой позже, он настиг очередную белую муху? – спросила Лариса. – Она же воображаемая!
– Давайте сначала используем подсказку, что у него на лапке часики, – решил Витя и набросал на листке бумаги алгоритм.
Пусть в начале часики, измеряющие время в секундах, показывают значение
Челночный цикл с номером n=1,2,... выглядит следующим образом.
В момент T(n) паучок стартует из НП, двигаясь по проволоке со скоростью V направо, чтобы догнать белую муху с меткой n. К моменту T(n) эта белая муха находится на расстоянии
от НП. Паучок догоняет её за время t(1,n)=R(1,n)/(d(n)V). Поскольку H=V, V сокращается:
Догнав муху в момент T(n)+t(1,n), паучок возвращается в НП, двигаясь по проволоке со скоростью V, за время t(1,n), то есть к моменту T(n)+2t(1,n) .
К этому моменту белая муха с меткой –n находится на расстоянии
от НП. Паучок догоняет её за время t(2,n)=R(2,n)/(d(n)V). Поскольку H=V, V сокращается:
Догнав муху в момент T(n)+2t(1,n)+t(2,n), паучок возвращается в НП за время t(2,n), то есть к моменту
По формулам (1)–(6) можно последовательно рассчитать моменты разворотов паучка в его челночных циклах: T(1)+t(1,1), T(1)+2t(1,1)+t(2,1) в первом цикле, T(2)+t(1,2), T(2)+2t(1,2)+t(2,2) во втором и т.д.
– С часиками у нас получилось. – сказала Лариса, изучив вместе с Петей алгоритм Вити. – А теперь без часиков. Твой выход, Петя!
– Это просто! – сказал Петя. – Паучку не обязательно останавливаться и разворачиваться именно в тот момент, когда он настигает очередную белую муху. Он может развернуться чуть позже, когда сравняется с очередной биркой.
Петя набросал на листке бумаги свой алгоритм, приговаривая:
– Усложним немного алгоритм Вити. Некоторые формулы останутся прежними, но мы выпишем их под новыми номерами, чтобы все формулы были в одной кучке.
Пусть в начале воображаемые часики (которых в реальности нет на лапке паучка) показывают значение
Челночный цикл с номером n выглядит так. В момент T(n) паучок стартует из НП направо, чтобы догнать белую муху с меткой n. К моменту T(n) эта белая муха находится на расстоянии
от НП. Паучок догоняет её за время
то есть в момент T(n)+t(1,n) , находясь между бирками B(1,n) и B(1,n)+1, где
Догнав муху, паучок не останавливается, а бежит до бирки B(1,n)+1, на что он тратит дополнительное время
Сравнявшись с биркой B(1,n)+1, паучок разворачивается и возвращается в НП за время t(1,n)+b(1,n), то есть к моменту T(n)+2(t(1,n)+b(1,n)).
К этому моменту белая муха с меткой –n находится на расстоянии
от НП. Паучок догоняет её за время
то есть в момент T(n)+2(t(1,n)+b(1,n))+t(2,n), находясь между бирками B(2,n) и B(2,n)–1, где
Догнав муху, паучок не останавливается, а бежит до бирки B(2,n)–1, на что он тратит дополнительное время
Сравнявшись с биркой B(2,n)–1, паучок разворачивается и возвращается в НП за время t(2,n)+b(2,n), то есть к моменту
Лариса изучила вместе с Витей алгоритм Пети и подвела итог:
– Паучок должен быть очень, очень умным, чтобы настигнуть всех мух. Он может это сделать как с часиками на лапке без внимания к биркам на проволоке с помощью формул (1)–(6), так и без часиков, ориентируясь только по биркам с помощью формул (7)–(16).
– Пожалуй, он должен быть даже умнее нас. – заметил Витя.
Друзья ещё не знали, что они решили только задачу № 1 Дум Думыча о неугомонном паучке, да и то не полностью.
На встрече с ними он посмотрел найденное ими решение и поинтересовался:
– А как паучок узнает свою скорость в случае, если он ориентируется по биркам?
– Он может измерить её, побегав между двумя далеко разнесёнными бирками! – воскликнул Петя.
– При этом он должен знать величину A. – заметил Витя.
– Получается, что без часиков и рулетки никак? – огорчилась Лариса.
Продолжение следует