Kezdőlap


Feladat:	1999. évi Kürschák matematikaverseny 1. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Füzet:	2000/február, 66. oldal		PDF \| MathML
Témakör(ök):	Osztók száma, Osztók összege, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):	Feladatok: 2000/február: 1999. évi Kürschák matematikaverseny 1. feladata

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Jelölje a szóban forgó összegek közül az elsőt $D_{1} (n)$ , a másodikat pedig $D_{2} (n)$ .
$D_{1} (n)$ meghatározásánál minden, az $n$ -nél nem nagyobb pozitív páros számot annyiszor kell figyelembe vennünk, ahány többszöröse van az 1, 2, $...$ , $n$ számok között. Ezért $D_{1} (n) = \sum_{2 j \leq n}^{} s_{n} (2 j)$ , ahol $s_{n} (k)$ jelöli a $k$ pozitív egész 1 és $n$ közé eső többszöröseinek számát: $s_{n} (k) = ⌊ n / k ⌋$ . Hasonlóképpen $D_{2} (n) = \sum_{2 j - 1 \leq n}^{} s_{n} (2 j - 1)$ . Világos, hogy $k < l$ esetén $s_{n} (k) \geq s_{n} (l)$ , így a $D_{1} (n)$ összeg minden egyes $s_{n} (2 j)$ tagját felülről becsülhetjük a $D_{2} (n)$ összeg megfelelő $s_{n} (2 j - 1)$ tagjával. Következésképpen $D_{1} (n) \leq D_{2} (n)$ . Hasonlóképpen, az első tag $s_{n} (1) = n$ kivételével, a $D_{2} (n)$ összeg minden egyes $s_{n} (2 j - 1)$ tagja ( $j \geq 2$ ) megbecsülhető a $D_{1} (n)$ összeg megfelelő $s_{n} (2 (j - 1))$ tagjával, ezért $D_{2} (n) \leq n + D_{1} (n)$ . A két egyenlőtlenség összevetéséből a feladat állítása azonnal leolvasható.

Megjegyzések. 1. A feladatot Pósa Lajos bocsátotta a versenybizottság rendelkezésére.
2. A fenti bizonyítást finomíthatjuk olyan módon, hogy az egyes összegek első néhány tagjára alkalmazzuk az

s_{n} (k) = ⌊ n / k ⌋

képletet, és csak a fennmaradó tagokat becsüljük a másik összeg megfelelő tagjaival. Így a

D_{1} (n) \leq D_{2} (n)

egyenlőtlenség helyett például

n \geq 2

esetén az erősebb

D_{1} (n) - ⌊ \frac{n}{2} ⌋ \leq D_{2} (n) - n

becslést alkalmazhatjuk, ahonnan

⌈ n / 2 ⌉ \leq D_{2} (n) - D_{1} (n) \leq n

következik. Általában tetszőleges

k

pozitív egész számra felírható

n \geq 2 k + 1

esetén a

\begin{matrix} \sum_{j = 1}^{k} ⌊ \frac{n}{2 j - 1} ⌋ - \sum_{j = 1}^{k} ⌊ \frac{n}{2 j} ⌋ \leq D_{2} (n) - D_{1} (n) \leq \sum_{j = 1}^{k + 1} ⌊ \frac{n}{2 j - 1} ⌋ - \sum_{j = 1}^{k} ⌊ \frac{n}{2 j} ⌋ \end{matrix}

egyenlőtlenség, amelyből kiindulva az

ln (k + 1) < 1 + \frac{1}{2} + ... + \frac{1}{k} < 1 + ln k

becslésre támaszkodva nem nehéz megmutatni, hogy a

(D_{2} (n) - D_{1} (n)) / n

sorozat határértéke

ln 2

.
Terpai Tamás dolgozatában azt is megmutatta, hogy a

D_{2} (n) - D_{1} (n)

különbség

n \cdot ln 2

-től való eltérése

\sqrt[]{n}

nagyságrendű. (Erre vonatkozóan lásd még az 1999. decemberi számunk A. 225. számú feladatát.)