Problem B. 5405. (September 2024)

B. 5405. Positive integers \(\displaystyle a_1,a_2,\ldots,a_n\) and \(\displaystyle b_1,b_2,\ldots,b_n\) satisfy the following property: for all indices \(\displaystyle i < j \leq n\) the greatest common divisor of \(\displaystyle b_i\) and \(\displaystyle b_j\) does not divide difference \(\displaystyle (a_i-a_j)\). Prove that \(\displaystyle \displaystyle \sum_{i=1}^n \frac1{b_i} \leq 1\).

Proposed by Boldizsár Varga, Budapest

(6 pont)

Deadline expired on October 10, 2024.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Legyen \(\displaystyle N=b_1b_2\dots b_n\), és tekintsük az \(\displaystyle S:=\{1,2,\dots,N\}\) halmazt. Az \(\displaystyle 1\leq i\leq n\) indexre álljon \(\displaystyle S_i\) azokból az \(\displaystyle s\in S\) elemekből, melyekre \(\displaystyle b_i\mid s-a_i\) teljesül. Az \(\displaystyle S_i\) halmazt tehát az \(\displaystyle a_i\)-vel egyező modulo \(\displaystyle b_i\) maradékosztályba eső \(\displaystyle S\)-beli elemek alkotják, így \(\displaystyle |S_i|=|S|/b_i\), hiszen \(\displaystyle b_i\mid N\).

Azt állítjuk, hogy az \(\displaystyle S_i\) halmazok páronként diszjunktak. Tegyük fel ugyanis, hogy valamely \(\displaystyle i<j\leq n\) indexekre \(\displaystyle s\in S_i\cap S_j\). Ekkor \(\displaystyle b_i\mid s-a_i\) és \(\displaystyle b_j\mid s-a_j\) miatt \(\displaystyle (b_i,b_j)\mid(s-a_j)-(s-a_i)=a_i-a_j\) ellentmond a feladat feltételének.

Tehát az \(\displaystyle S_1,\dots,S_n\) halmazok az \(\displaystyle S\) halmaz páronként diszjunkt részhalmazai, így \(\displaystyle \sum\limits_{i=1}^n |S_i|\leq |S|\), amiből \(\displaystyle |S|=N\)-nel való leosztás után éppen a bizonyítandó egyenlőtlenséget kapjuk.

Megjegyzés. A feladat állítása éles. Ha \(\displaystyle n=1\), akkor például az \(\displaystyle a_1=b_1=1\), ha pedig \(\displaystyle n\geq 2\), akkor például az \(\displaystyle a_1=1,a_2=2,\dots,a_n=n\), \(\displaystyle b_1=2(n-1),b_2=\dots=b_{n-1}=n-1, b_n=2(n-1)\) választás megfelelő, és egyenlőség teljesül.

Statistics:

10 students sent a solution.
6 points:	Aravin Peter, Diaconescu Tashi, Forrai Boldizsár, Görömbey Tamás, Holló Martin, Prohászka Bulcsú, Vigh 279 Zalán.
5 points:	Wágner Márton.
0 point:	2 students.

Problems in Mathematics of KöMaL, September 2024