Ещё раз прочтём задачу № 4, доставшуюся Ларисе.
По плоскости стелется конструкция из отрезков, напоминающая поваленное дерево с обилием веток. Из корня исходит 1 «побег» нулевого уровня. Каждый «побег» n-го уровня ветвится на M(n)>1 «побегов» n+1-го уровня. Суммарная длина «побегов» каждого уровня равна R м, причём все они равны по длине. По «побегам» ползают мухи, не мешая друг другу. Каждая когда-то стартовала из корня «дерева». Двигаться вспять мухе запрещено. При переходе с «побега» n-го уровня на «побег» n+1-го уровня муха уменьшает свою скорость в M(n) раз. Скорость мухи на «побеге» нулевого уровня (стартовая скорость) меньше W м/с. При этом разница может быть сколь угодно малой. В некоторый момент на корень «дерева» запрыгивает паучок. Он может носиться в любом направлении по всем «побегам», различая их. Его скорость в C раз больше W. Существует ли такое C, при котором паучок сможет догнать всех мух?
Вот как рассуждала Лариса. По условию задачи новые мухи после появления паучка на «дерево» не забираются (старт каждой из них отнесён к прошлому). Постараемся вместе с поиском какого-нибудь C найти попутно и минимальное C (возможно, что оно нецелое), а также выяснить, можно ли допустить появление новых мух.
Предположим, что паучок сможет догнать всех мух при некотором C в варианте без появления новых мух. Первое, что сделает паучок: промчится до конца «побега» нулевого уровня. Этот «побег» он больше не будет исследовать, догнав на нём всех встретившихся мух. Дальнейшие события будем рассматривать с момента первого появления паучка в конце «побега» нулевого уровня, считая этот конец базовой позицией (БП) паучка.
При n=1,2,… паучок со скоростью V=CW
а) стартуя из БП, исследует все «побеги» c 1-го по N(n)-й уровень и
б) возвращается в БП, чтобы продлить все исследованные траектории так, чтобы охватить все «побеги» с N(n)+1-го по N(n+1)-й уровень.
Поскольку систематические возвращения паучка в БП неизбежны, появление новых мух не влияет на ответ задачи: каждая новая муха, стартовав из корня «дерева», рано или поздно достигает БП, после чего паучок, не возвращающийся в корень «дерева», заведомо догоняет новую муху как отстающую от старых, если он догоняет старых мух. В дальнейших рассуждениях считаем для их упрощения, что новые мухи не появляются.
Предположим, что паучок не мудрствует и реализует n-ую вылазку из БП таким образом, что «побеги» N(n)+1-го уровня и выше выборочно не исследуются.
Введём удобное обозначение N(0)=0. Чтобы охватить при n-ой вылазке из БП все «побеги» c N(n–1)+1-го по N(n)-й уровень, паучок должен пробежать каждый «побег» на уровнях с 1-го по N(n)-й как минимум дважды (возвращаясь в точкам ветвления, чтобы перейти к другим «побегам»).
Существует (и не один) оптимальный алгоритм вылазки, при котором паучок пробегает каждый «побег» ровно 2 раза. Занумеруем как-нибудь все «побеги» отдельно на каждом уровне. Первое движение паучка – проход из БП по первому «побегу» первого уровня. Правила движения паучка из точки ветвления в конце «побега» m-го уровня.
1) Если есть хотя бы один исходящий «побег» m+1-го уровня, который паучок при n-й вылазке ещё ни разу не проходил и m+1≤N(n), то паучок выбирает из таких «побегов» «побег» с минимальным номером и проходит его.
2) Если m=N(n) или все исходящие «побеги» m+1-го уровня уже были пройдены дважды, то паучок направляется из конца «побега» m-го уровня в его начало.
В любом таком алгоритме финальная часть – возвращение в БП по единственному пути, начинающемуся от конца некоторого «побега» N(n)-го уровня. Найдём длину этого пути D(N(n)). Нам понадобится число J(k) «побегов» k-го уровня. Оно вычисляется по рекуррентным формулам
Заметим, что величины J(k) при k=0,1,2, … растут быстрее, чем 2ᵏ . Длина «побега» k-го уровня равна R/J(k). Имеем
где
(оценка L(k)<1=(1/2+1/4+1/8+…) следует из того, что 1/J(k)<1/2ᵏ при любом k).
При оптимальном (двукратном) прохождении «побегов» продолжительность n-й вылазки паучка T(n), время U(n) от начала n-й вылазки до начала её финальной части и время S(n) от начала первой до начала n-й вылазки равны
Муха имеет стартовую скорость
(1–p)W (м/с),
где p – характеризующая муху положительная величина, меньшая 1. На «побеге» первого уровня скорость мухи равна
(1–p)W/M(0).
На «побеге» второго уровня скорость мухи становится равной
(1–p)W/(M(0)M(1)).
Вообще, на «побеге» k-го уровня муха имеет скорость
(1–p)W/J(k) и проползает этот «побег» за время
(R/J(k))/((1–p)W/J(k))=R/((1–p)W) секунд.
Путь от начала «побега» 1-го уровня до конца «побега» N(n)-го уровня муха преодолевает за время (в секундах)
Казалось бы, скорость мухи, ползущей по «побегу», убывает с ростом уровня побега. При этом отношение скорости паучка к скорости мухи растёт. Однако, паучку нужно догонять не одну муху, а всех возможных мух по всем «побегам», число которых столь же стремительно растёт, обесценивая рост относительной скорости паучка.
Пусть муха стартует из БП за q>0 секунд до начала первой вылазки паучка. Мы установили, что муха проползает от БП до конца «побега» N(n)-го уровня за время N(n)R/((1–p)W) секунд, где 0<p<1 – параметр мухи. Для того, чтобы паучок при n-ой вылазке из БП при оптимальном обходе «побегов» успел догнать муху, по какой-бы траектории она ни удирала, должно быть
Умножим обе части неравенства (61) на CW/R , воспользуемся формулами (57)–(59) и перенесём все слагаемые, не содержащие q, в правую часть.
Для того, чтобы неравенство (62) могло выполниться при достаточно большом q, необходимо, чтобы множитель С/(1–p)–2 при величине N(n), возрастающей с ростом n, был положительным (ибо L(N(n))<1). При 1<C<2 множитель С/(1–p)–2 оказывается отрицательным при 0<p<1–C/2, то есть возможны такие пары (p,q), при которых паучок не догонит соответствующих мух. Поэтому для догона обязательно С≥2. Предположим, что паучок справится со своей задачей догнать всех мух уже при С=2. При этом значении C неравенство (62) эквивалентно неравенству
Попробуем выстроить последовательность N(1),N(2),… таким образом, чтобы паучок смог догнать всех мух без знания W и R и без часиков на лапке для организации вылазок из БП. Он может вообразить себе вдобавок к реальным чёрным мухам белых мух, задав для них q и p следующим образом. Возьмём убывающую к нулю последовательность d(1),d(2),… чисел из интервала (0,1) и последовательность неограниченно возрастающих положительных величин Q(1),Q(2),… . Отряд белых мух, имеющий номер n, пусть состоит из мух, для каждой из которых q=Q(n) и p=d(n), которые по всем возможным траекториям ползут до концов «побегов» N(n)-го уровня и настигаются паучком при его n-й вылазке из БП. Тогда для любой реальной чёрной мухи отыщется воображаемая белая, которая а) стартует из БП раньше чёрной и б) ползает быстрее. Догнав всех воображаемых белых мух, паучок попутно догонит всех чёрных.
Для определённости возьмём
Чтобы при каждом n для белых мух из n-го отряда выполнялось неравенство (63) (условие догона мухи при n-ой вылазке паучка из БП) можно потребовать
После подстановки p=d(n)=1/(n+1) и q=Q(n) выходит p/(1–p)=1/n и
Полагая Q(n)=nR/W, получаем рекуррентные формулы
Один из искомых алгоритмов для паучка при C=2 найден. Тот же алгоритм сработает при C>2 (разница только в том, что паучок будет быстрее догонять мух).
Итак, паучок не угонится за всеми мухами при C<2, но угонится при C≥2, даже если допустить появление новых мух. Для этого ему нужно (один из вариантов) при n=1,2,… без устали и остановок осуществлять вылазки из БП, пробегая при n-й вылазке по оптимальному маршруту все «побеги» на уровнях 1,…,N(n), где N(n) вычисляются по формулам (69).
Несколько первых значений: N(1)=1, N(2)=4+2×1=6, N(3)=9+3×(1+6)=30, N(4)=16+4×(1+6+30)=164, N(5)=25+5×(1+6+30+164)=1030.