Problem. Let $a_1<a_2<\dotsb<a_n\le 2n$ be a sequence of positive integers. Then $$ \min [a_i,a_j]\le 6\left(\Big[\frac n2\Big]+1\right), $$ where $[a_i,a_j]$ denotes the least common multiple of $a_i$ and $a_j$. This is the best possible estimate.

For the first part of the problem I found the following solution

Solution.The statement for $n<3$ is obvious, so suppose that $n\ge 3$. Let $r_i$ be the greatest non-negative integer such that $2^{r_i}a_i\le 2n$, and define $b_i=2^{r_i}a_i$. Now if two of the numbers $b_i$ are equal, then $b_i\le 2n\le 6\left(\Big[\frac n2\Big]+1\right)$ is a multiple of greatest common divisor of at least two of the numbers $a_i$. So we can suppose that $\{b_1,b_2,\dotsc,b_n\}=\{n+1,n+2,\dotsc,2n\}$. Now observe that $2\Big[\frac n2+1\Big]=b_i,3\Big[\frac n2+1\Big]=b_j$, for some $i,j$ (here we need the assumption $n\ge 3$), and we have $[b_i,b_j]=6\left(\Big[\frac n2\Big]+1\right)$, and hence $[a_i,a_j]\le 6\left(\Big[\frac n2\Big]+1\right)$.

Now to prove that this estimate is best possible, is it enough to give the example $a_1=4<a_2=5<a_3=6$ for $n=3$ to get inequality into equality?

  • $\begingroup$ I think you will need to give an example of equality for every n or atleast arbitrarily high n. $\endgroup$ – Asvin Apr 28 '15 at 13:56
  • $\begingroup$ I also think that there must be examples for arbitrary large n's...but what are these examples? $\endgroup$ – k1.M Apr 28 '15 at 13:59
  • $\begingroup$ May I suggest changing those $\alpha_i$'s to $r_i$'s? On my browser, at least, $\alpha_i$ and $a_i$ are virtually indistinguishable, especially when the former appears in reduced size as an exponent. $\endgroup$ – Barry Cipra Apr 28 '15 at 14:26
  • $\begingroup$ I applied your suggestion in the last edit... $\endgroup$ – k1.M Apr 28 '15 at 14:47

Your Answer

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

Browse other questions tagged or ask your own question.