Problem A. 882. (May 2024)

A. 882. Let \(\displaystyle H_1\), \(\displaystyle H_2\), \(\displaystyle \ldots\), \(\displaystyle H_m\) be non-empty subsets of the positive integers, and let \(\displaystyle S\) denote their union. Prove that \(\displaystyle \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 \(\displaystyle \sum_{(a,b)\in X}\) notation means that the summation is over ordered pairs \(\displaystyle (a,b)\) where \(\displaystyle a\in X\) and \(\displaystyle b\in X\).)

(Proposed by Dávid Matolcsi, Berkeley)

(7 pont)

Deadline expired on June 10, 2024.

We will use the following well know identity about Euler's totient function \(\displaystyle \varphi\):

\(\displaystyle \sum_{d|n} \varphi(d)=n.\)

Using this

\(\displaystyle \sum_{a, b\in S} \gcd(a, b) = \sum_{a,b\in S} \sum_{d|\gcd(a,b)} = \varphi(d)=\sum_{a,b\in S} \sum_{d|a,d|b} \varphi(d),\)

since exactly those numbers will divide both \(\displaystyle a\) and \(\displaystyle b\), which divide their greatest common divisor. Now let's focus on how many times will \(\displaystyle \varphi(d)\) appear in the sum: we have to count how many ways are there to choose two elements of \(\displaystyle S\) that is divisible by \(\displaystyle d\), which is clearly \(\displaystyle S_d^2\), where \(\displaystyle S_d\) denote the number of elements of \(\displaystyle S\) that is divisible by \(\displaystyle d\). Therefore,

\(\displaystyle \sum_{a, b\in S} \gcd(a, b)=\sum_{d=1}^{\infty} \varphi(d) S_d^2\)

Let \(\displaystyle H_{i,d}\) denote the number of elements in \(\displaystyle H_i\) that is divisible by \(\displaystyle d\), and let's apply the inequality between the arithmetic and the quadratic mean for numbers \(\displaystyle H_{i,d}\) (where \(\displaystyle d\) is fixed and \(\displaystyle i\) is the variable):

\(\displaystyle \frac{\sum_{i=1}^m H_{i,d}^2}{m} \ge \left(\frac{\sum_{i=1}^{m}H_{i,d}}{m}\right)^2\ge \frac{S_d^2}{m^2}.\)

Multiplying the above by \(\displaystyle m\) we get inequality

\(\displaystyle \sum_{i=1}^m H_{i,d}^2\ge \frac{S_d^2}{m}.\)

Now multiplying the above by \(\displaystyle \varphi(d)\) and summing it for all positive integers \(\displaystyle d\) we get

\(\displaystyle \sum_{i=1}^{m} \sum_{a,b\in H_i}\gcd(a,b)=\sum_{i=1}^m\sum_{d=1}^{\infty} \varphi(d)H_{i,d}^2 = \sum_{d=1}^{\infty}\sum_{i=1}^m\varphi(d)H_{i,d}^2\ge \sum_{d=1}^{\infty}\varphi(d)\frac{S_d^2}{m} = \frac{1}{m}\sum_{a,b\in S}\gcd(a,b),\)

and this completes our proof.

Statistics:

8 students sent a solution.
7 points:	Szakács Ábel, Varga Boldizsár.
6 points:	Forrai Boldizsár.
5 points:	1 student.
3 points:	1 student.
1 point:	2 students.
0 point:	1 student.

Problems in Mathematics of KöMaL, May 2024