а) Обозначим через $P_n(d)$ количество пар $(a,b)$ натуральных чисел $a\lt b\le n$ с наибольшим общим делителем $d=\gcd(a,b)$. Каждую такую пару можно представить в виде $a=dx$, $b=dy$, где $x\lt y\le k=\left[\dfrac nd\right]$, причём $x$ и $y$ взаимно просты. Количество $P_k=P_k(1)$ таких пар $(x,y)$ взаимно простых чисел нетрудно оценить сверху
$$
P_k\le 1+2+\ldots+(k-1)=\dfrac{k(k-1)}2,
$$
поскольку при каждом $y\le k$ число $x\lt y$ принимает не больше $y-1$ значений. Отсюда
$$
P_n(d)=P_{\left[\frac{\scriptstyle n}{\scriptstyle d}\right]}\le
\dfrac n{2d}\left(\dfrac n2-1\right)\le\dfrac{n(n-1)}{2d^2}.
$$
В конце решения мы докажем оценку снизу $P_k\ge\dfrac{k(k-1)}4$; из неё получается оценка для $P_n(d)$:
$$
P_n(d)\ge\dfrac14\left(\dfrac nd-1\right)\left(\dfrac nd-2\right)=
\dfrac{n^2-3nd+2d^2}{4d^2}\gt\dfrac{n(n-1)}{4d^2}-\dfrac{3n}{4d}.
$$
Сумма чисел $d=\gcd(a,b)$ по всем парам $(a,b)$ равна $\sum\limits_{d=1}^{n-1}dP_n(d)$, а их среднее арифметическое $A$ равно $\dfrac2{n(n-1)}\sum\limits_{d=1}^{n-1}dP_n(d)$. Используя оценки для $P_n(d)$, получаем:
$$
\begin{align*}
A&\le\dfrac2{n(n-1)}\sum\limits_{d=1}^{n-1}d\dfrac{n(n-1)}{2d^2}=1+\dfrac12+\dfrac13+\ldots+\dfrac1{n-1},\tag{1}\\
A&\gt\dfrac2{n(n-1)}\sum\limits_{d=1}^{n-1}d{\left(\dfrac{n(n-1)}{4d^2}-\dfrac{3n}{4d}\right)}=\dfrac12{\left(1+\dfrac12+\ldots+\dfrac1{n-1}\right)}-\dfrac32.\tag{2}
\end{align*}
$$
Далее нам потребуется следующая
Лемма.Для любого натурального$n$
$$
\dfrac12+\ldots+\dfrac1n\lt\ln n\lt 1+\dfrac12+\ldots+\dfrac1{n-1}.
$$
Рис. 1
Для её доказательства можно воспользоваться тем, что $\ln n=\displaystyle\int\limits_1^n\dfrac1tdt$ — площадь под гиперболой $f(t)=\dfrac1t$ на участке $1\le t\le n$ (рис. 1); можно не пользоваться интегралом, а, например, убедиться в справедливости неравенств
$$
\dfrac\alpha{1+\alpha}\le\ln(1+\alpha)\le\alpha\quad\text{при}~\alpha\ge0
$$
(заметив, что при $\alpha=0$ все три члена равны 0 и сравнив производные), затем подставить в них $\alpha=1$, $\alpha=\dfrac12$, $\ldots$, $\alpha=\dfrac1{n-1}$ и сложить все полученные неравенства.
Применяя лемму к оценкам (1) и (2), получим
$$
\dfrac12\ln n-\dfrac32\lt A\le\ln(n-1)+1\lt\ln n+1.
$$
б) Логарифм среднего геометрического нескольких чисел равен среднему арифметическому их логарифмов. Поэтому для решения задачи достаточно доказать, что среднее арифметическое чисел вида $\ln d$ (где $d=\gcd(a,b)$, $a\lt b\le n$) меньше 2; ведь $e^2\lt 10$, т. е. $2\lt\ln 10$. Действуя так же, как и выше, получим
$$
\dfrac2{n(n-1)}\sum\limits_{d=1}^n\ln d\cdot P_n(d)\le
\sum\limits_{d=2}^n\dfrac{\ln d}{d^2}\lt
\sum\limits_{d=2}^n\left(\dfrac1{d^2}\sum\limits_{h=1}^d\dfrac1h\right).
$$
Здесь мы применили лемму: $\ln d\le 1+\dfrac12+\ldots+\dfrac1d$. В образовавшейся двойной сумме чисел вида $\dfrac1{d^2}\dfrac1h$ ($1\le h\le d$, $2\le d\le n$) удобно собрать вместе члены с одинаковыми $h$ ($1\le d\le n$ при $h=1$, $h\le d\le n$ при $h\gt1$) и оценить $\sum\limits_{d=h}^n\dfrac1{d^2}$ с помощью легко сворачивающейся суммы
$$
\sum\limits_{d=h}^n\dfrac1{d(d-1)}=\sum\limits_{d=h}^n\left(\dfrac1{d-1}-\dfrac1d\right)=
\dfrac1{h-1}-\dfrac1n\lt\dfrac1{h-1}
$$
(эта оценка понадобится сейчас ещё раз для $h=2$). Окончательно получаем
$$
\sum\limits_{d=2}^n\dfrac{\ln d}{d^2}\lt
\sum\limits_{d=2}^n\dfrac{1}{d^2}+\sum\limits_{h=2}^n\left(\dfrac1h\sum\limits_{d=h}^{n-1}
\dfrac1{d^2}\right)\lt1+\sum\limits_{h=2}^n\dfrac1{h(h-1)}\lt2.
$$
Рис. 2
Докажем теперь оценку $P_k\ge k(k-1)$, использованную в решении пункта а). Положим $m=\left[\dfrac k2\right]$. Среди всех целых точек $(x,y)$, где $0\lt x\lt y\le k$, назовём красными те, для которых $x$ и $y$ взаимно просты (рис. 2). Проведём через каждую красную точку в треугольнике $x\lt y\le m$ луч из начала координат $(0,0)$. Эти $P_m$ лучей содержат, конечно, все $\dfrac{m(m-1)}2$ целых точек в треугольнике $x\lt y\le m$.
Рассмотрим целые точки на любом из $P_h$ лучей. Их количество на участке $h+1\le y\le k$ может превосходить их количество на участке $1\le y\le h$ не более, чем на единицу (ведь целые точки $(x,y)$ встречаются на луче через равные промежутки). Поэтому в трапеции $m+1\le y\le k$, $x\lt y$ из всех $\dfrac{k(k-1)}2-\dfrac{m(m-1)}2$ целых точек на проведённых лучах лежат не более $\dfrac{m(m-1)}2+P_m$ точек. Все остальные целые точки в трапеции — красные; таким образом, их число
$$
P_k-P_m\ge\dfrac{k(k-1)}2-m(m-1)-P_m,
$$
откуда
$$
P_k\ge\dfrac{k(k-1)}2-m(m-1)\ge\dfrac{k(k-1)}4
$$
(последнее неравенство нетрудно проверить для $k=2m$ и $k=2m+1$). Можно показать, что $\lim\limits_{k\to\infty}\dfrac{P_k}{k^2}=\dfrac3{\pi^2}$, т. е. вероятность, что случайно взятые натуральные числа $(x,y)$, не превосходящие $k$, окажутся взаимно простыми, стремится к $\dfrac6{\pi^2}$ при $k\to\infty$ (см., например, задачу 30 к главе III в книге И. М. Виноградова «Введение в теорию чисел», М.: Наука, 1965).
