В подвале три коридора (рисунок 1: $|OA|=|OB|=|OC|=l$), все выходы из которых закрыты. В нём находятся инспектор Варнике и преступник. Варнике замечает преступника, если расстояние между ними не превосходит $r$. Он знает, что максимальная скорость преступника в два раза меньше его собственной максимальной скорости. В начальный момент инспектор находится в точке $O$ и не видит преступника. Как должен действовать Варнике, чтобы наверняка поймать преступника, если
Рис. 1
$r=\dfrac l3$,
$r=\dfrac l4$,
$r\gt\dfrac l5$,
$r\gt\dfrac l7$.
Шириной коридоров и размерами людей пренебречь. (Варнике должен придумать такой план действий, чтобы, даже если преступник о нём заранее знает, он всё равно не смог ускользнуть.)
1. Решение задачи при $\bm{r\gt\dfrac l5}$$\Big($в частности, при $r=\dfrac l3$ и $r=\dfrac l4\Big)$. Сначала Варнике «прочёсывает» коридор $OC$. Убедившись, что преступника там нет, Варнике удаляется в коридор $OA$ на расстояние $2r$ и затем возвращается в точку $O$, двигаясь с максимальной скоростью (в дальнейшем будет подразумеваться, что инспектор всегда движется с максимальной скоростью). Предположим, что, вернувшись в точку $O$, инспектор не увидел преступника; что ему в таком случае известно о возможном местонахождении преступника?
1) Преступник не может находиться в коридоре $OC$: легко проверить, что если бы он за время отсутствия инспектора в точке $O$ попытался перебежать из коридора $OB$ в коридор $OC$, то к моменту возвращения инспектора в точку $O$ расстояние от преступника до $O$ было бы не больше, чем $r$.
Рис. 2
2) Если преступник находится в коридоре $OA$, то на расстоянии от $O$, большем $2r$: действительно, когда инспектор был в коридоре $OA$ на расстоянии $2r$ от $O$, то преступник (если он находился в $OA$) был на расстоянии от $O$, большем $3r$, а к моменту возвращения инспектора в точку $O$ расстояние от преступника до $O$ могло уменьшиться не более чем на $r$ (рис. 2).
Если же $r\ge\dfrac l3$, то преступник вообще не может находиться в $OA$ и тем самым задача а) решена: чтобы поймать преступника, инспектору достаточно исследовать до конца коридор $OB$.
Если $r\lt\dfrac l3$, то смысл дальнейших действий инспектора заключается в том, чтобы углубляться то в коридор $OB$, то в коридор $OA$ на все большие расстояния, но так, чтобы преступник не смог перебежать в коридор $OC$. Каждое такое углубление вместе с последующим возвратом в точку $O$ будем называть циклом. Первый цикл уже описан. Во втором цикле инспектор отправляется в коридор $OB$ на расстояние $3r$. Вернувшись в точку $O$ и не увидев преступника, инспектор знает, что
1) в коридоре $OC$ преступника нет (если преступник находится в коридоре $OA$, то — на расстоянии от $O$, больше $2r$, и потому до возвращения Варинке в точку $O$, при удалении его на расстояние $3r$ в коридор $OB$, преступник не сможет перебежать в коридор $OC$ так, чтобы при этом оказаться на расстоянии от $O$, больше $r$);
2) если преступник находится в коридоре $OB$, то расстояние от него до $O$ больше $\dfrac{5r}2$ $\Big($больше $(3r+r)-\dfrac{3r}2\Big)$.
Если же $r\ge\dfrac l4$, то преступник вообще не может находиться в коридоре $OB$ (поскольку тогда его длина больше $3r+r=4r\ge l$ — противоречие); тем самым решена задача б).
Пусть после цикла с номером $n$ инспектор знает, что в коридоре $OC$ преступника нет, а в коридоре $OX$ (где $X=A$ при $n$ нечётном и $X=B$ при $n$ чётном) преступник не может находиться на расстоянии от $O$, меньшем или равном $y_n$. Тогда в следующем цикле инспектор отправляется в другой коридор на расстояние $y_n+r$ (рис. 3). Вернувшись в точку $O$, инспектор знает, что
Рис. 3
1) в коридоре $OC$ преступника нет;
2) в только что исследованном коридоре преступник не может находиться на расстоянии от $O$, меньшем или равном $y_{n+1}=\dfrac{y_n+3r}2=\dfrac{y_n+r}2+r$;
если же $y_n+r\ge l-r$, то в исследованном коридоре преступника вообще нет.
Найдём формулу для $y_n$. Так как $y_{n+1}=\dfrac{y_n+3r}2$, то $3r-y_{n+1}=\dfrac{3r-y_n}2$, откуда $3r-y_n=\dfrac{3r-y_1}{2^{n-1}}=\dfrac r{2^{n-1}}$, т. е. $y_n=3r-\dfrac r{2^{n-1}}$. Преступник ловится, если $y_n+r\ge l-r$ при каком-нибудь $n$, т. е. $\dfrac r{2^{n-1}}\le 5r-l$. Отсюда видно, что если $5r\gt l$, то после достаточно большого числа циклов преступник ловится.
2. Решение задачи при $\bm{\dfrac l7\lt r\le \dfrac l5}$ использует следующую новую идею: после достаточно большого числа циклов, описанных в разделе 1, инспектор должен углубиться в очередной коридор на расстояние не $y_n+r$, а $l-r$ (т. е. «прочесать» его до конца), не обращая внимания на то, что преступник может перебежать в коридор $OC$.
Положим $\eps=\dfrac{7r-l}2$. Инспектор должен действовать так, как описано в разделе 1, до тех пор пока не будет выполняться неравенство $y_n\gt3r-\eps$. После этого инспектор углубляется в очередной коридор (скажем, $OA$) на расстояние $l-r$. Вернувшись в точку $O$ и не увидев преступника, инспектор знает, что в коридоре $OA$ преступника нет, а в коридоре $OC$ преступник не может находиться на расстоянии от $O$, большем $(l-r)-(3r-\eps)=3r-\eps$. Затем инспектор углубляется в коридор $OC$ на расстояние $4r-2\eps$. Вернувшись в точку $O$ и не увидев преступника, инспектор знает, что в коридоре $OC$ преступника нет (поскольку в противном случае преступник был бы пойман, оказавшись в коридоре $OC$ от Варнике на расстоянии, меньшем $(3r-\eps)+\dfrac{4r-2\eps}2-(4r-2\eps)=r\Big)$, а в коридоре $OA$ преступник не может находиться на расстоянии от $O$, большем $3r-2\eps$ ($=(4r-2\eps)-r$). Затем инспектор идёт в коридор $OA$ на расстояние $4r-4\eps$, затем в коридор $OC$ на расстояние $4r-8\eps$, снова в коридор $OA$ на расстояние $4r-16\eps$ и т. д. Когда инспектор увидит, что ему надо идти на отрицательное расстояние, он должен сделать вывод, что преступник находится в коридоре $OB$.
Замечание. Удалось доказать, что при $r\le\dfrac l7$ не существует способа наверняка поймать преступника. Доказательства этого факта, принадлежащие И. Голубчику и В. Прасолову, сложные и поэтому здесь не приводятся.
