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