Problemas - Combinatoria

Sea $n$ un entero positivo impar. Un $laberinto \ de \ espejos$ es un tablero de $n \times n$ casillas, con paredes de cristal, donde en cada casilla se coloca un espejo de doble cara en una de las dos diagonales posibles. Dado un laberinto de espejos, apuntamos un láser a una de sus paredes exteriores y el láser entra horizontalmente o verticalmente al laberinto. Si el láser choca con un espejo, siempre choca en el punto medio y se refleja $90^\circ$ según la orientación del espejo.

A Lalo le regalaron una red mágica, como la que se muestra en la figura. La red consta de 20 vértices unidos por algunas aristas. Lalo coloca, de una en una, hormigas en los vértices de la red. Las hormigas caminan sobre las aristas, y al hacerlo, la arista recorrida va desapareciendo. Lalo tiene $n$ hormigas y juega colocándolas de la siguiente manera:

Una cuadrícula con lados de longitudes $(2^n - 1)$ y $(2^n + 1)$ se quiere dividir en rectángulos ajenos con lados sobre líneas de la cuadrícula y con un número de cuadraditos de $1 \times 1$ dentro del rectángulo igual a una potencia de $2$.

Encuentra la menor cantidad de rectángulos en los que se puede dividir la cuadrícula.

Nota: El $1$ es considerado una potencia de $2$ pues $2^0 = 1$.

Sam y Hugo juegan con $n$ monedas, todas con $A$ en una cara y $S$ en la otra. Las monedas están puestas en fila sobre la mesa. Sam y Hugo se turnan. En su turno, Sam puede voltear una o más monedas, siempre que no voltee dos adyacentes; mientras Hugo elige exactamente dos monedas adyacentes y las voltea. Al comenzar el juego, todas las monedas muestran $A$. Sam juega primero y gana si todas las monedas muestran $S$ simultáneamente en cualquier momento. Halla todos los $n\geq 1$ con los que Hugo puede evitar que Sam gane.