KöMaL 2024 A882

Let $H_1$, $H_2$, $\ldots$, $H_m$ be non-empty subsets of the positive integers, and let $S$ denote their union. Prove that $\sum_{i=1}^m \sum_{a, b\in H_i} \gcd(a,b) \ge \frac{1}{m} \sum_{a, b\in S} \gcd(a, b)$. (The $\sum_{(a,b)\in X}$ notation means that the summation is over ordered pairs $(a,b)$ where $a\in X$ and $b\in X$.)