Prueba de que un tablero de ajedrez de $ 2^n \times 2^n $ con un cuadrado faltante puede ser cubierto por fichas en forma de L - Paso faltante

Question

Entiendo la solución recursiva para cubrir un tablero de ajedrez de $2^n. 2^n$ con una casilla faltante utilizando fichas en forma de L como estas:

utilizando el siguiente método para dividir el problema original en subproblemas:

Sin embargo, la prueba depende del hecho de que un tablero de ajedrez conteniendo $2^n . 2^n - 1$ casillas puede ser cubierto por las fichas en forma de L. Mientras puedo ver que el número de casillas en dicho tablero defectuoso es un múltiplo de $3$, no puedo entender por qué es necesario que todas estas casillas puedan ser cubiertas por las fichas en forma de L, independientemente de la posición de la casilla faltante.

¿Alguien podría por favor ayudarme a entender por qué es el caso?

Answer 1

Este es una prueba inductiva. Los casos base son $n = 0$ que es la primera imagen y $n = 1$ que son las próximas tres imágenes (el caso donde falta la ficha en la esquina inferior derecha está ausente - ah, bueno). La clave para el paso $n \to n + 1$ es la última imagen, pero eso puede formalizarse.

En particular, el caso $n + 1$ se puede reducir al caso $n$ dividiendo el tablero en cuatro cuadrantes y colocando una sola ficha en forma de L en la ubicación mostrada para eliminar un cuadrado de esos tres cuadrantes que aún no tienen un cuadrado.

Luego, cada uno de los cuatro cuadrantes puede ser cubierto usando la hipótesis inductiva.