CIMA 2018 - Problema 1 (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 1 (Competencia Interuniversitaria)

Mensaje sin leer por sebach »

Para cada número natural $n$, hallar el menor entero $r(n)$ para el cual existe una matriz $A$ de tamaño $n\times n$ con coeficientes reales que tiene exactamente $r(n)$ entradas (casilleros) no nulas, y tal que $A^2$ tiene todas sus entradas no nulas.

Aclaración: $A^2$ es la matriz de tamaño $n × n$ cuya entrada $(i, j)$ es $\sum \limits _{k=1}^{n} A_{ik}\cdot A_{kj}$ , siendo $A=\left (A_{ij}\right )$.
Avatar de Usuario
Matías V5

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020 OFO - Jurado-OFO 2021
Mensajes: 1114
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 8
Nivel: Exolímpico

Re: CIMA 2018 - Problema 1 (Competencia Interuniversitaria)

Mensaje sin leer por Matías V5 »

Spoiler: mostrar
Probaremos que $r(n) = 2n-1$ para todo $n \in \mathbb N$.
Consideramos la matriz $A$ que tiene $1$ en todas las entradas de la fila $n$ y la columna $n$, y $0$ en las demás. Por ejemplo, para $n=4$ sería $A = \begin{pmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 \end{pmatrix}$. Esta matriz tiene exactamente $2n-1$ entradas no nulas. Es fácil verificar que todas las entradas de $A^2$ son iguales a $1$, salvo en el lugar $(n,n)$ donde tiene un $n$. En particular todas las entradas de $A^2$ son no nulas y por lo tanto $r(n) \leq 2n-1$.
Ahora, supongamos que existe $A \in \mathbb R^{n \times n}$ con $r$ entradas no nulas tal que $A^2$ tiene todas sus entradas no nulas, y $r < 2n$. Debe haber alguna fila de $A$ con a lo sumo una entrada no nula (si no, sería $r \geq 2n$). Supongamos que esta es la fila $i$ y que todos los lugares salvo el $j$-ésimo son $0$. Afirmamos que entonces la fila $j$ no tiene ninguna entrada igual a $0$. Esto es así porque si $a_{jk} = 0$ entonces al multiplicar la fila $i$ por la columna $k$ se obtiene $0$, es decir el lugar $(i,k)$ de la matriz $A^2$ sería igual a $0$. Hasta aquí tenemos que las $n$ entradas de la fila $j$ son no nulas, y en cada una de las otras filas debe haber alguna entrada no nula. Esto nos da $r \geq 2n-1$, así que el ejemplo que habíamos encontrado no se puede mejorar. La solución está completa. $\blacksquare$
1  
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore!

Numberblocks - https://www.youtube.com/watch?v=KzTR72_srTU
Responder