Suppose $n$ is a perfect square. Consider the set of all numbers which is the product of two numbers, not necessarily distinct, both of which are at least $n$. Express the $n-$th smallest number in this set in terms of $n$.
Problem
Source: India Postal Set 1 P4 2016
Tags: number theory, inequalities, algebra
22.01.2017 18:40
The ans is $(n+\sqrt{n}-1)^2$. Create an array and done.
22.01.2017 19:33
$\textsc{Answer:}$The $n-$th smallest element in the said set is $(n+\sqrt{n}-1)^2$. $\textsc{Proof:}$ Let $n=m^2$, and let $A=\{(n+a)(n+b): a,b \text{ are nonnegative integers }\}$. We are required to find the $n-$th smallest number in this set. We claim the $n$ smallest numbers in order are in fact $$\begin{array}{cccc} n^2,\\ n(n+1), \\ n(n+2), & (n+1)(n+1),\\ n(n+3), & (n+1)(n+2),\\ & \vdots &\\ n(n+2m-2), & (n+1)(n+2m-3), &\cdots , & (n+m-1)(n+m-1)\end{array}$$One might verify that the number of elements written above is indeed $n$, since $1+1+2+2+\cdots +(m-1)+(m-1)+m=2\cdot \frac{m(m-1)}{2}+m=m^2-m+m=m^2=n$. Now, to prove our claim, we need to show two things: $n^2<n(n+1)<n(n+2)<\cdots <(n+m-1)(n+m-1)$, and all the other elements of $A$ are at least $(n+m-1)^2$. For proving part 1 (You need a proof! You don't trust me!) note that two elements occurring in the same row are of the form $(n+x)(n+k-x)$ and $(n+y)(n+k-y)$, with $x,y$ integers less that $\left\lfloor \frac{k}{2}\right\rfloor$, satisfying $x<y$ if $(n+x)(n+k-x)$ appears earlier. Now note that \begin{align*} (n+x)(n+k-x)<(n+y)(n+k-y) &\iff n^2+kn+kx-x^2< n^2+kn+ky-y^2\\ &\iff x^2-y^2-kx+ky>0\\ &\iff (y-x)(k-x-y)>0\end{align*}But the last inequality is obvious since $y>x$ and $ \frac{k}{2}>x,y$. So the numbers in each row are in increasing order. Now consider the greatest number in a row and the smallest number in the next row. We will assume that the index of the first row is odd; the other case is entirely similar. If the first row is the $2k+1$-th row, then the numbers are $(n+k)(n+k)$ and $n(n+2k+1)$. Now we note that \begin{align*} (n+k)^2<n(n+2k+1) &\iff n^2+2kn+k^2< n^2+2kn+n\\ &\iff k^2<n\end{align*}But the last inequality is trivially true, so I wasn't lying all this while. Now for the 2nd part, note that another element of $A$ would be of the form $(n+a)(n+b)$ with $a+b> 2m-2$, since we have already exhausted all elements with $a+b\le 2m-2$. Then we note that \begin{align*} (n+a)(n+b)\ge (n+m-1)^2 & \iff n^2+(a+b)n+ab\ge n^2+(2m-2)n+(m-1)^2\\ & \iff (a+b)n+ab+m^2\ge (2m-1)n+(m-1)^2\end{align*}For proving the last inequality, we note that $(a+b)n\ge (2m-1)n$, and that $ab+m^2\ge a(2m-1-a)+m^2\ge m^2+ 1(2m-2)> m^2 -2m+1$, so we are ready to draw a black square. $\blacksquare$
07.04.2017 14:21
The solution I submitted was as follows (it is almost the same as @Ankoganit's solution, but no one can be blamed, the problem with the problem is that it is mechanical.): $\textbf{Answer}:$ $(n+\sqrt{n}-1)^2$ $\textbf{Solution}:$ First, we set $n=k^2$ and observe that $k^2=\sum_{i=0}^{k}i+ \sum_{i=0}^{k-1}i.$ Now we draw a kind of an array, with the $2i-1$th and the $2i$th row having $i$ entries each, where $1\leq i\leq k$ and we omit the $2k$th row. By our observation, there will be exactly $n$ elements in our array. For the $2i-1$th row, the $j$th entry is $(k^2+j-1)(k^2+2i-j-1)$ with $1\leq j\leq i$ and for the $2i$th row the $j$th entry is $(k^2+j-1)(k^2+2i-j)$ with $1\leq j\leq i$. If $j\leq l-1$ for some $j, l$, $$l-j-1 \geq 0 \Longrightarrow (j+1)(l-1) \geq jl \Longrightarrow k^4+k^2(j+l)+jl \leq k^4+k^2(j+l) +(j+1)(l-1)$$$$ \Longrightarrow (k^2+j)(k^2+l) \leq (k^2+j+1)(k^2+l-1)$$which shows that we have ordered the elements of each particular row in ascending order. Also we note the inequality $(k^2+i-1)^2 < k^2(k^2+2i-1)$ which is true because $(k^2+i-1)^2 < k^2(k^2+2i-1) \Longleftrightarrow 2(i-1)k^2+(i-1)^2 < k^2(2i-1) \Longleftrightarrow i-1<k $. this implies that the last element of each row is smaller than the first element of the next row, which shows that we have arranged them in the normal increasing order. Now we show that no other number between $k^2$ and $k^2+k-1$ other than those we have listed can be factored in the required way. To see this we read the array columnwise. We observe that we have enumerated all the multiples of $(k^2+i-1)$ from $(k^2+i-1)^2$ to $(k^2+i-1)(k^2+2k-i-1)$. Since we have enumerated all such multiples from the beginning, and since smaller multiples have been included with the multiples of the smaller multiplicand, we just need to check that for any $i$ with the above limits satisfies the inequality $(k^2+i-1)(k^2+2k-i) \gneq (k^2+k-1)^2$ for then we would get that any higher multiple of $(k^2+i-1)$ would be greater than $(k^2+k-1)^2$ which would imply the conclusion. To prove the mentioned inequality, we note that after cancellations it is equivalent to $2ki-i^2+i > 1$, which is true as $2ki-i^2+i \geq i(2k-k+1) = i(k+1) >1$. So we conclude that the elements we have put in the array are actually the first $n$ elements of the required set and thus the answer is the largest number in the collection, i.e, $(k^2+k-1)^2$ which is $(n+\sqrt{n}-1)^2$. $\blacksquare$ \begin{tabular}{|c|c|c|c|} $16 \cdot 16$ \\ $16 \cdot 17$ \\ $16 \cdot 18$ & $17 \cdot 17$ \\ $16 \cdot 19$ & $17 \cdot 18$ \\ $16 \cdot 20$ & $17 \cdot 19$ & $18 \cdot 18$ \\ $16 \cdot 21$ & $17 \cdot 20$ & $18 \cdot 19$ \\ $16 \cdot 22$ & $17 \cdot 21$ & $18 \cdot 20$ & $19 \cdot 19$ \\ \end{tabular}