Az A. 838. feladat (2022. november)

A. 838. Az \(\displaystyle X\subset \mathbb{Z}^{+}\) és \(\displaystyle Y\subset \mathbb{Z}^{+}\) halmazokat bajtársiasnak nevezzük, ha minden pozitív egész \(\displaystyle n\) előáll \(\displaystyle n=xy\) alakban, ahol \(\displaystyle x\in X\) és \(\displaystyle y\in Y\). Jelöljük \(\displaystyle X(n)\)-nel és \(\displaystyle Y(n)\)-nel azt, hogy az \(\displaystyle X\) és \(\displaystyle Y\) halmazoknak hány eleme van az első \(\displaystyle n\) pozitív egész között.

Legyen \(\displaystyle f\colon \mathbb{Z}^{+}\to \mathbb{R}^{+}\) egy tetszőleges végtelenbe tartó függvény. Bizonyítsuk be, hogy léteznek olyan \(\displaystyle X\) és \(\displaystyle Y\) bajtársias halmazok, hogy \(\displaystyle \frac{X(n)}{n}\) és \(\displaystyle \frac{Y(n)}{n}\) is a \(\displaystyle 0\)-hoz tartanak, és tetszőleges \(\displaystyle \varepsilon>0\)-ra létezik olyan \(\displaystyle n \in \mathbb{Z}^+\), hogy

\(\displaystyle \frac{\min\big\{X(n), Y(n)\big\}}{f(n)}<\varepsilon. \)

(7 pont)

A beküldési határidő 2022. december 12-én LEJÁRT.

1. Lemma:

\(\displaystyle \prod_{p} \frac{p-1}{p}=0\)

ha a produktum az összes prímszámon végigfut.

Bizonyítás:

Legyen \(\displaystyle p_1, p_2, \ldots p_n\) az első \(\displaystyle n\) prímszám.

\(\displaystyle \prod_{i=1}^{n} \frac{p_i-1}{p}=\frac{1}{\prod_{i=1}^{n} \frac{p}{p-1}}=\frac{1}{\prod_{i=1}^{n} (1+\frac{1}{p}+\frac{1}{p^2}+\ldots)}\)

\(\displaystyle \prod_{i=1}^{n} (1+\frac{1}{p}+\frac{1}{p^2}+\ldots)\) szorzatot kibontva azt kapjuk, hogy ez azon számok reciprokösszege, amik előállnak \(\displaystyle p_i\) hatványok szorzataként, ahol a \(\displaystyle p_i\) prímtényzeők az első \(\displaystyle n\) prím közül kerülnek ki. Mivel minden \(\displaystyle p_n\)-nél kisebb-egyenlő szám előáll \(\displaystyle p_i\) hatványok szorzataként, ezért

\(\displaystyle \prod_{i=1}^{n} (1+\frac{1}{p}+\frac{1}{p^2}+\ldots)\ge \sum_{k=1}^{p_n} \frac{1}{k}.\)

A számok reciprokösszege közismerten végtelen, tehát \(\displaystyle \prod_{i=1}^{n} (1+\frac{1}{p}+\frac{1}{p^2}+\ldots)\) tart a végtelenhez, tehát a reciproka, \(\displaystyle \prod_{i=1}^{n} \frac{p_i-1}{p}\) tart a \(\displaystyle 0\)-hoz, vagyis definíció szerint

\(\displaystyle \prod_{p} \frac{p-1}{p}=0.\)

2. Lemma

Legyen \(\displaystyle P\) prímek egy végtelen halmaza, amire \(\displaystyle \prod_{p\in P} \frac{p-1}{p}=0\). Legyen \(\displaystyle S\) azon számok halmaza, amik nem oszthatók semelyik \(\displaystyle P\)-beli prímmel. Ekkor \(\displaystyle \frac{S(n)}{n}\) tart a \(\displaystyle 0\)-hoz.

Bizonyítás:

Legyen \(\displaystyle \varepsilon>0\) rögzített. Legyenek \(\displaystyle p_1, p_2,\ldots p_N\) a legkisebb prímek \(\displaystyle P\)-ben. Mivel \(\displaystyle \prod_{p\in P} \frac{p-1}{p}=0\), ezért választhatjuk \(\displaystyle N\)-et elég nagyra, hogy \(\displaystyle \prod_{i=1}^N \frac{p_i-1}{p_i}<\frac{\varepsilon}{2}\).

Kínai maradéktétel szerint \(\displaystyle 1\)-től \(\displaystyle Kp_1p_2\ldots p_N\)-ig \(\displaystyle K(p_1-1)(p_2-1)\ldots (p_N-1)<\frac{\varepsilon}{2} Kp_1p_2...p_n\) olyan szám van, ami nem osztható a \(\displaystyle p_1, p_2,\ldots p_n\) prímek egyikével sem, tehát van esélye, hogy benne legyen \(\displaystyle S\)-ben.

Legyen \(\displaystyle n>\frac{2}{\varepsilon}p_1p_2\ldots p_N\). Legyen \(\displaystyle K\) az asló egészrésze \(\displaystyle \frac{n}{p_1p_2\ldots p_N}\)-nek.

Ekkor

\(\displaystyle S(n)\le K(p_1-1)(p_2-1)\ldots (p_N-1)+n-Kp_1p_2\ldots p_N<\frac{\varepsilon}{2} Kp_1p_2\ldots p_n+p_1p_2\ldots p_n<\varepsilon Kp_1p_2\ldots p_n\le \varepsilon n\)

Ezzel beláttuk, hogy minden \(\displaystyle \varepsilon>0\)-ra igaz, hogy kellően nagy \(\displaystyle n\)-re \(\displaystyle \frac{S(n)}{n}<\varepsilon\), vagyis \(\displaystyle \frac{S(n)}{n}\) tart a \(\displaystyle 0\)-hoz.

3. Lemma:

Legyen \(\displaystyle S\) pozitív egészek egy olyan halmaz, amire \(\displaystyle \frac{S(n)}{n}\) tart a \(\displaystyle 0\)-hoz. Legyen \(\displaystyle Y\) az olyan pozitív egészek halmaza, amik felírhatók \(\displaystyle sm^2\) alakban, ahol \(\displaystyle s\in S\) és \(\displaystyle m\) egész szám. Ekkor \(\displaystyle \frac{Y(n)}{n}\) is tart a \(\displaystyle 0\)-hoz.

Bizonyítás:

\(\displaystyle Y_m\)-nek nevezem azon \(\displaystyle y\in Y\) számok halmazát, amikre \(\displaystyle m\) a legkisebb egész, hogy \(\displaystyle \frac{y}{m^2}\in S\). Ekkor \(\displaystyle Y_1, Y_2,\ldots \) diszjunkt halmazok, és az uniójuk \(\displaystyle Y\).

\(\displaystyle Y_m(n)\) kisebb-egyenlő, mint az olyan \(\displaystyle y\in Y, y\le n\) számok száma, amikre \(\displaystyle \frac{y}{m^2}\in S\). Tehát \(\displaystyle |Y_m(n)|\le S(\frac{n}{m^2}).\)

Ebből az következik, hogy

\(\displaystyle Y(n)\le \sum_{m=1}^{\infty} S\left(\frac{n}{m^2}\right)\)

Legyen \(\displaystyle \varepsilon>0\) konstans. Mivel \(\displaystyle \sum_{m=1}^{\infty} \frac{1}{m^2}\) véges, ezért létezik \(\displaystyle M\), amire \(\displaystyle \sum_{m=M}^{\infty} \frac{1}{m^2}<\frac{\varepsilon}{2}\).

Továbbá, mivel \(\displaystyle \frac{S(n)}{n}\) a \(\displaystyle 0\)-hoz tart, ezért kellően nagy \(\displaystyle n\)-re teljesül, hogy \(\displaystyle m<M\)-re \(\displaystyle S(\frac{n}{m^2})<\frac{\varepsilon}{8}\frac{n}{m^2}\).

Tehát kellően nagy \(\displaystyle n\)-re

\(\displaystyle Y(n)\le \sum_{m=1}^{M-1} S\left(\frac{n}{m^2}\right)+\sum_{m=M}^{\infty} S\left(\frac{n}{m^2}\right)< \frac{\varepsilon}{8} \sum_{m=1}^{M-1} \frac{n}{m^2}+n\left(\sum_{m=M}^{\infty} \frac{1}{m^2}\right)<n\left(\frac{\varepsilon}{8}\sum_{m=1}^{M-1} \frac{1}{m^2}+\frac{\varepsilon}{2}\right) \)

Mivel

\(\displaystyle \sum_{m=1}^{M-1} \frac{1}{m^2}<\sum_{m=1}^{\infty} \frac{1}{m^2}<4,\)

ezért \(\displaystyle Y(n)<\varepsilon n\) kellően nagy \(\displaystyle n\)-re. Ez minden \(\displaystyle \varepsilon>0\)-ra igaz, tehát \(\displaystyle \frac{Y(n)}{n}\) tart a \(\displaystyle 0\)-hoz.

Ezeknek a lemmáknak a felhasználásával most létrehozunk megfelelő \(\displaystyle X\) és \(\displaystyle Y\) bajtársias halmazokat.

Létrehozzuk a prímek egy végtelen \(\displaystyle P\) halmazát egy iteratív módon. Legyen \(\displaystyle P_1=\{2\}\). Ezután \(\displaystyle P_{k+1}\) mindig \(\displaystyle P_k\) bővítése az alábbi módon:

Legyen \(\displaystyle |P_k|=t_k\). Mivel \(\displaystyle f\) a végtelenbe tart, létezik olyan \(\displaystyle r\) érték, amire \(\displaystyle f(r)\ge 2^{2t_k}\). Választunk egy ilyen \(\displaystyle r\)-et, amire egyben az is teljesül, hogy \(\displaystyle r>\prod_{p\in P_k} p\). Nevezzük ezt \(\displaystyle r_k\)-nak.

\(\displaystyle P_{k+1}\)-et úgy képezzük, hogy \(\displaystyle P_k\)-hoz hozzávesszük az első \(\displaystyle h\) prímszámot, amik nagyobbak \(\displaystyle r_k\)-nál. Nevezzük őket \(\displaystyle q_1, q_2,\ldots , q_h\)-nak. \(\displaystyle h\)-t olyan nagyra választjuk meg, hogy

\(\displaystyle \prod_{i=1}^h \frac{q_i-1}{q_1}<\frac{1}{2}.\)

Mivel az 1. Lemma szerint az összes prímre nézve a \(\displaystyle \prod \frac{p-1}{p}\) szorzat tart a \(\displaystyle 0\)-hoz, ezért tetszőleges \(\displaystyle r\)-re igaz, hogy az \(\displaystyle r\)-nél nagyobb prímekre is \(\displaystyle 0\)-hoz kell tartania a szorzatnak, vagyis létezik elég nagy \(\displaystyle h\), amire teljesül a feltétel.

Miután iteratív bővítésekkel létrehoztuk a \(\displaystyle P\) prím-halmazt, legyen \(\displaystyle X\) azon négyzetmentees számok halmaza, amiknek csak \(\displaystyle P\)-beli prímosztói vannak.

Ekkor tetszőleges \(\displaystyle k\)-ra teljesül, hogy \(\displaystyle X(r_k)\)-ban pontosan a \(\displaystyle P_k\)-ban szereplő prímekből alkotható négyzetmentes szorzatok szerepelnek, ugyanis \(\displaystyle r_k>\prod_{p\in P_k} p\). Mivel \(\displaystyle |P_k|=t_k\), ezért az ilyen négyzetmentes szorzatok száma \(\displaystyle 2^{t_k}\).

Másrészt \(\displaystyle f(r_k)>2^{2t_k}\), tehát

\(\displaystyle \frac{X(r_k)}{f(r_k)}<\frac{1}{2^{t_k}}.\)

\(\displaystyle t_k\) tart a végtelenhez, így \(\displaystyle \frac{1}{2^{t_k}}\) tart a \(\displaystyle 0\)-hoz, tehát tetszőleges \(\displaystyle \varepsilon>0\)-ra létezik \(\displaystyle n=r_k\), amire

\(\displaystyle \frac{\min\{X(n),Y(n)\}}{f(n)}\le \frac{X(n)}{f(n)}<\varepsilon.\)

A \(\displaystyle P\) halmazt úgy konstruáltuk, hogy \(\displaystyle \prod_{p\in P} \frac{p-1}{p}=0\) legyen.

Legyen \(\displaystyle S\) az olyan számok halmaza, amik nem oszthatók semelyik \(\displaystyle P\)-beli prímmel. Ekkor a 2. Lemma szerint \(\displaystyle \frac{S(n)}{n}\) tart a \(\displaystyle 0\)-hoz.

Legyen \(\displaystyle Y\) az olyan pozitív egészek halmaza, amik felírhatók \(\displaystyle sm^2\) alakban, ahol \(\displaystyle s\in S\) és \(\displaystyle m\) egész szám. A 3. Lemma szerint \(\displaystyle \frac{Y(n)}{n}\) is tart a \(\displaystyle 0\)-hoz.

Minden pozitív egész \(\displaystyle n\) felírható \(\displaystyle n=m^2sx\) alakban, ahol \(\displaystyle m\) egész, \(\displaystyle s\) és \(\displaystyle x\) pedig négyzetmentes számok, ahol \(\displaystyle s\)-nek csak \(\displaystyle P\)-n kívüli, \(\displaystyle x\)-nek pedig csak \(\displaystyle P\)-n belüli prímtényezői vannak. Tehát minden pozitív egész felírható egy \(\displaystyle m^2s\in Y\) és egy \(\displaystyle x\in X\) szám szorzataként, vagyis \(\displaystyle X\) és \(\displaystyle Y\) bajtársias halmazok.

Ha \(\displaystyle r_k\) meghatározásánál még azt is kikötjük, hogy \(\displaystyle P_k\) legnagyobb eleme és \(\displaystyle r_k\) közötti \(\displaystyle q\) prímekre \(\displaystyle \prod \frac{q-1}{q}<\frac{1}{2}\) legyen, azzal azt is biztosítjuk, hogy \(\displaystyle \frac{X(n)}{n}\) is mindenképp a \(\displaystyle 0\)-hoz tartson, hiszen \(\displaystyle X\) elemei nem oszthatók ezekkel a \(\displaystyle q\) prímekkel, így hivatkozhatunk a 2. Lemmára.

Tehát az így kapott \(\displaystyle X\) és \(\displaystyle Y\) megfelelő bajtársias halmazok.

Forrás: Ez a probléma és a bizonyítás egy egyszerűbb tételként szerepel Kocsis Anett, Matolcsi Dávid, Sándor Csaba és Tőtős György hamarosan megjelenő, Multiplicative Complements II cikkében.

Statisztika:

5 dolgozat érkezett.
7 pontot kapott:	Varga Boldizsár.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2022. novemberi matematika feladatai