A B. 5405. feladat (2024. szeptember)

B. 5405. Az \(\displaystyle a_1\), \(\displaystyle a_2\), \(\displaystyle \ldots\), \(\displaystyle a_n\) és \(\displaystyle b_1\), \(\displaystyle b_2\), \(\displaystyle \ldots\), \(\displaystyle b_n\) pozitív egész számokra teljesül, hogy bármely \(\displaystyle i<j\leq n\) indexekre \(\displaystyle b_i\) és \(\displaystyle b_j\) legnagyobb közös osztója nem osztója \(\displaystyle (a_i-a_j)\)-nek. Mutassuk meg, hogy \(\displaystyle \displaystyle \sum_{i=1}^n \frac1{b_i} \leq 1\).

Javasolta: Varga Boldizsár, Budapest

(6 pont)

A beküldési határidő 2024. október 10-én LEJÁRT.

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.

Statisztika:

10 dolgozat érkezett.
6 pontot kapott:	Aravin Peter, Diaconescu Tashi, Forrai Boldizsár, Görömbey Tamás, Holló Martin, Prohászka Bulcsú, Vigh 279 Zalán.
5 pontot kapott:	Wágner Márton.
0 pontot kapott:	2 versenyző.

A KöMaL 2024. szeptemberi matematika feladatai