MathDB
sum of gcd over sets is more then sum of gcd over union

Source: KoMaL A. 882

June 11, 2024
number theoryGCDgreatest common divisor

Problem Statement

Let H1,H2,…,HmH_1, H_2,\ldots, H_m be non-empty subsets of the positive integers, and let SS denote their union. Prove that ∑i=1m∑(a,b)∈Hi2gcd⁡(a,b)≥1m∑(a,b)∈S2gcd⁡(a,b).\sum_{i=1}^m \sum_{(a,b)\in H_i^2}\gcd(a,b)\ge\frac1m \sum_{(a,b)\in S^2}\gcd(a,b). Proposed by Dávid Matolcsi, Berkeley
Back to ProblemsView on AoPS