Problema del juego de cuadrícula 2x2

Question

Un amigo mío está intentando hacer una página web que tenga un juego para una cuadrícula de 2x2 que sea similar al antiguo juego Norte, Sur, Este, Oeste. No puedo por la vida de mí entender esto.

Esencialmente, el juego haría esto. Un jugador comienza en la coordenada (0,0) y se mueve por la cuadrícula. Esta coordenada de la cuadrícula sería blanca mientras que el resto son negras. Aquí hay un diagrama:

$$ \begin{align} &WB \\ &BB \end{align} $$

Una vez que el jugador se mueve, las cosas cambian. Cuando un jugador se mueve de una casilla, esa casilla se vuelve amarilla. Aquí hay un nuevo diagrama para ilustrar esto (moverse de (0,0) a (0,1)):

$$ \begin{align} &YW \\ &BB \end{align} $$

Una vez que un jugador descubre una casilla, ésta no puede volver a ser negra. Además, la coordenada (0,0) nunca puede ser negra (ya que el jugador comienza allí). Sólo puede haber un cuadrado blanco en cualquier momento.

Mi amigo (y ahora yo) quiere saber el número de permutaciones/combinaciones de resultados de los colores de los cuadrados. Lo he intentado, pero no consigo entender cómo funcionaría esto. Lo mejor que se me ocurrió fue:

$$ \begin{align} &4^2-1 = 15 \end{align} $$

Lo deduje del hecho de que cada caja sólo puede ser de uno de dos colores en un momento dado y la primera caja no puede ser de uno de esos colores (negro). ¿Hay una forma mejor de enfocar esto? ¿Hay una forma más general que funcione para cuadrículas de diferentes tamaños (3x3, 4x4, etc)?

Answer 1

Si he entendido las reglas de su juego, la configuración del tablero, depende de los movimientos particulares que haga el jugador. Voy a numerar las casillas así:

$$\begin{align} &12 \\ &34 \end{align}$$

Los siguientes caminos dan lugar a diferentes configuraciones de color de la placa: 1, 12, 13, 121, 124, 131, 134, 1213, 1242, 1312, 1343. Esto hace que $11$ . Estos caminos no cubren todo el tablero, es decir, quedan casillas negras.

Si pasas por todas las casillas, todas son amarillas, excepto una que es blanca. Hay $4$ posibilidades para el cuadrado que es blanco. Así que hay $15$ posibilidades.

He asumido que los movimientos diagonales no están permitidos.

Para un $n\times n$ tablero, el problema parece muy difícil, porque los cuadrados amarillos deben formar un conjunto conectado. No sé cómo contar los conjuntos conectados en un tablero.

Answer 2

Me sale

$$1+3\cdot2+3\cdot3+4=20$$

diferentes disposiciones de color B/Y/W. Es decir, sólo hay 1 disposición con tres B (es decir, la disposición inicial), $3\cdot2=6$ con dos B, una Y y una W (es decir, se elige una de las $3$ B para moverte a la primera, pero después puedes volver a la esquina superior izquierda, pasando de Y a W), $3\cdot3=9$ con una B, dos Y y una W, y 4 sin B, tres Y y una W.

Nota, esta respuesta depende de que el jugador pueda moverse a cualquier casilla en cualquier turno. Si ese es el caso, entonces la generalización a cualquier matriz con un total de $N$ cuadrados, con uno designado a partir de W y el resto B, viene dado por

$$\sum_{k=0}^{N-1}{N-1\choose k}(k+1)$$