Problema del salto de la rana

Question

Las hojas de loto están dispuestas alrededor de un círculo.

Una rana comienza a saltar desde una hoja de la manera descrita a continuación. En el primer salto se salta una hoja, el siguiente salto se salta dos, tres el siguiente salto y así sucesivamente.

Si la rana puede alcanzar todas las hojas, demuestre que el número de hojas no puede ser impar.

Answer 1

Supongamos que hay $m$ hojas, donde $m$ es impar. Si $m=1$ la rana obviamente llega a todas las hojas, así que asumimos $m>1$ . (En cualquier caso, es de suponer que una hoja no puede estar "dispuesta alrededor de un círculo"). El número total de hojas saltó hasta el escenario $n$ es $\frac{1}{2}n(n+1)$ y la hoja a la que se llega es la $k$ desde el principio, donde $$\frac{1}{2}n(n+1)\equiv k\pmod m\ .$$ Si $k$ es impar entonces esta congruencia es equivalente a $$4n(n+1)\equiv 8k\pmod m$$ y por lo tanto a $$(2n+1)^2\equiv 8k+1\pmod m\ .$$ Supongamos que esto tiene una solución para cada $k$ . Desde $8$ y $m$ son coprimos, los valores $8k+1$ incluirá todos los residuos módulo $m$ Así que $$(2n+1)^2\equiv l\pmod m$$ tiene una solución para cada $l$ . Es decir, cada $l$ es un cuadrado módulo $m$ . Pero esto no es cierto.

Answer 2

Supongamos que hemos numerado las hojas como $a_1$ , $a_2$ , $\cdots$ en el sentido de las agujas del reloj. A esto lo llamamos nuestro $n$ -tupla. Ahora vemos el problema de la siguiente manera. Cada vez que la rana salta de $a_i$ a $a_j$ consideramos un intercambio de $a_i$ y $a_j$ . Ahora bien, como por hipótesis la rana alcanza todas las hojas, en nuestra construcción del problema esto equivale a la afirmación de que alcanzamos nuestra inicial $n$ -tupla después de esas operaciones en un número par de pasos.

Esto es fácil. Por un momento olvidemos el problema y consideremos el siguiente problema-

Para cualquier colección de $n$ objetos distintos partiendo de una permutación particular, se llega a esa permutación particular después de $k$ pasos intercambiando dos vecinos consecutivos. Demostrar que $k$ debe ser uniforme.

Una solución es considerar una biyección entre los objetos distintos y el $n$ -y decir que los números $a_i$ y $a_j$ se dice que está fuera de servicio si $\max (a_i,a_j)$ está a la izquierda del más pequeño. En ese caso, forman una inversión. Ahora demuestre que el intercambio de dos vecinos cambia la paridad del número de inversiones.

Consideremos ahora la siguiente generalización del problema anterior.

Para cualquier colección de $n$ objetos distintos partiendo de una permutación particular, se llega a esa permutación particular después de $k$ pasos. Demostrar que $k$ debe ser uniforme.

La pista para el problema anterior es observar que cualquier al azar permutación consiste en un impar número de los anteriores restringido permutaciones.

¿Has notado que al demostrar la equivalencia (en realidad la generalización del segundo problema es mucho más general) has demostrado una versión mucho más general de tu problema?