domingo, 9 de febrero de 2020

(509) - Tomándose demasiado en serio la animación del DVD




Todos nosotros hemos visto alguna vez la típica animación del reproductor de DVDs en el que aparece un icono rebotando por la pantalla. Además, hace tiempo que está por internet el meme en el que todo el mundo espera a que el icono golpee justo en una esquina. Este meme tiene origen en un episodio de The Office emitido en 2007, pero resurgió hace un año cuando se volvió viral el siguiente vídeo.




Ahora bien, ¿tan raro es este suceso? Primero, veamos las condiciones en las que trabajamos.
  1. Esta animación siempre consiste en una figura que se mueve con un ángulo de 45º.
  2. Las dimensiones de un monitor, puesto que está compuesto de píxeles, son enteras. ($a, b \in \mathbb{Z}$)
  3. Por el mismo motivo, las coordenadas iniciales del icono, también son enteras. ($a_0, b_0 \in \mathbb{Z}$)


Primero, podemos tratar el icono como un punto sin pérdida de generalidad (este sería el centro de la figura, matemáticamente se representaría igual, pero reduciendo las dimensiones del monitor).

A la hora de afrontar este problema he encontrado conveniente representar los rebotes como una prolongación de la trayectoria del logo. Es decir, si hacemos revotar algo en una superficie plana quedaría así:

Así pues, podemos representar todos los rebotes a base de dividir el plano en rectángulos de la forma del monitor y hacer pasar una recta por estos rectángulos. Pero aún mejor sería, si fueran cuadrados, porque entonces podríamos usar las coordenadas cartesianas. Así que "comprimimos" los ejes para que cada rectángulo represente un espacio 1x1, de este modo, las esquinas del monitor serían los puntos con coordenadas enteras.

De este modo el problema ya parece más fácil de analizar. Tan solo tenemos que determinar si una recta pasa por algún punto de coordenadas enteras, siendo esa recta la ecuación de la trayectoria del icono, que sacamos conociendo un punto (usamos $\frac{b_0}{b}$ y $\frac{a_0}{a}$ porque recordemos que usamos las coordenadas "comprimidas" entre 0 y 1) y la pendiente ($\frac{a}{b}$ debido a esa transformación de los ejes):

$$y = \frac{b_0}{b} + \frac{a}{b} (x - \frac{a_0}{a})$$

Multiplicando por $b$ y reordenando:

$$by - ax = b_0 - a_0$$

Como $a,b,a_0,b_0 \in \mathbb{Z}$ podemos usar la identidad de Bezout para sacar los puntos con coordenadas enteras. En particular, la primera de ellas, que es la que nos interesa, la llamaremos $x_0, y_0 \in \mathbb{Z}$ que representarían el punto de esa cuadrícula imaginaria donde el CD impacta contra la esquina.
Por tanto, el icono chocará con una esquina $\Longleftrightarrow \gcd{(a, b)} \mid b_0 - a_0$

En el caso particular de que haya empezado en el $(0,0)$, podemos ver que es seguro que tarde o temprano impactará contra otra esquina.

Ahora, algunas otras cosas interesantes, ¿va a tardar mucho? o ¿contra qué esquina chocará?. Para esto, pongamos un ejemplo:

Supongamos que el monitor es un monitor estándar, 1920x1080, y que parte del $(0,0)$. Esta sería la representación. Las distintas soluciones enteras de la ecuación se han rodeado (la primera es $(9, 16)$):
Para ver cuántos rebotes da antes de chocarse contra el vértice basta con contar cuántas veces corta la recta la cuadrícula antes de la primera solución. Esto es $16 + 9 - 2 = 23$ rebotes, el choque con el vértice sería el número $24$.

De forma general, el número de rebotes será: $x_0 + y_0 - 2$.

Para ver en qué esquina chocará, tendremos en cuenta cuál es la orientación del monitor en cada cuadrado, según se haya invertido en vertical (amarillo), horizontal (rojo), ambas (naranja), o ninguna (azul).


Este patrón se repite por todo el plano, así que para saber en qué esquina golpeará, podemos tratar los puntos módulo 2.


$x_0 (mod 2)$
$0$ $1$
$y_0 (mod 2)$ $0$ $\swarrow$ $\searrow$
$1$ $\nwarrow$ $\nearrow$

Además, analizando las soluciones enteras de la ecuación módulo dos, es fácil darse cuenta de que en caso de que impacte contra alguna esquina, impactará con exactamente dos esquinas distintas.

Comprobando en la tabla, podemos ver que, en el caso particular de antes, impactará en la esquina inferior derecha y después volverá a impactar con la esquina inferior izquierda, de donde salió en un principio.

Como vemos, es un problema que no tiene ninguna dificultad a la hora de analizarlo, y que solo requiere un mínimo de geometría y la identidad de Bezout.

No hay comentarios:

Publicar un comentario