Kvant Math Problem 572

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 2m26s
Source on kvant.digital

Problem

A kangaroo jumps in the corner $x\ge0$, $y\ge0$ of the coordinate plane $Oxy$ as follows: from point $(x;y)$ the kangaroo can jump to point $(x+1;y-1)$ or to point $(x-5;y+7)$, and it is not allowed to jump to points in which one of the coordinates is negative. From which initial points $(x;y)$ can the kangaroo not reach a point located at a distance greater than 1000 from the origin? Draw the set of all such points $(x;y)$ and find its area.

A. G. Kushnirenko, A. B. Sosinsky

All-Union Mathematical Olympiad for School Students (1979, 8th grade)

Exploration

The kangaroo moves in the integer lattice of the first quadrant with vectors $v_1=(1,-1)$ and $v_2=(-5,7)$, always staying in $x\ge 0$, $y\ge 0$. The question asks for which initial points the reachable set never leaves the disk of radius $1000$.

A natural approach is to understand whether there is an invariant or a monotone quantity controlling escape to infinity. A linear functional is the most promising candidate because both moves are linear.

Compute the effect of a general linear form $L=ax+by$ under the moves:

$$\Delta_1 = a-b, \qquad \Delta_2 = -5a+7b.$$

Choosing $a=7$, $b=5$ gives

$$\Delta_1 = 2, \qquad \Delta_2 = 0.$$

So $L=7x+5y$ never decreases along any allowed move and strictly increases under $v_1$.

Thus boundedness of $L$ is equivalent to boundedness of all reachable positions.

The only way to fail escaping is if the process cannot keep producing $v_1$ moves indefinitely. The obstruction occurs only when $y=0$ (so $v_1$ is forbidden) and simultaneously $x<5$ (so $v_2$ is forbidden). This suggests a small terminal set.

We test whether any other region can avoid eventually reaching a configuration where both moves become usable in alternation, which would allow unbounded growth of $L$.

This points toward a finite exceptional set near the boundary.

Problem Understanding

This is a Type A problem. We must determine all initial lattice points $(x,y)$ in the first quadrant from which the kangaroo can never reach any point whose Euclidean distance exceeds $1000$.

The key issue is whether the move system allows unbounded escape; if it does, then every sufficiently non-degenerate initial position permits reaching arbitrarily large $7x+5y$, hence arbitrarily large radius.

The expected outcome is a small finite set of “trapped” starting points from which no motion or no growth is possible.

Proof Architecture

The first lemma identifies a linear functional $L=7x+5y$ that is monotone nondecreasing under both moves.

The second lemma proves that if a position allows both moves to be used infinitely often in a controlled alternation, then $L$ is unbounded along reachable states.

The third lemma characterizes precisely the terminal configurations where no move is possible.

The fourth lemma shows that every initial point outside this terminal set eventually reaches a configuration enabling unbounded growth of $L$, hence eventually reaching distance exceeding $1000$.

The most delicate part is proving that no other “hidden trap” cycles exist that keep $L$ bounded while allowing movement; this is resolved by analyzing when each move is disabled and showing that such situations force immediate transition into a region where both moves become available.

Solution

Consider the linear function

$$L(x,y)=7x+5y.$$

Under the move $(x,y)\mapsto(x+1,y-1)$,

$$L(x+1,y-1)=7(x+1)+5(y-1)=7x+5y+2,$$

and under the move $(x,y)\mapsto(x-5,y+7)$,

$$L(x-5,y+7)=7(x-5)+5(y+7)=7x+5y.$$

Hence every allowed move satisfies $L_{\text{new}}\ge L_{\text{old}}$, with strict increase under the first move.

Suppose a position satisfies $x\ge 5$ and $y\ge 1$. Then both moves are available. From such a position, applying $(x-5,y+7)$ preserves $L$ while increasing $y$, and repeated application eventually produces a position with $y\ge 1$ and still $x\ge 5$, allowing the move $(x+1,y-1)$, which increases $L$ by $2$. By alternating these two moves, one constructs arbitrarily large values of $L$.

Since

$$7x+5y \le 7\sqrt{x^2+y^2}+5\sqrt{x^2+y^2}=12\sqrt{x^2+y^2},$$

we obtain

$$\sqrt{x^2+y^2}\ge \frac{L(x,y)}{12}.$$

Thus unboundedness of $L$ implies unbounded Euclidean distance.

Therefore, any initial position from which one can reach a configuration with $x\ge 5$ and $y\ge 1$ is capable of reaching points of arbitrarily large distance.

We determine when such growth is impossible. The only situation where no move is available is when $y=0$ and $x<5$, since $(x+1,y-1)$ is forbidden by negativity of $y$, and $(x-5,y+7)$ is forbidden by negativity of $x$. These are exactly the five points

$$(0,0),(1,0),(2,0),(3,0),(4,0).$$

If the initial point lies outside this set, then either $y\ge 1$ or $x\ge 5$. If $y\ge 1$, then the first move is allowed, increasing $x$; repeated use ensures that either $x$ reaches $5$ or $y$ returns to $0$ while $x$ has increased, in which case $x\ge 5$ is eventually achieved after finitely many steps. If $x\ge 5$, then the second move is allowed and increases $y$; repeating it produces a configuration with $y\ge 1$ while preserving $x\ge 5$. Hence every nonterminal starting position eventually reaches a state with both coordinates enabling alternation of moves, and thus yields unbounded growth of $L$.

Consequently, from every initial point not in the set ${(x,0)\mid x=0,1,2,3,4}$ the kangaroo can reach points of arbitrarily large distance, in particular exceeding $1000$. From these five points no move is possible, so no point at any positive distance is reachable.

The required set is

$$\boxed{{(0,0),(1,0),(2,0),(3,0),(4,0)}}.$$

The area of this set, being finite and consisting of isolated points, equals $0$.

Verification of Key Steps

The critical point is the claim that $L=7x+5y$ allows unbounded growth whenever the process is not trapped. This relies on producing a state where both moves can be used in alternation. Starting from any state with $x\ge 5$, the move $(x-5,y+7)$ preserves $L$ and increases $y$ without losing feasibility, guaranteeing eventual access to $y\ge 1$ while retaining $x\ge 5$. Once both inequalities hold, $(x+1,y-1)$ is always admissible and strictly increases $L$, and $(x-5,y+7)$ restores the ability to apply it after $y$ drops.

The second delicate point is the identification of terminal states. When $y=0$ and $x<5$, both moves are forbidden by definition: the first violates nonnegativity of $y$, the second violates nonnegativity of $x$. Any other boundary configuration allows at least one move, which immediately exits the boundary or increases one coordinate, preventing permanent confinement.

Alternative Approaches

One can also analyze the problem via the semigroup generated by the two move vectors and its action restricted by the first quadrant constraint. In that viewpoint, the only absorbing class corresponds to the finite set of points where the semigroup action is blocked entirely. Another approach is to study the directed graph on lattice points induced by the moves and classify its finite sinks; this yields the same five-point trap set but requires more combinatorial bookkeeping than the linear functional method used above.