Olimpiadas de Matemáticas
Página de preparación y problemas

Solución. La condición que nos da el enunciado nos dice que la pulga puede cambiar su velocidad en cada paso a lo sumo en una unidad, entendiendo la velocidad (con signo) como la diferencia entre una posición y la siguiente.

Para cada natural $n\in\mathbb{N}$, sea $P(n)$ el número mínimo de pasos necesarios para llegar a un número mayor o igual que $n$ con velocidad $0$. Está claro que para pasar dos veces por el número $n$ se tiene que llegar previamente a un número mayor que $n$ con velocidad $0$, luego será suficiente demostrar que $P(n)\geq \lceil 2\sqrt{n}\rceil$ (la función techo $\lceil x\rceil$ es una forma de escribir el menor entero positivo mayor o igual que un número real $x$). Vamos a probar que, de hecho, $P(n)=\lceil 2\sqrt{n}\rceil$ para todo $n\in\mathbb{N}$.

• $P(n)$ es creciente ya que si podemos llegar con $P(n)$ pasos a un número mayor que $n$ con velocidad $0$, entonces el mismo camino nos permite hacer lo mismo para todo $m\lt n$. Esto quiere decir que si $m\lt n$, entonces $P(m)\leq P(n)$.
• $P(a^2)=2a$ para todo $a\in\mathbb{N}$. Esto es porque para llegar al punto $a^2$ con velocidad $0$, la ruta óptima es acelerar de la velocidad inicial $1$ a velocidad $a$ y luego decelerar hasta velocidad $0$ (en otras palabras, esta es la sucesión de $2a$ pasos que nos permite llegar más lejos del origen acabando con velocidad $0$). Observamos que, efectivamente, esta suma de $2a$ pasos nos da $a^2$: \[1+2+\ldots+a+(a-1)+(a-2)+\ldots+1+0=a^2.\]
• $P(a^2+a)=2a+1$ para todo $a\in\mathbb{N}$. En efecto, tenemos que $P(n)\geq P(a^2)=2a$ por monotonía y no puede ser $P(n)=2a$ ya que el punto más lejano que se puede alcanzar con $2a$ pasos acabando con velocidad $0$ es $a^2$. No obstante, una forma de alcanzar $a^2+a$ con $2a+1$ pasos es acelerar de velocidad $1$ a $a$, luego repetir velocidad $a$ y después decelerar hasta $0$: \[1+2+\ldots+a+a+(a-1)+(a-2)+\ldots+1+0=a^2+a.\] Por tanto, $a^2+a$ es el punto más lejano que se puede alcanzar con $2a+1$ pasos y acabar con velocidad $0$.

Lo anterior puede resumirse como que \[P(n)=\begin{cases}2a+1&\text{si }a^2\lt n\leq a^2+a,\\2a+2&\text{si }a^2+a\lt n\leq (a+1)^2.\end{cases}\] Dicho de otra forma, \[P(n)=\begin{cases}2a+1&\text{si }2a\lt 2\sqrt{n}\leq 2\sqrt{a^2+a},\\2a+2&\text{si }2\sqrt{a^2+a}\lt 2\sqrt{n}\leq 2a+2.\end{cases}\] Es inmediato entonces que $P(n)=\lceil 2\sqrt{n}\rceil$ para todo $n\in\mathbb{N}$, lo que concluye la demostración.