Sum of the entries

For discussing Olympiad Level Algebra (and Inequality) problems
tanmoy
Posts:312
Joined:Fri Oct 18, 2013 11:56 pm
Location:Rangpur,Bangladesh
Sum of the entries

Unread post by tanmoy » Thu Oct 13, 2016 6:01 pm

You are given a $n \times n$ array as follows:
\[\begin{array}{cccc}\displaystyle
1 & \frac 1 2 & \cdots & \frac 1 n\\
\frac 1 2 & \frac 1 3 & \cdots & \frac 1 {n+1}\\
: & : & & :\\
: & : & & :\\
\frac 1 n & \frac 1 {n+1} & \cdots & \frac 1 {2n-1}
\end{array}
\]
Prove that the sum of any $n$ entries situated in different rows and different columns is not less than $1$.
"Questions we can't answer are far better than answers we can't question"

User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:

Re: Sum of the entries

Unread post by Phlembac Adib Hasan » Sat Oct 15, 2016 2:10 pm

($1000^{th}$ post, yay)
Solution:
Enumerate the rows and columns from the top-left corner. Then the entry in $i$-th row and $j$-th column is $\dfrac {1}{i+j-1}$. Suppose the set of selected $n$ entries is $E$.

Now using Cauchy-Schwartz's Inequality,
\[
\begin{split}
\sum_{(i,j)\in E} \frac{1}{i+j-1} &\ge \frac{n^2}{\sum i+j-1}\\
&= \frac{n^2}{\frac{n(n+1)}{2}+\frac{n(n+1)}{2}-n}\\
&=\frac{n^2}{n(n+1)-n}\\
&=\frac{n^2}{n^2}\\
&=1
\end{split}
\]
as desired.

Comment:
There is another inductive solution. It becomes pretty obvious when you notice the problem statement holds even if you start filling the array from $\frac 1 m$.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

Post Reply