# trap frogs0518

a frog jumps around on the number ray and you try to catch it. jumping and catching always alternate. the frog starts at position $$s \in \mathbb{Z}$$ and at every move it jumps a distance of $$z \in \mathbb{Z}$$ (if $$z>0$$, it jumps to the right, others if to the left). $$z\ ) is the same at every jump. catching consists of giving an integer position. you don't know \(z\ ) or \(s\ ). we show that there is a way to always catch the frog. First, \(a_1 = s$$ and $$a_{n+1} = a_n + z = s + n \cdot z$$ with $$s,z \in \mathbb{Z}$$.

We now choose

$$h:\mathbb{N} \to \mathbb{Z}^2: h(2^k r) = \left ( (-1)^{k+1} \left \lfloor \frac{k+1}{2} \right \rfloor, (-1)^{\frac{r+1}{2}} \left \lfloor \frac{r+1}{4} \right \rfloor \right )$$

as the function that assigns (exactly) a number tuple of whole numbers to every natural number. The choice of this function is through the functions $$f(n) = (-1)^n \left \lfloor \frac{n}{2} \right \rfloor$$ , the $$\mathbb{N}$$ on $$\mathbb{Z}$$ and $$g(2^kr) = (k+1, \frac{r+1}{2})$$ , which $$\mathbb{N}$$ on $$\mathbb{N}^2$$ map bijectively, motivated.

We now show the surjectivity of $$h$$ ( $$h$$ is also injective, but we do not need this property).

Let $$(x,y) = (2^{k_1} r_1, 2^{k_2} r_2) \in\mathbb{Z}^2$$ . But then

$$h \left ( 2^{2 \cdot 2^{k_1} r_1 - 1} \cdot (4 \cdot 2^{k_2} r_2 - 1) \right ) = (2^{k_1} r_1, 2^{k_2} r_2) = (x,y).$$

Hence: $$\forall (s,z) \in \mathbb{Z}^2 \, \exists \, m \in \mathbb{N}$$ with $$h(m) = (x_m,y_m) = (s, z)$$ .

If, for example, the move is at $$n = 88$$, we calculate $$h(88)=(2,3)$$ and choose $$2 + 88 \cdot 3 = 266$$ as the position.

Then after exactly $$m$$ moves with $$x_m + m \cdot y_m = s + m \cdot z = a_m$$ the choice falls on the frog.

Besides $$h$$, many other functions are possible, such as the Cantorian pairing function or a bijective spiral.

A simple implementation in JavaScript follows:

See the Pen catch the frog by David Vielhuber (@vielhuber) on CodePen.

Back