Nemotron-IMO-Bench 2026 N44

Let $A_1, A_2,\ldots, A_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 A_i^2}\gcd(a,b)\ge\frac1m \sum_{(a,b)\in S^2}\gcd(a,b).$$