Cono Sur 2019 - Problema 5

Problemas que aparecen en el Archivo de Enunciados.
Sandy

OFO - Medalla de Bronce
Mensajes: 50
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 1
Nivel: 2

Cono Sur 2019 - Problema 5

Mensaje sin leer por Sandy » Sab 31 Ago, 2019 9:21 pm

Sea $n≥3$ un entero positivo. En cada casilla de un tablero de $n\times n$ se debe escribir $1$ ó $2$ de tal modo que la suma de todos los números escritos en cada subtablero de $2\times 3$ y $3\times 2$ sea par. ¿De cuántas maneras distintas se puede llenar el tablero?

BrunZo

OFO - Medalla de Bronce FOFO 8 años - Mención Especial OFO - Medalla de Plata FOFO Pascua 2019 - Medalla
Mensajes: 143
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 4
Nivel: 1

Re: Cono Sur 2019 - Problema 5

Mensaje sin leer por BrunZo » Dom 01 Sep, 2019 3:54 pm

Solución:
Spoiler: mostrar
Digamos que $f(n)$ es la cantidad de formas de llenar un tablero de $n\times n$ de esta forma. Vamos a separar el problema en partes:

Parte primera: $f(3)=32$
Spoiler: mostrar
Tomemos el $3\times 2$ superior. Es claro que hay $2^5=32$ formas de completar cinco de sus casilleros, y el sexto está determinado por paridad. Ahora, si tomamos el $3\times 2$ inferior, y los dos $2\times 3$, obtenemos que si $A$, $B$ y $C$ son los números en la fila interior:
$A+B+C\equiv x$, $A+B\equiv y$ y $B+C\equiv z$ están determinados por paridad
De modo que la única y válida forma posible de completarlo es $A\equiv x-z$, $B\equiv y+z-x$, $C\equiv x-y$.
Esto significa, que para cada una de las $32$ configuraciones de esos cinco casilleros, hay una y sólo una forma de completar el $3\times 3$, es decir, $f(3)=32$
Parte segunda: $f(n)=f(3)=32$
Spoiler: mostrar
Es claro que hay exactamente $32$ formas de completar el $3\times 3$ superior izquierdo del tablero.
Notemos que el mismo argumento de unicidad de la primera parte funciona para el $3\times 3$ formado por las columnas segunda, tercera y cuarta, en las primeras tres filas. Esto es, las tres casillas superiores de la cuarta columna están determinadas por paridad, a partir de las primeras tres columnas.
Así siguiendo por todas las columnas, todas las casillas en las primeras tres filas están determinadas por un $3\times 3$ (de hecho, es como continuar el tablero periódicamente).
Ahora, aplicando el razonamiento en vertical, todas las casillas en las primeras tres columnas ahora están determinadas, y lo mismo se puede obtener para el resto de columnas.
Todo esto significa, que un $n\times n$ está determinado por su $3\times 3$ superior, o sea, $f(n)=f(3)=32$.

Responder