Entrenamiento Cono 2018 P17

Problemas que aparecen en el Archivo de Enunciados.
Matías

OFO - Medalla de Bronce-OFO 2016 OFO - Medalla de Bronce-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años
OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 204
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 8
Nivel: 3

Entrenamiento Cono 2018 P17

Mensaje sin leer por Matías » Sab 11 Ago, 2018 3:01 pm

A un tablero se lo denomina guayaco si puede ser cubierto totalmente con fichas como se muestra en la figura, sin superposiciones ni fichas que sobresalgan del tablero.
Determinar todos los valores de $n$ para los cuales el tablero de dimensión $n\times (n+1)$ es guayaco.
\begin{array}{|c|c|c|c|c|} \hline \times & \times & \times & \times & \times \\ \hline \times & & & & \\ \hline \times & & \times & \times & \\ \hline \times & & & \times & \\ \hline \times & \times & \times & \times & \\ \hline \end{array}

Avatar de Usuario
¿hola?

OFO - Mención-OFO 2016 OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Plata-OFO 2019 OFO - Medalla de Oro-OFO 2020
COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 149
Registrado: Vie 01 Ene, 2016 1:12 am
Medallas: 6
Nivel: 3
Contactar:

Re: Entrenamiento Cono 2018 P17

Mensaje sin leer por ¿hola? » Vie 25 Sep, 2020 3:00 pm

Spoiler: mostrar
Primero, con dos de esa cosa fea se puede formar una pieza $5\times 6$, y si una cosa fea esta en el tablero, es formando una pieza $5\times 6$ con otra cosa fea. Por lo anterior, el problema es equivalente a ver que tableros $n\times (n+1)$ se pueden llenar con piezas $5\times 6$. Este nuevo problema se puede resolver mirando esto para obtener que o bien $n≡0$ modulo $5$ o $6$ y $n≡-1$ modulo $6$ o $5$ respectivamente, o bien, $n≡0$ o $n≡-1$ modulo $30$ y $n$ o $n+1$, respectivamente, se pueden escribir de la forma $a5+b6$ con $a$ y $b$ enteros no negativos. De las primeras soluciones obtenemos $n≡5$ o $n≡24$ modulo $30$ y de las segundas obtenemos $n≡0$ o $n≡29$ modulo $30$ exceptuando cuando $n$ o $n+1$, respectivamente, no son de la forma $a5+b6$ con $a$ y $b$ enteros no negativos, y como $5$ y $6$ son coprimos, por el teorema de Chicken McNuggets tenemos que el numero mas grande que cumple esto es $19$ y como $19<29$ jamás ocurrirá que $n$ o $n+1$ no son de la forma $a5+b6$ ya que $n\geq 29$.

Finalmente todos los tableros guayacos de $n\times (n+1)$ son los que $n$ es congruente con $0,5,24,29$ modulo $30$.
1  
Yes, he who

Responder