Kezdőlap


Feladat:	2003. évi Kürschák matematikaverseny 3. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Füzet:	2004/február, 70 - 72. oldal		PDF \| MathML
Témakör(ök):	Algebrai egyenlőtlenségek, Legnagyobb közös osztó, Prímtényezős felbontás, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):	Feladatok: 2004/február: 2003. évi Kürschák matematikaverseny 3. 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.

I. megoldás. Vizsgáljuk meg, hogy egy rögzített $d$ szám hányszor lép fel $(i; j)$ -ként a feladatbeli összegben! Világos, hogy ha $(i; j) = d$ , akkor $\frac{i}{d}$ és $\frac{j}{d}$ relatív prímek, továbbá mindkettő az $[1; ⌊ \frac{n}{d} ⌋]$ intervallumba esik, ahol $⌊ n ⌋$ az $n$ alsó egészrészét jelöli.
Másfelől, ha $i', j' \in [1; ⌊ \frac{n}{d} ⌋]$ relatív prímek, akkor $i : = i' \cdot d$ , ill. $j : = j' \cdot d$ esetén $(i; j) = d$ és $i, j \in [1; n]$ . A feladatbeli egyenlőtlenség bal oldalán álló mennyiséget $f (n)$ -nel jelölve, a fenti gondolatmenet formálisan az alábbi összeg átrendezése:

\begin{matrix} f (n) : = \sum_{i = 1}^{n} \sum_{j = 1}^{n} (i; j) = \sum_{d = 1}^{n} \sum_{\begin{matrix} (i; j) = d, \\ 1 \leq i \leq n, \\ 1 \leq j \leq n \end{matrix}}^{} d = \sum_{d = 1}^{}^{n} \sum_{\begin{matrix} (i; j) = 1, \\ 1 \leq i \leq \frac{n}{d}, \\ 1 \leq j \leq \frac{n}{d} \end{matrix}}^{} d = \sum_{d = 1}^{n} d \cdot g (\frac{n}{d}), \end{matrix}

(1)

ahol

g (x)

1

és

x

közé eső számokból alkotható relatív prím számpárok száma. A továbbiakban

g (x)

értékét fogjuk megbecsülni, pontosabban igazoljuk, hogy

\begin{matrix} g (x) \geq \frac{x^{2}}{100} . \end{matrix}

(2)

Mivel az

(1; 1)

számpár megfelelő, ezért

x \leq 10

esetén

(2)

triviálisan teljesül. A becslés úgy adódik, hogy az összes számpárok számából minden

d

-re kivonjuk azon számpárok számát, melyeknek

d

közös osztója. Azaz,

\begin{matrix} g (x) \geq {⌊ x ⌋}^{2} - {⌊ \frac{x}{2} ⌋}^{2} - {⌊ \frac{x}{3} ⌋}^{2} - {⌊ \frac{x}{4} ⌋}^{2} - ... > {(\frac{9 x}{10})}^{2} - \frac{x^{2}}{2^{2}} - \frac{x^{2}}{3^{2}} - \frac{x^{2}}{4^{2}} - ... > \\ > & x^{2} (\frac{81}{100} - \frac{1}{4} - (\frac{1}{2 \cdot 3} + \frac{1}{3 \cdot 4} + \frac{1}{4 \cdot 5} ...)) = \\ = & x^{2} (\frac{81}{100} - \frac{1}{4} - (\frac{1}{2} - \frac{1}{3} + \frac{1}{3} - \frac{1}{4} + \frac{1}{4} - \frac{1}{5} ...)) \geq x^{2} (\frac{81}{100} - \frac{1}{4} - \frac{1}{2}) > \frac{x^{2}}{100} . \end{matrix}

A becslést (1)-be helyettesítve azt kapjuk, hogy

\begin{matrix} f (n) = \sum_{d = 1}^{n} d \cdot g (\frac{n}{d}) \geq \sum_{d = 1}^{n} d \cdot \frac{n^{2}}{100 \cdot d^{2}} = \frac{n^{2}}{100} \sum_{d = 1}^{n} \frac{1}{d} \end{matrix}

(3)

Ismert, hogy a harmonikus sor divergens, ezért valamely

N

-re

\sum_{d = 1}^{N} \frac{1}{d} > 400

teljesül (például

N = 2^{800}

megfelel), így

n \geq N

-re (3) alapján

\begin{matrix} \sum_{i = 1}^{n} \sum_{j = 1}^{n} (i; j) = f (n) \geq \frac{n^{2}}{100} \cdot 400 = 4 n^{2}, \end{matrix}

amint azt bizonyítanunk kellett.

□

Megjegyzések. 1. A bizonyításból látható, hogy a feladatbeli becslés jobb oldalán álló

4

-es szorzó tetszőleges konstanssal helyettesíthető azon az áron, hogy megnő az a legnagyobb egész, melyre a feladatbeli egyenlőtlenség még nem teljesül.
2. Mélyebb számelméleti ismereteket felhasználva megmutatható, hogy a megoldásban szereplő

g (x)

függvény aszimptotikusan

\frac{6}{π^{2}} x^{2}

, ahonnan a feladatban szereplő

f (n)

összeg értéke aszimptotikusan

\frac{6}{π^{2}} x^{2} log x

-nek adódik.
3. A legtöbb megoldó a fentinél kevésbé elemi, a prímek reciprokösszegének divergenciájára építő megoldást talált. Az alábbiakban vázoljuk ezt a gondolatmenetet.

II. megoldás. Az

(i; j)

legnagyobb közös osztót az

i

j

számok közös prímosztóinak összegével becsüljük. Legyenek

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

mindazon prímek, melyek az

i

és

j

számokat egyaránt osztják. Mivel bármely szóban forgó prím legalább

2

, ezért

\begin{matrix} (i; j) & \geq p_{1} \cdot p_{2} \cdot ... \cdot p_{k} \geq p_{1} + p_{2} \cdot p_{3} \cdot ... \cdot p_{k} \geq & (4) \\ \geq p_{1} + p_{2} + p_{3} \cdot ... \cdot p_{k} \geq ... \geq p_{1} + p_{2} + ... + p_{k} \end{matrix}

teljesül. Jól ismert, hogy a prímek reciprokösszege

\infty

-hez tart, így létezik olyan

N

szám, melyre az

1

és

N

közti prímek reciprokösszege nagyobb, mint

6

. Ha tehát

n \geq N

, akkor (4) alapján az I. megoldásban definiált

f (n)

-t az alábbi módon becsülhetjük:

\begin{matrix} f (n) & \geq & \sum_{p prím} \sum_{p ∣ (i; j)} p = \sum_{p prím} p \cdot {⌊ \frac{n}{p} ⌋}^{2} \geq \sum_{\begin{matrix} p prím \\ p \leq n \end{matrix}} p {(\frac{n}{p} - 1)}^{2} = \\ = & \sum_{\begin{matrix} p prím \\ p \leq n \end{matrix}} (\frac{n^{2}}{p} - 2 n + p) > - 2 n^{2} + n^{2} \cdot \sum_{\begin{matrix} p prím \\ p \leq n \end{matrix}} \frac{1}{p} \geq - 2 n^{2} + n^{2} \cdot \sum_{\begin{matrix} p prím \\ p \leq N \end{matrix}} \frac{1}{p} \geq \\ \geq & - 2 n^{2} + 6 n^{2} = 4 n^{2} . □ \end{matrix}