Página 1 de 1

Nacional 1998 - N3 P3

Publicado: Mar 19 Nov, 2019 7:43 pm
por BrunZo
Dados dos enteros $m\geq 2$ y $n\geq 2$ consideramos dos tipos de sucesiones de longitud $m\cdot n$ formadas exclusivamente por $0$ y $1$:
Las sucesiones de TIPO 1 son todas las que verifican las siguientes dos condiciones:
  • $a_ka_{k+m} = 0$ para todo $k = 1, 2, 3, ...$
  • Si $a_ka_{k+1} = 1$, entonces $k$ es un múltiplo de $m$.
Las sucesiones de TIPO 2 son todas las que verifican las siguientes dos condiciones:
  • $a_ka_{k+n} = 0$ para todo $k = 1, 2, 3, ...$
  • Si $a_ka_{k+1} = 1$, entonces $k$ es un múltiplo de $n$.
Demostrar que la cantidad de sucesiones del tipo 1 es igual a la cantidad de sucesiones del tipo 2.

Re: Nacional 1998 - N3 P3

Publicado: Mié 20 Nov, 2019 2:05 am
por Ivan
Spoiler: mostrar
Sea $T$ un tablero de $n \times m$ que tiene en cada casilla un número que puede ser $0$ o $1$. Decimos que $T$ es bueno si para cada par de casillas que comparten un lado el producto de los números de estas casillas es $0$.

Las sucesiones de Tipo 1 se pueden poner en biyección con los tableros buenos de $n \times m$: dada una sucesión podemos escribirla en el tablero llenando primero la fila 1, después la fila 2 y así sucesivamente (de izquierda a derecha). Queda de ejercicio verificar que esto es una biyección :oops:

Las sucesiones de Tipo 2 se pueden poner en biyección con los tableros buenos de $n \times m$: dada una sucesión podemos escribirla en el tablero llenando primero la columna 1, después la columna 2 y así sucesivamente (de arriba a abajo). Queda de ejercicio verificar que esto es una biyección :oops: