CIMA 2018 - Problema 2 (Competencia Interuniversitaria)

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

CIMA 2018 - Problema 2 (Competencia Interuniversitaria)

Mensaje sin leer por sebach »

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$.$$\begin{array}{|c|c|c|c|c}
\vdots & \vdots & \vdots & \vdots \\
\hline
2 & 3 & 0 & 1 & \ldots \\
\hline
1 & 0 & 3 & 2 & \ldots \\
\hline
0 & 1 & 2 & 3 & \ldots \\
\hline
\end{array}$$
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: 206
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 8
Nivel: 3

Re: CIMA - Problema 2 (Competencia Interuniversitaria)

Mensaje sin leer por Matías »

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