Suppose $n$ is a perfect square. Consider the set of all numbers which are 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$.

If, for example, $n = 4$, then the numbers are $4^2, 4 \cdot 5, 4 \cdot 6, 5^2$. If $n = 9$, then the numbers are $9^2,9 \cdot 10, 9 \cdot 11, 10^2, 9 \cdot 12, 10 \cdot 11,9 \cdot 13, 10 \cdot 12, 11^2$. Thus we conjecture the answer is $(n+\sqrt{n}-1)^2$, but how do we prove this?

  • $\begingroup$ that number isn't an integer for most $n$ I think. $\endgroup$ – Jorge Fernández Hidalgo Jan 18 '17 at 3:39
  • $\begingroup$ @JorgeFernándezHidalgo Recall that $n$ is a perfect square. $\endgroup$ – Puzzled417 Jan 18 '17 at 3:39
  • $\begingroup$ oh, my bad.${}{}{}$ $\endgroup$ – Jorge Fernández Hidalgo Jan 18 '17 at 3:39
  • $\begingroup$ Why do you think that number works? $\endgroup$ – Jorge Fernández Hidalgo Jan 18 '17 at 3:46
  • $\begingroup$ @JorgeFernándezHidalgo Because I tested it for some examples and it was true. $\endgroup$ – Puzzled417 Jan 18 '17 at 3:48

Clearly there $w=(n+\sqrt n -1)^2$ is at least the $n$'th number in the list.

We must only prove that $w<ab$ if $a+b>2n+2\sqrt{n}-2$, with both $a$ and $b\geq n$.

Clearly this product is minimized in the case $a=n$, Which leaves $b>n+2\sqrt{n}-2$, since $b$ is an integer we can take the minimal case $b=n+\sqrt{2n}-1$.

So we must only prove $n(n+2\sqrt{n}-1)\geq (n+\sqrt{n}-1)^2\iff -n>-2n-2\sqrt{n}+n+1=-n-2\sqrt{n}+1$.

So it is in fact true.

  • $\begingroup$ Why is $w$ at least the $n$th number in the list? $\endgroup$ – Puzzled417 Jan 18 '17 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.