Ниже будет доказано более общее утверждение. Пусть $a_1\lt a_2\lt\ldots\lt a_n\le2n$.
а) Докажем, что требуемое неравенство выполняется при $n\ge5$. Пусть среди элементов последовательности $a_1$, $a_2$, $\ldots$, $a_n$ найдётся число $a\le n$. Если число $2a$ также принадлежит данной последовательности, то $$
\min\limits_{i,j}{}[a_i,a_j]\le[a,2a]=2a\le2n\le6\left(\left[\dfrac n2\right]+1\right),
$$
что даёт решение задачи. Если же $2a$ не принадлежит последовательности, то выбросим из неё число $a$ и заменим его на $2a$. Ясно, что $\min{}[a_i,a_j]$ для новой последовательности не меньше, чем для исходной. Применив это же рассуждение к каждому элементу $a\le n$, мы придём в конце концов к последовательности $n+1$, $n+2$, $\ldots$, $2n$, причём $\min{}[a_i,a_j]$ для этой последовательности не меньше соответствующего минимума для любой другой последовательности, из которой она была получена, в частности — для исходной.
Докажем теперь, что для последовательности $n+1$, $n+2$, $\ldots$, $2n$ при $n\ge5$ выполняется равенство $\min\limits_{i,j}{}[a_i,a_j]=6\left(\left[\dfrac n2\right]+1\right)$. В самом деле, если $n=2k$ или $n=2k+1$, возьмём следующие числа: $a=2k+2$, $b=3k+3$. Тогда при $n\ge5$
$$
n+1\le a\lt b\le2n
$$
и $$
[a,b]=6k+6=6\left(\left[\dfrac n2\right]+1\right).
$$
А теперь проверим, что для любой пары чисел $c$, $d$, удовлетворяющей условию $n+1\le c\lt d\le2n$, выполняется неравенство $[c,d]\ge6\left(\left[\dfrac n2\right]+1\right)$. Действительно, $[c,d]=pd=qc$, где $q\gt p\gt 1$. При этом либо $p=2$ и $q\ge3$, либо $q\ge4$. В первом случае $c$ — число чётное, тем самым
$c\ge2\left(\left[\dfrac n2\right]+1\right)$ и $[c,d]=qc\ge3c\ge6\left(\left[\dfrac n2\right]+1\right)$.
Во втором случае $[c,d]=qc\ge4(n+1)\gt6\left(\left[\dfrac n2\right]+1\right)$. Этим завершается доказательство утверждения а).
б) Рассмотрим более общую задачу: пусть $a_1\lt a_2\lt\ldots \lt a_k\le B$ — последовательность натуральных чисел; требуется оценить снизу $\max{}(a_i,a_j)$. Для этого полезно решать обратную задачу: пусть $A$, $B$ — положительные (не обязательно целые) числа; определить максимальное $k$, для которого найдётся последовательность из $k$ различных натуральных чисел $a_1$, $a_2$, $\ldots$, $a_k$ такая, что
- каждый элемент последовательности не превосходит $B$;
- $(a_i,a_j)\le A$ для любых различных элементов $a_i$, $a_j$.
Будем обозначать это максимальное количество через $k(A,B)$. Для решения исходной задачи нужно подобрать $A$ так, чтобы $k(A,2n)$ примерно равнялось $n$. Действительно, если для какого-то $A$
$$
k(A,2n)\lt n,
$$
то для любой последовательности $a_1\lt a_2\lt\ldots\lt a_n\le2n$ будет $\max{}(a_i,a_j)\ge A;$ если же $k(A,2n)\ge n$, то найдётся последовательность $a_1\lt a_2\lt\ldots\lt a_n\le2n$ такая, что $\max(a_i,a_j)\le A$.
Пусть $a_1$, $\ldots$, $a_k$ — последовательность, удовлетворяющая условиям (1) и (2). Если у какого-то элемента $a_i$ этой последовательности найдётся собственный (т. е. не совпадающий с $a_i$) делитель $d\gt A$, то в силу условия (2) $d$ не является элементом последовательности. Тогда, заменяя $a_i$ на $d$, мы получим новую последовательность той же длины, также удовлетворяющую условиям (1) и (2). Поступая таким же образом, мы получим в конце концов последовательность, в которой никакой элемент не имеет собственных делителей, больших $A$. Такую последовательность назовём несократимой.
Рассмотрим теперь множество $M$ всех натуральных чисел, которые не превосходят $B$ и не имеют собственных делителей, бо́льших $A$. $M$ является несократимой последовательностью, удовлетворяющей условиям (1) и (2), и любая другая несократимая последовательность содержится в $M$. Поэтому ясно, что $k(A,B)$ просто равно числу элементов множества $M$.
Чтобы подсчитать число элементов множества $M$, сосчитаем отдельно число чётных элементов, число нечётных элементов, делящихся на 3, и т. д. Более точно, пусть $M_2$ состоит из всех чётных элементов множества $M$, $M_3$ состоит из всех нечётных элементов из $M$, делящихся на 3, $M_5$ состоит из всех элементов $M$, делящихся на 5, но не делящихся ни на 2, ни на 3. И вообще, для любого простого числа $p$ множество $M_p$ состоит из тех элементов множества $M$, которые делятся на $p$ и не имеют простых делителей, меньших $p$.
Подсчитаем число элементов множества $M_p$. Любой элемент из $M_p$ имеет вид $pc$, где $c\le A$ (так как $M$ — несократимое множество), $pc\le B$ и $c$ не имеет простых делителей, меньших $p$. Если $pA\le B$, то условие $pc\le B$ можно не принимать во внимание, и число элементов $M_p$ равно количеству натуральных $c\le A$, не имеющих простых делителей, меньших $p$ (такое число будем обозначать через $m_p(A)$). Если же $pA\gt B$, то число элементов $M_p$ равно $m_p{\left(\dfrac Bp\right)}$ и не превосходит $m_p(A)$.
Зафиксируем простое число $p$. Множества $M_2$, $M_3$, $M_5$, $\ldots$, $M_p$, вообще говоря, не исчерпывают множества $M$. Обозначим через $N$ множество всех оставшихся элементов $M$. Они не имеют делителей среди чисел 2, 3, 5, $\ldots$, $p$, поэтому их количество не превосходит числа $m_q(B)$, где $q$ — следующее за $p$ простое число. Таким образом,
$$
k(A,B)\le m_2(A)+m_3(A)+\ldots+m_p(A)+m_q(B).
$$
Если $pA\le B \lt qA$, то это неравенство превращается в равенство. Действительно, ясно, что каждое $M_r$ содержит ровно $m_r(A)$ элементов. С другой стороны, каждое число $c\le B$, которое не имеет делителей, меньших $q$, не имеет тем самым делителей, бо́льших $A$ (если $c=df$, где $f\gt A$ и $c\le B\lt qA$, то $f\lt q$), и поэтому входит в $N$; следовательно, $N$ содержит $m_q(B)$ элементов.
Теперь займёмся оценкой чисел вида $m_r(C)$. Во-первых, $m_2(C)$ равно количеству всех натуральных $l\le C$, т. е. равно $[C]$, и отличается от $C$ меньше, чем на 1. Далее, $m_3(C)=m_2(C)-m_2{\left(\dfrac C2\right)}$ (количество всех $l\le C$ минус количество чётных $l\le C$. Поскольку $m_2(C)$ и $m_2{\left(\dfrac C2\right)}$ отличаются от $C$ и $\dfrac C2$ меньше, чем на 1, то $m_3(C)$ отличается от $C\left(1-\dfrac12\right)$ меньше чем на 2.
Рассуждая таким же образом, мы получим, что если $p$ и $q$ ($p\lt q$) — два соседних простых числа, то $m_q(C)=m_p(C)-m_p{\left(\dfrac Cp\right)}$, откуда индукцией получается, что $m_q(C)$ отличается от числа $C\left(1-\dfrac12\right)\left(1-\dfrac13\right)\ldots\left(1-\dfrac1p\right)$ меньше, чем на $2^{i-1}$, где $i$ — номер простого числа $q$. Иначе говоря, обозначив через $Z_q$ произведение всех чисел вида $\left(1-\dfrac1r\right)$, где $r$ — простое число, меньшее $q$ (и положив $Z_2=1$), получим
$$
|m_q(C)-C\cdot Z_q|\lt2^{i-1}
$$
($i$ — номер простого числа $q$). Таким образом, для числа $k(A,B)$ верны следующие оценки:
$$
\begin{gather*}
k(A,B)\le m_2(A)+\ldots+m_p(A)+m_q(B)\lt\\
\lt A(Z_2+Z_3+\ldots+Z_p)+B\cdot Z_q+(1+2+\ldots+2^{i-1})=\\
=A(Z_2+\ldots+Z_p)+B\cdot Z_q+(2^i-1);
\end{gather*}
$$
если же $pA\le B\lt qA$, то $$
\begin{gather*}
k(A,B)=m_2(A)+\ldots+m_p(A)+m_q(B)\gt\\
\gt A(Z_2+\ldots+Z_p)+B\cdot Z_q-(2^i-1).\tag3
\end{gather*}
$$
Вернёмся теперь к исходной задаче и выясним, при каких $A$ $k(A,2n)\lt n$. Для этого достаточно решить относительно $A$ неравенство
$$
A(1+Z_3+\ldots+Z_p)+2n\cdot Z_q+(2^i-1)\le n.
$$
Беря $p$ равным 3, 5 или 7, мы получим, соответственно,
$$
A\le\dfrac29n-\dfrac{14}3,\quad A\le\dfrac{14}{55}n-\dfrac{90}{11},\quad A\le\dfrac{38}{147}n-\dfrac{310}{21}.
$$
При $p=7$ появляется таинственный множитель $\dfrac{38}{147}$, самый большой из трёх. Брать $p\ge11$ бессмысленно, так как $11\cdot\dfrac{38}{147}n\gt2n,$ и неравенства для $k(A,2n)$ будут менее точными. Итак, мы доказали, что при $n\ge2$ для любой последовательности $a_1\lt a_2\lt \ldots \lt a_n\le2n$
$$
\max{}(a_i,a_j)\gt\dfrac{38}{147}n-\dfrac{310}{21}.
$$
Чтобы доказать, что коэффициент $\dfrac{38}{147}$ нельзя увеличить, возьмём $A=\dfrac{38}{147}n+\dfrac{310}{21}$. Тогда при $n\ge543$ будет $7A\le2n\lt11A$, и, используя неравенство (3), получаем $k(A,2n)\ge n$. Следовательно, при $n\ge543$ всегда найдётся последовательность $a_1\lt a_2\lt\ldots\lt a_n\le2n$, для которой $\max{}(a_i,a_j)\le\dfrac{38}{147}n+\dfrac{310}{21}$.
Если оценить $m_r(C)$ слегка аккуратней, то можно получить более точные неравенства: при $n\ge2$ для любой последовательности $a_1\lt a_2\lt\ldots\lt a_n\le2n$
$$
\max{}(a_i,a_j)\ge\dfrac{38}{147}n-\dfrac{73}{49};
$$
и, кроме того, существует последовательность $a_1\lt a_2\lt\ldots\lt a_n\le2n$, для которой
$$
\max{}(a_i,a_j)\le\dfrac{38}{147}n+\dfrac{73}{49}
$$
(замечательно то, что константу $\dfrac{73}{49}$ в этих неравенствах уменьшить уже нельзя).
