MathDB
Problems
Contests
International Contests
KoMaL A Problems
KoMaL A Problems 2023/2024
A. 882
A. 882
Part of
KoMaL A Problems 2023/2024
Problems
(1)
sum of gcd over sets is more then sum of gcd over union
Source: KoMaL A. 882
6/11/2024
Let
H
1
,
H
2
,
…
,
H
m
H_1, H_2,\ldots, H_m
H
1
,
H
2
,
…
,
H
m
be non-empty subsets of the positive integers, and let
S
S
S
denote their union. Prove that
∑
i
=
1
m
∑
(
a
,
b
)
∈
H
i
2
gcd
(
a
,
b
)
≥
1
m
∑
(
a
,
b
)
∈
S
2
gcd
(
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).
i
=
1
∑
m
(
a
,
b
)
∈
H
i
2
∑
g
cd
(
a
,
b
)
≥
m
1
(
a
,
b
)
∈
S
2
∑
g
cd
(
a
,
b
)
.
Proposed by Dávid Matolcsi, Berkeley
number theory
GCD
greatest common divisor