A grasshopper is sitting at an integer point in the Euclidean plane. Each second it jumps to another integer point in such a way that the jump vector is constant. A hunter that knows neither the starting point of the grasshopper nor the jump vector (but knows that the jump vector for each second is constant) wants to catch the grasshopper. Each second the hunter can choose one integer point in the plane and, if the grasshopper is there, he catches it. Can the hunter always catch the grasshopper in a finite amount of time?
Problem
Source: Balkan BMO Shortlist 2017 C1
Tags: combinatorics, Combinatorial games, game strategy, IMO Shortlist
-[]-
31.07.2019 14:54
Yes. The problem is equivalent to guessing intergers $a,b$ where the position of a grasshopper at time $t$ is $a+bt$. We can iterate all possible values of $(a,b)$ by going in the spiral way from $(0,0)$ (the same way as proving that the set of rational numbers is iterable).
RodSalgDomPort
05.10.2019 23:57
I quite didn't understand
brainiacmaniac31
06.10.2019 02:22
RodSalgDomPort wrote: I quite didn't understand Let me try to explain: Since the jump vector is constant, at time $t$, the position of the grasshopper is $(x_0+x_1t,y_0+y_1t)$. Here, $(x_0,y_0)$ is the initial starting point and $\langle x_1,y_1\rangle$ is the jump vector. Now, the problem is reduced to showing that there is an algorithm which finds all ordered quadruplets $(x_0,x_1,y_0,y_1)\in\mathbb{Z}^4$.[quote=-[]-]Yes. The problem is equivalent to guessing intergers $a,b$ where the position of a grasshopper at time $t$ is $a+bt$. We can iterate all possible values of $(a,b)$ by going in the spiral way from $(0,0)$ (the same way as proving that the set of rational numbers is iterable).[/quote] This is on the Euclidean plane, so the position cannot be one-dimensional.