Let $n\geq 2$ be an integer. Let $a_{ij}, \ i,j=1,2,\ldots,n$ be $n^2$ positive real numbers satisfying the following conditions: For all $i=1,\ldots,n$ we have $a_{ii}=1$ and, For all $j=2,\ldots,n$ the numbers $a_{ij}, \ i=1,\ldots, j-1$ form a permutation of $1/a_{ji}, \ i=1,\ldots, j-1.$ Given that $S_i=a_{i1}+\cdots+a_{in}$, determine the maximum value of the sum $1/S_1+\cdots+1/S_n.$
Problem
Source: Romania TST 2022
Tags: inequalities, algebra, romania, Romanian TST
15.05.2022 21:14
Very nice problem! The required maximum is $1.$ This can obviously be achieved by letting all entries of the matrix be equal to $1.$ Using the condition, we could rewrite the inequality as $$\sum_{j=1}^{n}\frac{1}{1+\sum_{i<j}\frac{1}{a_{ij}}+\sum_{i>j}a_{ji}}\le 1.$$ We will prove this inequality by induction on $n$. When $n=2$ this is just $\frac{1}{1+a_{12}}+\frac{1}{1+\frac{1}{a_{12}}}\le 1$, which is obviously true - we have equality, in fact. Now, suppose that the inequality is true for $n$, and we will prove it for $n+1.$ Denote $S'_{j} = 1 + \sum_{1<i<j}\frac{1}{a_{ij}}+\sum_{i>j}a_{ji}$ for any $j\ge 2$, so that $S_j-S'_j=\frac{1}{a_{1j}}$ for all $j\ge 2.$ Then, \begin{align*} \sum_{j=2}^{n+1}\frac{1}{S'_j}-\sum_{j=1}^{n+1}\frac{1}{S_j} &= \left[\sum_{j\ge 2}\left(\frac{1}{S'_j}-\frac{1}{S_j}\right)\right]-\frac{1}{S_1}\\ &= \left[\sum_{j\ge 2}\frac{\left(\frac{1}{S'_j}\right)^2}{a_{1j}+\frac{1}{S'_j}}\right]-\frac{1}{S_1} \\ &\ge\frac{\left(\sum_{j\ge 2}\frac{1}{S'_j}\right)^2}{S_1-1+\left(\sum_{j\ge 2}\frac{1}{S'_j}\right)}-\frac{1}{S_1}, \end{align*} where the last inequality is just Cauchy-Schwarz. For simplicity, denote $a = \sum_{j\ge 2}\frac{1}{S'_j}$ and $b=S_1-1=\sum_{j\ge 2}a_{1j}>0.$ Note that $a\le 1$ by the induction hypothesis (too see why, just eliminate the first row of the upper triangular matrix). Thus, \begin{align*} a-\sum_{j=1}^{n+1}\frac{1}{S_j} &\ge\frac{a^2}{a+b}-\frac{1}{1+b} \\ &= \left(a-\frac{1}{\frac{1}{a}+\frac{1}{b}}\right)-\left(1-\frac{1}{1+\frac{1}{b}}\right) \\ &= (a-1)+\left(\frac{1}{1+\frac{1}{b}}-\frac{1}{\frac{1}{a}+\frac{1}{b}}\right) \\ &\ge a-1. \end{align*} This proves that $\sum_{j=1}^{n+1}\frac{1}{S_j}\le 1$, thus establishing the induction step. This ends our proof.
28.07.2022 14:04
Actually the problem is equivalent to something I've posted before in 2021. See here.