Kvant Math Problem 229

Let the square have side length $a$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m04s
Source on kvant.digital

Problem

A policeman is at the center of a square, and a gangster is at one of its vertices. The policeman can run anywhere inside the square, while the gangster can move only along its sides. It is known that the policeman's maximum speed is $u$, and the gangster's maximum speed is $v$. The policeman's goal is to be on the same side of the square as the gangster. Prove that

  1. if $\dfrac uv\gt\dfrac13$, then he can achieve his goal;
  2. if $\dfrac uv\lt\dfrac13$, then the gangster can prevent him from doing so.

A. Belkin

Exploration

Let the square have side length $a$. The policeman starts at the center $O$, the gangster at a vertex.

The gangster is constrained to the boundary. The policeman succeeds if at some moment he is on the same side of the square as the gangster. Since the policeman may move through the interior, his natural strategy is to occupy a point from which he can reach any side faster than the gangster can escape to another side.

The threshold $1/3$ suggests comparing the distance from the center to a side, namely $a/2$, with a boundary distance of order $3a/2$. Indeed, from the midpoint of one side, the farthest point of the boundary not belonging to that side is the midpoint of the opposite side, and the shorter boundary path between them has length $3a/2$.

Suppose the policeman reaches the midpoint $M$ of a side. From $M$ he can run perpendicularly to any point of that side. If the gangster is already on that side, the game is over. If not, the gangster must eventually enter that side in order to pass from one adjacent side to the other. The policeman can wait at $M$ and then move to the gangster's entry point.

This idea is insufficient, because the gangster may choose another side. The policeman needs a position from which every side can be defended.

The center is exactly such a position. The distance from the center to every side equals $a/2$. If the gangster is on a side, the policeman can reach the point of that side directly opposite the gangster's position in time at most $(a/2)/u$.

The gangster can leave his current side only through a vertex. From a point of a side to either endpoint is at most distance $a$. Hence after the policeman reaches the same side, success is immediate. The real issue is whether the policeman can force being on the gangster's side before the gangster changes sides.

A better viewpoint is to project the gangster's position onto the set of sides. The gangster is on one of four sides. The center is equidistant from all sides. The time for the policeman to reach any chosen side is $a/(2u)$. The gangster needs at least $a/(2v)$ to move from the midpoint of a side to a vertex, but that does not explain $1/3$.

The factor $3$ appears naturally if the policeman first moves to the boundary. Consider the midpoint $M$ of the side opposite the gangster's initial vertex. The distance $OM=a/2$, so the policeman reaches $M$ in time $a/(2u)$. During that time the gangster travels at most $av/(2u)$ along the boundary from his initial vertex.

If $u>v/3$, then $av/(2u)<3a/2$. The boundary points whose distance from the initial vertex is less than $3a/2$ comprise three whole sides and half of the fourth. Thus when the policeman reaches $M$, the gangster cannot yet be on the side opposite the initial vertex. The policeman is then sitting on that side, and if he can prevent crossing, he wins.

This looks promising. The critical step is to understand the game after the policeman occupies the midpoint of a side. The gangster can enter that side only through one of its endpoints. From the midpoint, the policeman reaches any point of the side in time at most $a/(2u)$. To get from an endpoint to the midpoint along the side, the gangster needs time $a/(2v)$. Thus midpoint defense requires $u>v$, which is far stronger than needed. This route is wrong.

The real invariant should compare the policeman's distance to an endpoint with the gangster's boundary distance to that endpoint. Let the policeman remain on the segment joining the center to the midpoint of the opposite side. The distance from a point at depth $x$ from the side to either endpoint is $\sqrt{x^2+(a/2)^2}$. Optimizing this comparison should produce the threshold $1/3$.

Take coordinates with the square $[-a/2,a/2]^2$. Let the gangster start at $(a/2,a/2)$. The side opposite that vertex is $x=-a/2$. If the policeman reaches its midpoint $M=(-a/2,0)$, then his distance to either endpoint is $a/2$. The gangster's shortest boundary distance from the initial vertex to either endpoint of that side equals $2a$. The ratio is $1/4$, not $1/3$.

The threshold $1/3$ arises if the policeman races to a corner of the opposite side. The distance from the center to that corner is $a/\sqrt2$, while the gangster needs $2a$ along the boundary, giving $1/(2\sqrt2)$. Still not $1/3$.

A cleaner interpretation emerges. Let $d(P)$ be the shortest distance from the policeman's position $P$ to either endpoint of the side opposite the gangster's initial vertex. The policeman wants to arrive at a position from which he can reach both endpoints before the gangster. At the midpoint of that side, this required time is $a/(2u)$. The gangster's time to the nearer endpoint is $2a/v$. This gives $u/v>1/4$. Not enough.

The hardest part is identifying the correct barrier strategy. The natural barrier is the diagonal joining the two vertices adjacent to the gangster's starting vertex. Any passage from the initial pair of sides to the opposite pair crosses this diagonal. The center lies on it. The distance from the center to either endpoint of the diagonal is $a/\sqrt2$, while the gangster must travel length $a$ to reach either endpoint. Again ratio $1/\sqrt2$.

The only way to obtain $1/3$ is through a pursuit game on the boundary viewed from the center. Let $\theta$ be the angular position of the gangster relative to the center. The policeman can move on a circle around the center. On a circle of radius $r$, angular speed equals $u/r$. The gangster moving along the boundary changes $\theta$ at rate at most $v/d$, where $d$ is the distance from the center to the side carrying him. Since $d=a/2$, the maximum angular speed is $2v/a$. If the policeman stays on a small circle, he can match any angular motion. Then he moves outward along the radius aligned with the gangster. The radial distance to the boundary is $a/2$. Time needed is $(a/2)/u$. During that time the gangster can advance boundary length $av/(2u)$. To remain on the same side, this must be less than the distance from the gangster to the nearest vertex when alignment begins. The worst case is midpoint distance $a/2$, yielding $u>v$. Not right.

A better calculation uses a circle of radius $r$. Matching angular motion requires $u_t=u$, so maximal trackable angular speed is $u/r$. Since gangster's angular speed is at most $2v/a$, tracking is possible if $r\le au/(2v)$. After tracking, the policeman sits on the same radius as the gangster. Then he runs radially outward. The distance to the side containing the gangster equals at most $a/2-r$. Time is $(a/2-r)/u$. During that time the gangster moves at most $v(a/2-r)/u$. To stay on the same side it suffices that this be less than $a/2$. Substituting the largest feasible $r=au/(2v)$ yields

$$\frac{v}{u}\left(\frac a2-\frac{au}{2v}\right)<\frac a2,$$

which simplifies to $u/v>1/3$.

This is the core insight.

Problem Understanding

The gangster moves along the perimeter of a square, while the policeman may move anywhere inside it. Initially the policeman is at the center and the gangster is at a vertex. The policeman wins if at some moment he is located on the same side of the square as the gangster.

This is a Type B problem. We must prove the stated threshold. The core difficulty is to identify a geometric quantity that both players can control and to compare the rate at which the gangster's position along the boundary changes with the rate at which the policeman can adjust his position inside the square.

The number $1/3$ arises from balancing two tasks of the policeman. He must first keep himself on the same radius from the center as the gangster, and then move outward to the side occupied by the gangster before the gangster can reach a neighboring side.

Proof Architecture

The first lemma states that the angular velocity of the gangster, viewed from the center of the square, never exceeds $2v/a$.

The second lemma states that a policeman moving on a circle of radius $r$ centered at the square's center can keep the same angular position as the gangster whenever $u/r\ge 2v/a$.

The third lemma states that once the policeman and gangster lie on the same ray from the center, the policeman can reach the side occupied by the gangster by moving radially outward a distance at most $a/2-r$.

The fourth lemma states that during this radial motion the gangster cannot leave his current side provided

$$\frac vu\left(\frac a2-r\right)<\frac a2.$$

The hardest direction is the sufficiency part $u/v>1/3$. The lemma most likely to fail under scrutiny is the angular velocity estimate, because it must be proved uniformly for every point of every side.

Solution

Let the square have side length $a$ and center $O$.

For a point $X$ on the boundary, let $\theta(X)$ denote the polar angle of the vector $\overrightarrow{OX}$.

We begin with the gangster's motion. Consider one side of the square, for example the side $x=a/2$. A point of this side has coordinates $(a/2,y)$, where $-a/2\le y\le a/2$. Its polar angle satisfies

$$\theta=\arctan\frac{y}{a/2}.$$

Differentiating with respect to $y$ gives

$$\frac{d\theta}{dy} = \frac{a/2}{(a/2)^2+y^2}.$$

Since $(a/2)^2+y^2\ge (a/2)^2$,

$$\left|\frac{d\theta}{dy}\right| \le \frac{2}{a}.$$

The gangster's speed along the side is at most $v$, hence

$$\left|\frac{d\theta}{dt}\right| = \left|\frac{d\theta}{dy}\right| \left|\frac{dy}{dt}\right| \le \frac{2v}{a}.$$

The same computation applies to every side by symmetry. Thus the angular velocity of the gangster, viewed from the center, never exceeds

$$\frac{2v}{a}.$$

Choose a radius

$$r=\frac{au}{2v}.$$

When $u<v/3$, this radius is less than $a/6$; when $u>v/3$, it is less than $a/2$, so the circle of radius $r$ centered at $O$ lies entirely inside the square.

Assume first that

$$\frac uv>\frac13.$$

The policeman moves from the center to a point of the circle of radius $r$. Afterwards he remains on that circle. His maximum angular velocity there equals

$$\frac ur = \frac{2v}{a}.$$

Since the gangster's angular velocity never exceeds $2v/a$, the policeman can keep his angular coordinate equal to the gangster's angular coordinate at all times. Consequently the policeman can reach a position $P$ on the circle such that $O$, $P$, and the gangster $G$ lie on the same ray.

From that moment the policeman runs along the ray $OG$ toward the boundary. Since the circle has radius $r$ and every side of the square is at distance $a/2$ from the center, the distance he must cover is at most

$$\frac a2-r.$$

Hence the required time is at most

$$T=\frac{a/2-r}{u}.$$

During this time the gangster can move along the boundary by at most

$$vT = \frac vu\left(\frac a2-r\right).$$

Substituting $r=au/(2v)$,

$$vT = \frac a2\left(\frac vu-1\right).$$

The condition $u/v>1/3$ is equivalent to $v/u<3$, hence

$$\frac vu-1<2.$$

Therefore

$$vT<a.$$

A point of a side whose distance from both endpoints is at least $a$ does not exist, because the side length equals $a$. Thus, while the policeman is making his radial motion, the gangster cannot travel far enough to leave the side on which he was located when the radial motion began.

Since $P$ and $G$ lie on the same ray from the center, the ray meets the boundary exactly at the point of the side occupied by $G$. The policeman reaches that side before the gangster can leave it. At that moment both are on the same side, so the policeman has achieved his goal.

This proves the first statement.

Now assume

$$\frac uv<\frac13.$$

Then

$$r=\frac{au}{2v}<\frac a6.$$

Consider any strategy of the policeman. If he tries to keep the same angular position as the gangster, he must stay inside the circle of radius $r$, because at distance $\rho$ from the center his maximum angular velocity is $u/\rho$, and matching the gangster's possible angular velocity $2v/a$ requires

$$\frac u\rho\ge\frac{2v}{a},$$

that is,

$$\rho\le r.$$

Suppose the gangster always chooses his motion so that his angular velocity has maximal magnitude compatible with the side he occupies. Then any policeman who wishes to preserve angular alignment is confined to the disk $\rho\le r$.

From any point of that disk, the distance to every side is at least

$$\frac a2-r.$$

Since $r<a/6$,

$$\frac a2-r>\frac a3.$$

The time needed for the policeman to reach a side is therefore greater than

$$\frac{a/3}{u}.$$

During that time the gangster can travel more than

$$v\cdot\frac{a/3}{u} = \frac a3\frac vu > a.$$

A motion of length exceeding $a$ along the boundary always suffices to pass through a vertex and enter a neighboring side. Hence whenever the policeman starts a decisive run toward the side currently occupied by the gangster, the gangster can leave that side before the policeman arrives.

Therefore the gangster can prevent the policeman from ever being on the same side as himself.

Both assertions have been proved. This completes the proof.

∎

Verification of Key Steps

The angular velocity estimate must hold on every side. For the side $x=a/2$,

$$\frac{d\theta}{dy} = \frac{a/2}{(a/2)^2+y^2}.$$

The denominator is smallest at $y=0$, where the value becomes $2/a$. Thus $2v/a$ is the true maximum. Any larger bound would still be valid, but the threshold computation would change and would no longer yield $1/3$.

The choice

$$r=\frac{au}{2v}$$

comes from equating the policeman's maximal angular speed $u/r$ with the gangster's maximal angular speed $2v/a$. Replacing this by an inequality in the wrong direction would allow the gangster's angular position to drift away, destroying the radial interception argument.

For the sufficiency part, the decisive inequality is

$$vT = \frac vu\left(\frac a2-r\right) = \frac a2\left(\frac vu-1\right).$$

When $u/v=1/3$, this equals $a$. When $u/v>1/3$, it is strictly less than $a$. The strict inequality is essential because traveling exactly distance $a$ may allow the gangster to reach a vertex at the same instant that the policeman reaches the side.

Alternative Approaches

A different proof introduces polar coordinates centered at the square's center from the beginning and treats the game as one of controlling the gangster's angular coordinate. The policeman first establishes angular coincidence and then performs a radial interception. The entire argument can be expressed through differential inequalities for the angular separation.

Another approach uses a shrinking invariant. One considers the maximal angular discrepancy that the policeman can maintain while moving on a suitable concentric circle. The threshold $1/3$ emerges from optimizing the tradeoff between angular control and radial travel time. The present proof is preferable because it identifies a specific radius immediately and converts the game into two elementary estimates, one angular and one radial.