OFO 2022 Problema 15

Problemas que aparecen en el Archivo de Enunciados.
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
Mensajes: 1925
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 14
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

OFO 2022 Problema 15

Mensaje sin leer por Gianni De Rico »

En un tablero de $2022\times 2022$ se escriben números reales positivos, uno en cada casilla, de modo que si dos casillas son simétricas respecto de la diagonal principal, entonces el producto de los números escritos en ambas es $1$. Sea $c_i$ la suma de los números escritos en la fila $i$, para cada $i=1,2,\ldots ,2022$, y sea$$c=\frac{1}{c_1}+\frac{1}{c_2}+\cdots +\frac{1}{c_{2022}}.$$Hallar el mayor valor posible de $c$.

Aclaración: La diagonal principal es la que va de la esquina superior izquierda a la esquina inferior derecha.
1  
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850
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
Mensajes: 1925
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 14
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: OFO 2022 Problema 15

Mensaje sin leer por Gianni De Rico »

Solución Oficial:
Spoiler: mostrar
Resolvemos el problema para un tablero de $n\times n$, en particular el resultado vale para $n=2022$. Sea $a_{i,j}$ el número escrito en la fila $i$, columna $j$ del tablero, entonces $c_i=\sum \limits _{k=1}^na_{i,k}$. Sea $c=\sum \limits _{i=1}^n\dfrac{1}{c_i}$, buscamos hallar el mayor valor posible de $c$.

Notemos que si $a_{i,j}=1$ para todos $i,j$, entonces el tablero cumple la condición y $c=1$. Veamos ahora que $c\leq 1$.
En efecto, si $x_1,\ldots ,x_n\in \mathbb{R}^+$, entonces por Cauchy Fraccionario tenemos que$$\sum \limits _{j=1}^n\frac{x_j^2}{a_{i,j}}\geq \frac{\left (\sum \limits _{j=1}^nx_j\right )^2}{\sum \limits _{j=1}^na_{i,j}}$$para todo $i$. Como $a_{i,j}=\dfrac{1}{a_{j,i}}$ para todos $i,j$, poniendo $x_j=\dfrac{1}{c_j}$ tenemos que$$\sum \limits _{j=1}^n\frac{a_{j,i}}{c_j^2}\geq c^2\frac{1}{c_i}$$para todo $i$. Sumando sobre $i$ obtenemos que$$\sum \limits _{i=1}^n\sum \limits _{j=1}^n\frac{a_{j,i}}{c_j^2}\geq c^2\sum \limits _{i=1}^n\frac{1}{c_i}=c^3.$$Por otro lado, como$$\sum \limits _{i=1}^n\sum \limits _{j=1}^n\frac{a_{j,i}}{c_j^2}=\sum \limits _{j=1}^n\sum \limits _{i=1}^n\frac{a_{j,i}}{c_j^2}=\sum \limits _{j=1}^n\left (\frac{1}{c_j^2}\sum \limits _{i=1}^na_{j,i}\right )=\sum \limits _{j=1}^n\frac{1}{c_j^2}c_j=\sum \limits _{j=1}^n\frac{1}{c_j}=c$$entonces $c\geq c^3$.
Como $c>0$, entonces $1\geq c^2$, de donde $c\leq 1$.

Habiendo dado la cota y el ejemplo, tenemos que el mayor valor posible de $c$ es $1$.
1  
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850
juandodyk

OFO - Medalla de Oro-OFO 2022
Mensajes: 28
Registrado: Mar 26 Jun, 2018 1:59 am
Medallas: 1
Nivel: Exolímpico

Re: OFO 2022 Problema 15

Mensaje sin leer por juandodyk »

Spoiler: mostrar
El mayor valor posible es de $c$ es $1$, y vale cambiando $2022$ por $n$ para cualquier $n$ entero positivo. Lo que hay que probar es que para toda matriz $A\in\mathbb R_+^{n\times n}$ tal que $a_{ij}a_{ji}=1$ para todos $1\leq i,j\leq n$ se cumple que $$\sum_{i=1}^n \frac{1}{\sum_{j=1}^n a_{ij}} \leq 1.$$

Sea $\epsilon\in(0,1)$. El conjunto $X=\{(a_{ij})_{1\leq i<j\leq n} : a_{ij} \in [\epsilon, 1/\epsilon]\}$ es compacto. Sea $M$ el conjunto de las matrices del enunciado, es decir, $M=\{(a_{ij})_{1\leq i,j\leq n} : a_{ij}>0, a_{ij}a_{ji}=1 \text{ para todos } i,j\}$. Sea $\iota : X \to M\cap[\epsilon, 1/\epsilon]^{n\times n}$ dada por $\iota(A)_{ij} = a_{ij}$ si $i<j$, $\iota(A)_{ii}=1$, $\iota(A)_{ji}=a_{ij}^{-1}$ si $i>j$, donde $A=(a_{ij})_{1\leq i<j\leq n}$. Obviamente es continua y biyectiva. La funcion $f:M \to \mathbb R$ dada por $f(A) = \sum_{i=1}^n \frac{1}{\sum_{j=1}^n a_{ij}}$ es obviamente continua, por lo que $g=f\circ\iota:X\to\mathbb R$ es continua. Entonces por Weierstrass hay $A\in X$ tal que $g(A)$ es maximo.

Tenemos que $$g(A) = f\circ\iota(A) = \sum_{i=1}^n \frac{1}{\sum_{j=1}^{i-1} a_{ji}^{-1} + 1 + \sum_{j=i+1}^n a_{ij}}.$$
La derivada parcial respecto a $a_{ij}$ con $i<j$ es
$$\frac{\partial g}{\partial a_{ij}} = \frac{-1}{\left( \sum_{k=1}^{i-1} a_{ki}^{-1} + 1 + \sum_{k=i+1}^n a_{ik} \right)^2} + \frac{1}{a_{ij}^2\left( \sum_{k=1}^{j-1} a_{kj}^{-1} + 1 + \sum_{k=j+1}^n a_{jk} \right)^2}.$$
Como $A$ es maximo, esta derivada tiene que ser 0, luego $\sum_{k=1}^{i-1} a_{ki}^{-1} + 1 + \sum_{k=i+1}^n a_{ik} = a_{ij}\left( \sum_{k=1}^{j-1} a_{kj}^{-1} + 1 + \sum_{k=j+1}^n a_{jk} \right)$.
Tomemos $i=1$. La ecuacion es $1 + \sum_{k=2}^n a_{1k} = a_{1j}\left( \sum_{k=1}^{j-1} a_{kj}^{-1} + 1 + \sum_{k=j+1}^n a_{jk} \right)$. Es decir,
$$\frac{1}{\sum_{k=1}^{j-1} a_{kj}^{-1} + 1 + \sum_{k=j+1}^n a_{jk}} = \frac{a_{1j}}{1 + \sum_{k=2}^n a_{1k}}.$$
Sumando sobre $j=2,\ldots,n$ obtenemos
$$\sum_{j=2}^n \frac{1}{\sum_{k=1}^{j-1} a_{kj}^{-1} + 1 + \sum_{k=j+1}^n a_{jk}} = \frac{\sum_{j=2}^n a_{1j}}{1 + \sum_{k=2}^n a_{1k}}.$$
Sumando $\frac{1}{1 + \sum_{k=2}^n a_{1k}}$ a ambos lados obtenemos
$$\sum_{j=1}^n \frac{1}{\sum_{k=1}^{j-1} a_{kj}^{-1} + 1 + \sum_{k=j+1}^n a_{jk}} = \frac{1+\sum_{j=2}^n a_{1j}}{1 + \sum_{k=2}^n a_{1k}} = 1.$$
Lo de la izquierda es $g(A)$. Luego $g(A)=1$.

Esto implica que el maximo de $f$ sobre $M\cap[\epsilon, 1/\epsilon]^{n\times n}$ es $1$. Para todo $A\in M$ hay $\epsilon\in(0,1)$ tal que $A\in [\epsilon, 1/\epsilon]^{n\times n}$, por ejemplo $\epsilon=\frac12\min\{a_{ij}\}$. Entonces $f(A)\leq 1$ para todo $A$, como queriamos probar.
2  
Responder