Ещё раз вчитаемся задачу № 5, доставшуюся Васе.
Плоскость разбита сеткой горизонтальных и вертикальных прямых на клетки размером 1 м на 1 м. Среди этих прямых обе координатные оси. Единица измерения по каждой оси 1 м. По прямым ползают мухи. Каждая муха стартовала в своё время из начала координат. Её стартовая скорость была меньше некоторой величины W (м/с). Разница могла быть сколь угодно малой. При r=1,2,... муха, достигнув границы квадрата с вертикальной стороной 2r (м) и центром в начале координат, приобретает скорость, уменьшенную по сравнению со стартовой в 1+r раз. Внутрь каждого такого квадрата муха не возвращается. До достижения границы следующего такого квадрата величина скорости мухи не меняется. При этом мухе разрешено переползать с одной прямой на другую через точки их пересечения. Движение вспять для мухи запрещено. Паучок запрыгивает в начало координат и может бегать по всем прямым, перебегая с одной на другую через точки их пересечения, различая эти точки по их координатам. Его скорость в C раз больше W. Существует ли такое C, при котором паучок сможет повстречать всех мух?
Вася рассуждал так. Предположим, что такое C существует. Занумеруем канонические квадраты (квадраты с целочисленными координатами углов и центром в начале координат) в порядке возрастания их размеров. Канонический квадрат с нулевым номером – точка в начале координат.
Мухе разрешено а) ползать по границе любого невырожденного канонического квадрата и б) смещаться по любому горизонтальному или вертикальному отрезку с целочисленными координатами концов, соединяющему границу предыдущего канонического квадрата с границей следующего, двигаясь строго в сторону границы следующего квадрата.
От границы n-го канонического квадрата (со стороной 2n и периметром 8n) к границе (n+1)-го квадрата ведут 4(2n+1) доступных для мухи путей.
Чтобы не пропустить ни одну муху, способную маневрировать, паучок должен пробежать хотя бы 1 раз (направление не важно) по каждому горизонтальному и вертикальному отрезку, соединяющему начало координат с границей первого канонического квадрата, после чего в цикле по n=1,2,…
1) выйдя на границу n-го квадрата, пробежать её по часовой стрелке столько раз, сколько нужно, чтобы гарантированно догнать любую удирающую по границе муху, и
2) пробежать хотя бы 1 раз (направление не важно) по каждому разрешённому для мухи пути от границы n-го квадрата к границе (n+1)-го.
Число витков паучка по границе канонического квадрата можно вычислить из следующих соображений. Расстояние, отсчитываемое вдоль границы n-го канонического квадрата по часовой стрелке от паучка до мухи, не превосходит 8n. Это расстояние при гонках по границе сокращается со скоростью не менее V–W/(n+1) (где V=CW – скорость паучка в м/с) за время не более
(8n/V)/(1–1/((n+1)C))≤(8n/V)C/( C–1/2).
Здесь 8n/V – время, соответствующее одному витку паучка вдоль границы n-го канонического квадрата. Таким образом, в качестве числа витков можно взять наименьшее целое, большее или равное С/(C–1/2). При 1<C это будет 2.
Начальная часть траектории паучка может быть следующей:
Паучок пробегает её за время
Далее при n=1,2,… паучок
а) обходит границу n-го канонического квадрата 2 раза по часовой стрелке от точки (–n,–n) к ней же за время t(n,1)=16n/V,
б) движется змейкой вдоль левого края n-го квадрата за время t(n,2)=2(2n+1)/V из точки (–n,–n) в точку (–n,n) по линии
в) движется змейкой вдоль верхнего края n-го квадрата за время t(n,3)=2(2n+1)/V из точки (–n,n) в точку (n,n) по линии
г) движется змейкой вдоль правого края n-го квадрата за время t(n,4)=2(2n+1)/V из точки (n,n) в точку (n,–n) по линии
д) движется змейкой вдоль нижнего края n-го квадрата за время t(n,5)=2(2n+1)/V из точки (n,–n) в точку (–n–1,–n–1) по линии
На весь n-й цикл паучок затрачивает время
Время от начала движения паучка до конца n-го цикла равно
T(0)+…+T(n)=8/V+8(4(1+…+n)+n)/V=8/V+8(2n(n+1)+n)/V
В более компактной форме
Пусть муха стартует из начала координат за q>0 секунд до начала движения паучка, имеет стартовую скорость (1–p)W , где p принадлежит интервалу (0,1), и удаляется от начала координат по одной из координатных осей, не сворачивая (резвая муха). От границы n–1-го до границы n-го канонического квадрата резвая муха проползает за время 1/((1–p)W/n)=n/((1–p)W).
От начала координат до границы n-го канонического квадрата резвая муха проползает за время
Паучок догонит резвую муху, если при некотором n она окажется на границе n-го канонического квадрата позже, чем начнётся n-й цикл (закончится n–1-й цикл), то есть если
Подставляя V=CW и умножая обе части на 2W , находим
Неравенство (73) выполняется при достаточно больших n как следствие более сильного неравенства с заменой 2n–1 величиной 2n+2
Для выполнения неравенства (74) для любого p из интервала (0,1) и любого q>0 при достаточно большом n, зависящем от p и q, необходимо, чтобы величина 32/C не превосходила 1. В этом случае множитель 1/(1–p)–32/C будет больше нуля. Это достигается уже при C=32.
Поскольку паучок догоняет всех резвых мух, он встречает также и всех остальных (отстающих из-за маневрирования). При встречах с отстающими мухами паучок может либо догонять их, либо сближаться с ними лоб в лоб.
Таким образом, паучок повстречает всех мух (если, конечно, не появятся новые), двигаясь при C≥32 по специальной спирали, начало и принцип построения которой представлены на вышеприведённом рисунке.
Продолжение следует