Problema 3 Cono Sur 2017

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
ésta

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2017 OFO - Jurado-OFO 2018
Mensajes: 300
Registrado: Sab 16 Oct, 2010 4:55 pm
Medallas: 4
Nivel: Ñandú

Problema 3 Cono Sur 2017

Mensaje sin leer por ésta »

Sea [math] un entero positivo. Se tiene un tablero cuadriculado de [math] dividido en casillas de [math], y [math] piezas como la que se muestra en la figura. Determinar de cuántas maneras se puede cubrir totalmente el tablero con estas piezas.
Ttetra - Copy.png
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
Imagen
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Problema 3 Cono Sur 2017

Mensaje sin leer por Gianni De Rico »

Que buen problema
♪♫ do re mi función lineal ♪♫
Avatar de Usuario
Emerson Soriano

OFO - Mención-OFO 2015 OFO - Medalla de Oro-OFO 2016 OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Mención-OFO 2020
OFO - Medalla de Plata-OFO 2022
Mensajes: 826
Registrado: Mié 23 Jul, 2014 10:39 am
Medallas: 6

Re: Problema 3 Cono Sur 2017

Mensaje sin leer por Emerson Soriano »

Respuesta.
Spoiler: mostrar
[math]
Más tarde subo la solución.
sebach

Colaborador-Varias OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Bronce-OFO 2020 OFO - Medalla de Plata-OFO 2021
OFO - Medalla de Plata-OFO 2022 OFO - Medalla de Plata-OFO 2023 OFO - Medalla de Oro-OFO 2024
Mensajes: 202
Registrado: Dom 06 Mar, 2011 11:49 am
Medallas: 8
Nivel: Exolímpico

Re: Problema 3 Cono Sur 2017

Mensaje sin leer por sebach »

Spoiler: mostrar
Tenemos el tablero vacío:
0000000...
0000000...
0000000...
0000000...
Llamo [math] a la cantidad de formas de llenar un tablero de ancho [math]. Voy a hacer una recursión.

Sea la casilla [math] la casilla de la columna [math] empezando desde la izquierda, y la fila [math] empezando desde abajo. Veamos que hay dos maneras de ubicar una ficha de modo que cubra la casilla [math].

La primera:

0000000
0000000
0100000
1110000

Luego, la casilla [math] podemos llenarla de una sola manera:

2000000
2200000
2100000
1110000

Lo mismo pasa ahora con la [math], estamos obligados a llenarla así:

2333000
2230000
2100000
1110000

Ahora, la casilla [math] se puede cubrir en principio de tres formas:


2333000
2234000
2144000 ====> Si tenemos calculada T(n-1), sumamos a T(n) ese valor ya que acá cubrimos el cuadrado de 4x4.
1114000


2333000
2234000
2144400
1110000 ==> Acá no podemos cubrir la casilla [math], entonces no es una configuración válida.


2333000 ----------------------------------------------------------------------------------------------> 23335777
2230000 -------------------------------------------------------------------------------------------- -> 22355570
2144400 ====> Sólo podemos cubrir la casilla [math] y la casilla [math] así: 21444600
1114000 ----------------------------------------------------------------------------------------------> 11146660

Y ahora nuevamente, podemos o "cerrar" el rectángulo de [math], donde a [math] se le suma [math], o no. Si no lo cerramos, tendremos una situación como cuando podíamos cerrar o no el cuadrado de [math], ya que se ve que una de las opciones no es válida para seguir, y la otra nos deja una "L" invertida arriba, y una casilla suelta abajo (como luego de agregar la ficha número [math] en este caso.

Luego tenemos que cubriendo la casilla [math] como mencionamos en este caso, a [math] se le suma [math],
donde [math] ya que al completar el tablero, esa forma en la que lo completamos suma [math] a [math].


La otra manera de completar la casilla [math] es así:

0000000
1000000
1100000
1000000

Si hacemos el procedimiento como antes, viendo al principio que las casillas [math] y [math] tiene una sola forma de completarse, llegaremos a la misma fórmula que antes (1). Por lo que se obtiene que:

[math].

Vemos por ejemplo que [math], ya que son las dos formas que concuerdan con "cerrar" los cuadrados de [math] según los dos casos de cómo cubrir a la casilla [math]. Esto coincide con la fórmula.
A partir de ahí, vemos que [math], [math], [math], y podemos ver que hasta ahora, agrandar en [math] a [math] nos da el triple de soluciones.

Entonces intentemos demostrar que [math] para [math]. Esto podemos verlo rápidamente viendo que:

[math]
[math]

Luego, [math], ya que se cancelan todos los demás términos.

Entonces, como [math], vimos que la manera de llenar un tablero de ancho [math] es [math] para todo [math] entero positivo.
Responder