Kezdőlap


Feladat:	2008. évi Kürschák matematikaverseny 1. feladata	Korcsoport: 16-17	Nehézségi fok: nehéz
Füzet:	2009/február, 67 - 68. oldal		PDF \| MathML
Témakör(ök):	Kürschák József (korábban Eötvös Loránd), Számelmélet alaptétele, Osztók száma függvény, Prímtényezős felbontás
Hivatkozás(ok):	Feladatok: 2009/február: 2008. é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.

Megoldás. Azt a legkisebb $c$ -t keressük, amire $c \geq \frac{d (n)}{\sqrt[]{n}}$ teljesül minden pozitív egész $n$ -re. Tudjuk, hogy ha az $n$ kanonikus alakja $n = p_{1}^{α_{1}} \cdot p_{2}^{α_{2}} \cdot ... \cdot p_{k}^{α_{k}}$ , akkor $n$ osztóinak száma
$d (n) = (α_{1} + 1) (α_{2} + 1) ... (α_{k} + 1)$ . Eszerint

\begin{matrix} c^{2} \geq \frac{d {(n)}^{2}}{n} = \frac{{(α_{1} + 1)}^{2} {(α_{2} + 1)}^{2} ... {(α_{k} + 1)}^{2}}{p_{1}^{α_{1}} \cdot p_{2}^{α_{2}} \cdot ... \cdot p_{k}^{α_{k}}} = \frac{{(α_{1} + 1)}^{2}}{p_{1}^{α_{1}}} \cdot ... \cdot \frac{{(α_{k} + 1)}^{2}}{p_{k}^{α_{k}}} . \end{matrix}

(1)

Ahhoz, hogy a feladatban leírt, lehető legkisebb

c

-t megkeressük, az szükséges, hogy (1) jobb oldalát maximalizáljuk. (Pontosabban az, hogy megtaláljuk a szuprémumát, de mint látni fogjuk, ez itt maximalizálást jelent.) Az (1) formula jobb oldala pedig akkor lesz a lehető legnagyobb, ha minden

p_{i}

prímhez olyan

α_{i} \in {0,1,2, ...}

kitevőt választunk, ami maximalizálja az

\begin{matrix} \frac{{(α_{i} + 1)}^{2}}{p_{i}^{α_{i}}} = \frac{{(2 / 1)}^{2}}{p_{i}} \cdot \frac{{(3 / 2)}^{2}}{p_{i}} \cdot \frac{{(4 / 3)}^{2}}{p_{i}} \cdot ... \cdot \frac{{((α_{i} + 1) / α_{i})}^{2}}{p_{i}} \end{matrix}

(2)

egyenlőség bal oldalát. A (2) jobb oldalán álló törtek számlálója szigorúan monoton csökken, nevezőjük azonos, tehát a szorzatuk akkor lesz maximális, ha

α_{i}

-t úgy választjuk, hogy a szorzatba pontosan az

1

-nél nagyobb

\frac{{((s + 1) / s)}^{2}}{p_{i}}

alakú tényezők kerüljenek. Ha

p_{i} > 4

, akkor már a szorzat első tényezője is egynél kisebb. Ezért ha egy szám kanonikus alakjából elhagyjuk a

4

-nél nagyobb prímosztókat, akkor ettől a

d (n) / \sqrt[]{n}

hányados növekszik. Tehát elegendő csak azokkal a számokkal foglalkoznunk, amiknek a prímosztói csak a

2

és a

3

lehetnek. A

2

és

3

prímosztók maximumot meghatározó kitevőit szintén a fentiek figyelembe vételével kaphatjuk meg; vegyük ugyanis észre, hogy

\begin{matrix} \frac{{(3 / 2)}^{2}}{2} > 1 > \frac{{(4 / 3)}^{2}}{2}, illetve \frac{{(2 / 1)}^{2}}{3} > 1 > \frac{{(3 / 2)}^{2}}{3} . \end{matrix}

Ez azt jelenti, hogy a

\frac{d (n)}{\sqrt[]{n}}

kifejezés

n = 2^{2} \cdot 3 = 12

-re maximális. Tehát a keresett legkisebb

c

érték nem más, mint

\begin{matrix} c = \frac{d (12)}{\sqrt[]{n}} = \frac{3 \cdot 2}{\sqrt[]{4 \cdot 3}} = \frac{3 \cdot 2}{2 \sqrt[]{3}} = \frac{3}{\sqrt[]{3}} = \sqrt[]{3} . □ \end{matrix}

Megjegyzés. A megoldás módszerével megmutatható, hogy tetszőleges pozitív

ε

kitevőre létezik egy olyan

c_{ε}

szám, amire

d (n) \leq c_{ε} \cdot n^{ε}

teljesül minden pozitív egész

n

számra úgy, hogy van olyan pozitív egész

n_{ε}

, amire egyenlőség áll. Ebből az is következik, hogy tetszőleges

ε > 0

esetén

\begin{matrix} {lim}_{n \to \infty}^{} \frac{d (n)}{n^{ε}} = 0. \end{matrix}

Ez úgy is kimondható, hogy

log d (n) / log n \to 0

, ha

n \to \infty

. (Itt feltehető, hogy pl.

e

alapú logaritmusról beszélünk, hisz az (

1

-nél nagyobb) alap sem a konvergencia tényét, sem a határértéket nem befolyásolja.) Megjegyezzük, hogy az az erősebb állítás is igaz, hogy alkalmas

C

konstanssal minden pozitív egész

n

-re:

\begin{matrix} \frac{log d (n)}{log n} < \frac{C}{log log n} . \end{matrix}

Ez a felső becslés pedig már konstans szorzótól eltekintve pontos és nem javítható tovább. Mindez az

n = p_{1} p_{2} ... p_{k}

alakú számokat vizsgálva látható be, ahol

p_{1} < p_{2} < ... < p_{k} < ...

az egymást követő prímek sorozata. Vagyis a fenti egyenlőtlenség lényegében éles, ha

n

az első

k

prím szorzata.