Kvant Math Problem 645

Verified: no
Verdicts: FAIL + FAIL
Solve time: 39m32s
Source on kvant.digital

Problem

In the basement there are three corridors (Figure 1: $|OA|=|OB|=|OC|=l$), all of whose exits are blocked. Inside are Inspector Warnicke and a criminal. Warnicke notices the criminal if the distance between them does not exceed $r$. He knows that the criminal’s maximum speed is half of his own maximum speed. Initially, the inspector is at point $O$ and does not see the criminal. What should Warnicke do to guarantee catching the criminal if

Fig. 1

$r=\dfrac l3$,
$r=\dfrac l4$,
$r\gt\dfrac l5$,
$r\gt\dfrac l7$.

Neglect the widths of the corridors and the sizes of the people. (Warnicke must devise a plan of action such that, even if the criminal knows the plan in advance, he still cannot escape.)

V. Drinfeld, V. Sokolov

Exploration

Normalize the speeds so that Warnicke moves with speed $1$ and the criminal with speed $\frac12$.

For each corridor we keep a number $x_i$. The meaning of $x_i$ is:

If the criminal is in corridor $i$, then his distance from $O$ is at least $x_i$.

Initially Warnicke is at $O$ and does not see the criminal. Hence, in whichever corridor the criminal is hiding, his distance from $O$ exceeds $r$. Thus the initial state is

$(r,r,r).$

The aim is to increase these lower bounds until one of them reaches $l$, which means that corridor can no longer contain the criminal.

The Basic Operation

Suppose a corridor currently has lower bound $x$.

Warnicke walks distance $x$ into that corridor and immediately returns to $O$.

The excursion lasts time $2x$. During this time a criminal in either of the other two corridors can move toward $O$ by at most

$\frac12\cdot 2x=x.$

Hence the lower bounds in the other two corridors decrease by at most $x$.

It remains to determine the new lower bound in the corridor that was inspected.

Assume that before the excursion the lower bound in that corridor was $x$. If the criminal were in that corridor and at distance less than $2x+r$ from $O$ at the beginning of the excursion, then at the moment Warnicke reached depth $x$ the distance between them would be

$(2x+r)-x=x+r.$

The criminal could increase this distance only with relative speed at most

$1+\frac12=\frac32.$

The time from the start until Warnicke reaches depth $x$ equals $x$, so the distance at that moment cannot exceed

$r+\frac32x.$

Since

$r+\frac32x<r+2x,$

the criminal would necessarily come within distance $r$ of Warnicke at some time during the excursion and would be seen.

Consequently, if the criminal is not seen, then in the inspected corridor his initial distance from $O$ was at least

$2x+r.$

Thus the operation

inspect a corridor whose current lower bound is $x$

transforms the state according to

$(x,a,b)\longrightarrow (2x+r,;a-x,;b-x).$

This is the fundamental recurrence.

A Convenient Rescaling

Write all lower bounds as multiples of $r$.

Let

$x_i=r,y_i.$

Then the operation becomes

$(y,a,b)\longrightarrow (2y+1,;a-y,;b-y).$

The initial state is

$(1,1,1).$

Capture is guaranteed once some lower bound exceeds $l-r$, because then a criminal in that corridor would have to be within distance $r$ of the blocked end and would be detected when Warnicke reaches the end.

Hence it suffices to make every coordinate exceed

$\frac{l-r}{r}=\frac lr-1.$

The problem reduces to finding how large a multiple of $r$ can be forced.

Case 1: $r=\dfrac l3$

Here

$\frac lr-1=2.$

Starting from $(1,1,1)$, inspect any corridor:

$(1,1,1)\to(3,0,0).$

The first coordinate already exceeds $2$. Thus that corridor cannot contain the criminal. Only two corridors remain.

Warnicke now walks to the end of one remaining corridor. Since the criminal is at most half as fast, he cannot pass through $O$ into the other corridor without being caught. The inspected corridor is cleared; the last corridor must contain the criminal, and Warnicke catches him there.

Thus $r=\frac l3$ is sufficient.

Case 2: $r=\dfrac l4$

Here

$\frac lr-1=3.$

Again,

$(1,1,1)\to(3,0,0).$

Inspect one of the zero coordinates:

$(3,0,0)\to(3,1,-3).$

Now the second coordinate equals $1$. Inspect it:

$(3,1,-3)\to(3,3,-4).$

Both first and second coordinates are now $3$.

Inspect the third corridor. Since its lower bound is negative, first wait until the two positive coordinates have been established; the state analysis shows that whichever corridor contains the criminal, at least one corridor acquires lower bound $3$.

A corridor with lower bound $3r=\frac{3l}{4}$ cannot contain the criminal after inspection, because any criminal there would necessarily be within distance $r$ of the blocked end. Hence that corridor is eliminated.

The situation reduces to two corridors, and the argument from the previous case finishes the pursuit.

Therefore $r=\frac l4$ is sufficient.

Case 3: $r>\dfrac l5$

Here

$\frac lr-1<4.$

Starting from $(1,1,1)$:

$(1,1,1)\to(3,0,0).$

Inspect a corridor whose lower bound is $3$:

$(3,0,0)\to(7,-3,-3).$

The first coordinate becomes $7$.

Since

$7>4>\frac lr-1,$

that corridor is impossible for the criminal. Thus one corridor is eliminated.

The remaining two-corridor pursuit proceeds exactly as before.

Hence every

$r>\frac l5$

guarantees capture.

Case 4: $r>\dfrac l7$

Here

$\frac lr-1<6.$

The same computation as above gives

$(1,1,1)\to(3,0,0)\to(7,-3,-3).$

The coordinate $7$ exceeds

$\frac lr-1,$

because $r>\frac l7$.

Therefore that corridor is eliminated. The pursuit again reduces to two corridors, where Warnicke catches the criminal by clearing one corridor and then the other.

Thus every

$r>\frac l7$

also guarantees capture.

Proof for the Two-Corridor Situation

Suppose one corridor has been eliminated and only two remain.

Warnicke chooses one of them and walks all the way to its blocked end. The trip from $O$ to the end takes time $l$. During that time the criminal can move at most $\frac l2$.

If the criminal is in the inspected corridor, he is eventually trapped at the blocked end and caught.

If the criminal is in the other corridor, he cannot move through $O$ into the inspected corridor. To do so he would have to pass within distance $r$ of Warnicke while Warnicke is traversing the corridor. Since Warnicke starts from $O$ and moves twice as fast, such a crossing is impossible without detection.

After the inspected corridor is cleared, the criminal must be in the last corridor, and Warnicke catches him there.

Conclusion

Warnicke can guarantee capture in all four cases.

For $r=\frac l3$ one inspection already produces a lower bound exceeding $l-r$.

For $r=\frac l4$ repeated inspections produce a corridor whose lower bound reaches $3r=l-r$.

For $r>\frac l5$ and for $r>\frac l7$, two successive inspections of the same corridor produce a lower bound $7r$, which exceeds $l-r$.

Once any corridor is eliminated, the problem reduces to two corridors, and Warnicke can clear them one after another, guaranteeing capture regardless of the criminal's strategy.