CIMA - Problema 2 (Competencia Interuniversitaria)

Para discutir problemas de competencias para graduados de secundaria (Número de Oro, CIMA/Paenza, etcétera) y problemas que requieran conocimientos avanzados.
sebach

Colaborador OFO - Medalla de Bronce
Mensajes: 136
Registrado: Dom 06 Mar, 2011 11:49 am
Medallas: 3
Nivel: Exolímpico

CIMA - Problema 2 (Competencia Interuniversitaria)

Mensaje sin leer por sebach » Jue 21 Jun, 2018 7:44 pm

En la casilla inferior izquierda de un tablero cuadriculado infinito como el de la figura, se escribe el número $0$. A partir de ello, de izquierda a derecha y de abajo hacia arriba, en cada una de las demás casillas se escribe el menor entero no negativo que no aparezca a la izquierda (en la misma fila) ni debajo (en la misma columna). Determinar cuál es el número escrito en la casilla ubicada en la fila $2018$ y la columna $10000$.
(La figura debería tener las columnas divididas pero no encontré cómo hacerlo en Látex y así creo que se entiende. Se ven las primeras 4 columnas.)

\begin{vmatrix}
\dots & \dots & \dots & \dots \\
\hline
2 & 3 & 0 & 1 & \dots \\
\hline
1 & 0 & 3 & 2 & \dots \\
\hline
0 & 1 & 2 & 3 & \dots \\
\hline
\end{vmatrix}

Matías

OFO - Medalla de Bronce FOFO Pascua 2017 - Medalla OFO - Medalla de Plata
Mensajes: 106
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 4
Nivel: 2

Re: CIMA - Problema 2 (Competencia Interuniversitaria)

Mensaje sin leer por Matías » Lun 02 Jul, 2018 7:43 pm

Spoiler: mostrar
Veamos el cuadrado inferior izquierdo de lado $2^n$ (siendo $n\in N$), es decir, el cuadado que está de la fila $2^n$ (inclusive) para abajo y de la columna $2^n$ (inclusive) hacia la izquierda, y veamos el cuadrado inferior izquierdo de lado $2^{n-1}$ (siendo $n\in N_0$).

Tenemos que:
-En el cuadrado inferior izquierdo de lado $2^n$, en cada fila y en cada columna, están todos los enteros no negativos menores a $2^n$, y ninguno mayor o igual a $2^n$.
-Dentro del cuadrado inferior izquierdo de lado $2^n$, el cuadrado superior derecho de lado $2^{n-1}$ (es decir, el cuadrado entre las filas $2^{n-1}+1$ y $2^n$ y entre las filas $2^{n-1}+1$ y $2^n$, todas inclusive) es idéntico al cuadrado inferior izquierdo de lado $2^{n-1}$; y los cuadrados inferior derecho y superior izquierdo de lado $2^{n-1}$ son como el cuadrado inferior izquierdo de lado $2^{n-1}$ pero añadidos en $2^{n-1}$ en cada una de sus respectivas casillas (es decir, si a cada casilla del cuadrado inferior izquierdo le sumamos $2^{n-1}$, obtenemos los cuadrados inferior derecho y superior izquierdo).

Vamos a demostrarlo por inducción:
-Para $n=1$ (caso base) tenemos que se cumple:
1 0
0 1
Ahora, sabiendo que se cumple para $n$, vamos a demostrar que se cumple para $n+1$:

Tenemos que $(1;2^n+1)=(2^n+1;1)=2^n$ (ya que la casilla inferior izquierda $(1;1)=0$ y, a partir de ahí, construimos la primera columna y la primera fila sumándole 1 a la casilla que está abajo o a la izquierda (respectivamente), entonces tenemos que $(1;m)=(m;1)=m-1$ $\forall m\in N$). Y como en el cuadrado inferior izquierdo de lado $2^n$, en cada casilla y en cada columna, ya están todos los números enteros no negativos menores a $2^n$, los cuadrados superior izquierdo e inferior derecho de lado $2^n$ se van a construir de la misma forma que el inferior izquierdo pero añadidos en $2^n$, es decir, en cada casilla se va a escribir el menor entero mayor o igual a $2^n$ que no aparezca a la izquierda ni debajo, ya que en sus casillas inferiores izquierdas está escrito el $2^n$. Notemos que, de esta manera, en cada fila y en cada columna de los cuadrados superior izquierdo e inferior derecho, van a estar presentes todos los números enteros mayores o iguales a $2^n$ y menores a $2^{n+1}$, y ninguno menor a $2^n$ o mayor o igual a $2^{n+1}$.

Y el cuadrado superior derecho de lado $2^n$ va a ser idéntico al inferior izquierdo, ya que en los cuadrados superior izquierdo e inferior derecho todos los números son mayores o iguales a $2^n$, entonces vamos a tener que $(2^n+1;2^n+1)=0$ (de hecho $(a;b)=0\Leftrightarrow a=b$ $\forall a, b\in N$) y a partir de ahí se va a completar el cuadrado.

De esta forma, volvemos a tener que, en cada fila y en cada columna del cuadrado inferior izquierdo de lado $2^{n+1}$, están presentes todos los números enteros no negativos menores a $2^{n+1}$, y ninguno mayor o igual a $2^{n+1}$. Así que completamos el paso inductivo.

Entonces tenemos que $(10000;2018)=$
$(1808;2018)+8192=$
$(784;994)+8192=$
$(272;482)+8192=$
$(16;226)+8192=$
$(16;98)+8320=$
$(16;34)+8384=$
$(16;2)+8416=$
$(8;2)+8424=$
$(4;2)+8428=$
$(2;2)+8430=$
$0+8430=8430$
Por lo tanto concluimos que en la casilla de la fila $2018$ y la columna $10000$ está escrito el número $8430$.

Responder