Los seguidores de Manolo

Tetris

In Álgebra Lineal on Lunes 13, julio, 2009 at 12:06 pm

por Pablo Lessa

Definimos el siguiente producto de matrices:

(AB)_{i,j} = \max\{a_{i,k}+b_{k,j}\}

El producto consiste en hacer el producto usual pero cambiando las multiplicaciones por sumas y las sumas por máximos.

Por ejemplo:

\left(\begin{array}{cc}2&2\\1 &1\end{array}\right)\otimes \left(\begin{array}{cc}2&1\\2 &1\end{array}\right)= \left(\begin{array}{cc}\max\{2+2, 2+2\}&\max\{2+1,2+1\}\\\max\{1+2,1+2\} &\max\{1+1,1+1\}\end{array}\right)= \left(\begin{array}{cc}4&3\\3 &2\end{array}\right)

Ahora suponete que tenes una fichita de tetris, que por simplicidad suponemos ocupa solo 2 columnas.  Asociale una matriz de dos por dos que en el lugar i,j tiene la diferencia de altura entre el lugar más alto de la columna i y el lugar más bajo de la columna j.

Por ejemplo:

\begin{array}{cc}*&\\ * &*\\&*\end{array} \mapsto \left(\begin{array}{cc}2&3\\1&2\end{array}\right)

mientras que

\begin{array}{cc}&*\\ * &*\\&*\end{array} \mapsto \left(\begin{array}{cc}1&2\\2&3\end{array}\right)

Multiplicando con el producto raro ambas matrices obtenemos:

\left(\begin{array}{cc}2&3\\1&2\end{array}\right)\otimes \left(\begin{array}{cc}1&2\\2&3\end{array}\right) = \left(\begin{array}{cc}5&6\\4&5\end{array}\right)

que es exactamente la matriz asociada a apilar ambas fichas:

\begin{array}{cc}*&\\ * &*\\&*\\&*\\ *&*\\&*\end{array}\mapsto \left(\begin{array}{cc}5&6\\4&5\end{array}\right)

Algunos datos culturales y un problema:

  • A la estructura \mathbb{R} con \max en lugar de suma y + en lugar de producto se le llama el semi anillo “max-plus”  (la “suma” no tiene opuestos).
  • El álgebra lineal sobre esta porquería se llama “tropical” supuestamente porque un brasilero fué de los primeros en probar algún teorema al respecto.
  • Un problema abierto consiste en calcular el “exponente de lyapunov” de un conjunto de “matrices de tetris” al azar.  Es decir, cual es el ritmo esperado de crecimiento de la altura de la pila, si las fichas se eligen al azar con cierta distribución (y se dejan caer derechito nomás).

Pensando en las dos fichas que usamos como ejemplo más arriba.  Supongamos que se elige de manera independiente una o la otra con la misma probabilidad y se van apilando.

Es obvio que al caer la ficha:

\begin{array}{cc}*&\\ * &*\\&*\end{array}

por lo menos se le suma 2 a la altura de cada columna (se le sumaría exáctamente eso a cada columna si las dos mitades de la ficha estuvieran “despegadas”).

En caso de caer la ficha:

\begin{array}{cc}&*\\ *&*\\&*\end{array}

se le suma por lo menos 1 a la primer columna y por lo menos 3 a la segunda.

Por lo tanto una cota inferior para el ritmo de crecimiento de la primer columna es (2+1)/2 = 1.5, mientras que para la segunda columna es (2+3)/2 = 2.5.

Hice un programita para simular esto y resulta que luego de tirar 100 fichas, la altura de la pila me da siempre cerca de 250.

Esto sugiere que el exponente de Lyapunov quizás sea el máximo de lo que da cada columna en el caso “desligado”.

Tiene sentido porque la diferencia de alturas entre las columnas nunca va ser mucha (si hay una ficha que ocupe todas las columnas claro está).

En fin, queda por esa.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: