Az A. 664. feladat (2016. február)

A. 664. Legyen \(\displaystyle a_1<a_2<\ldots<a_n\) pozitív egészekből álló számtani sorozat. Mutassuk meg, hogy

\(\displaystyle [a_1,a_2,\ldots,a_n] \ge [1,2,\ldots,n]. \)

(A \(\displaystyle [\ldots]\) szimbólum a legkisebb közös többszöröst jelöli.)

(5 pont)

A beküldési határidő 2016. március 10-én LEJÁRT.

Megoldás. A megoldás során a baloldalt alulról, a jobboldalt felülről fogjuk becsülni egy-egy, lényegében \(\displaystyle 4^n\) nagyságrendű kifejezéssel.

Jelöljük a sorozat differenciáját \(\displaystyle d\)-vel, azaz \(\displaystyle d=a_2-a_1=\ldots=a_n-a_{n-1}\). Ha az \(\displaystyle a_1,\dots,a_n\) számoknak és \(\displaystyle d\)-nek van \(\displaystyle 1\)-nél nagyobb közös osztója, akkor ezzel végig osztva a számokat, a baloldal csökken. Az állítást tehát elég abban az esetben igazolni, ha az \(\displaystyle a_1,\dots,a_n\) számok relatív prímek \(\displaystyle d\)-hez.

Ha \(\displaystyle d=1\), akkor az \(\displaystyle 1,\ldots,n\) számok mindegyikének van többszöröse \(\displaystyle a_1,\ldots,a_n\) között, így \(\displaystyle [a_1,a_2,\ldots,a_n]\) osztható \(\displaystyle [1,2,\ldots,n]\)-nel, és az állítás triviális.

A továbbiakban feltételezzük, hogy \(\displaystyle d\ge2\), és az \(\displaystyle a_1,\ldots,a_n\) számok relatív prímek \(\displaystyle d\)-hez.

Tetszőleges \(\displaystyle x\) nemnulla egész és \(\displaystyle p\) prímszám esetén \(\displaystyle v_p(x)\) jelöli a \(\displaystyle p\) kitevőjét az \(\displaystyle x\) prímtényezős felbontásában.

Az \(\displaystyle [1,2,\ldots,n]\) felső becslése

Legyen \(\displaystyle L_n=[1,2,\ldots,n]\). Azt mutatjuk meg, hogy

A \(\displaystyle L_n<4^n\) alakú becslések és élesítéseik jól ismertek, bár a legtöbb bevezető számelmélet-tankönyv csak az \(\displaystyle n\)-nél nem nagyobb prímszámok szorzatát becsüli felülről \(\displaystyle 4^n\)-nel.

Az \(\displaystyle L_n\) szám nem más, mint az \(\displaystyle n\)-nél nem nagyobb, maximális prímhatványok szorzata:

\(\displaystyle L_n = [1,2,\ldots,n] = \prod_{p^\ell\le n <p^{\ell+1}} p^\ell = \prod_{p^\ell\le n} p. \)

A Legendre-formula jól ismert következménye, hogy \(\displaystyle v_p\left(\binom{2k}{k}\right) = \sum\limits_{\ell=1}^\infty \left( \bigg[\frac{2k}{p^\ell}\bigg]- 2\bigg[\frac{k}{p^\ell}\bigg]\right)\), és a zárójelben álló szám minden esetben \(\displaystyle 0\) vagy \(\displaystyle 1\). Ha van olyan \(\displaystyle \ell\) kitevő, amelyre \(\displaystyle k<p^\ell\le 2k\), akkor az ehhez tartozó zárójelben \(\displaystyle 1\) áll, ilyenkor tehát \(\displaystyle p\big| \binom{2k}{k}\). Ezért

\(\displaystyle \prod_{k<p^\ell\le 2k} p \,\,\bigg|\,\, \binom{2k}{k}. \)

A \(\displaystyle k\) szerinti indukcióval könnyen ellenőrizhető, hogy \(\displaystyle k\ge5\) esetén \(\displaystyle \binom{2k}{k}<4^{k-1}\), és így

\(\displaystyle \prod_{k<p^\ell\le 2k} p \le \binom{2k}{k} < 4^{k-1} \quad(k\ge5). \)

Ebből az (A) állítást \(\displaystyle n\) szerinti indukcióval igazolhatjuk. Az \(\displaystyle n\le8\) eseteket kézzel ellenőrizhetjük:

Ha \(\displaystyle n\ge 10\) páros, \(\displaystyle n=2k\), és az indukciós feltevés teljesül \(\displaystyle k\)-ra, akkor

\(\displaystyle L_n = \prod_{p^\ell\le n} p = \prod_{p^\ell\le k} p \cdot \prod_{k< p^\ell\le 2k} p < 4^{k-2} \cdot 4^{k-1} < 4^{n-2}. \)

Ha pedig \(\displaystyle n\ge 9\) páratlan, \(\displaystyle n=2k-1\), akkor

\(\displaystyle L_n = \prod_{p^\ell\le n} p = \prod_{p^\ell\le k} p \cdot \prod_{k< p^\ell\le 2k-1} p < 4^{k-2} \cdot 4^{k-1} = 4^{n-2}. \)

Az \(\displaystyle [a_1,a_2,\ldots,a_n]\) alsó becslése

Azt fogjuk igazolni, hogy

Ez \(\displaystyle n\le2\)-re semmitmondó; feltesszük, hogy \(\displaystyle n\ge3\).

Lemma. Ha \(\displaystyle b_0<b_1<\ldots<b_m\) pozitív egészekből álló, \(\displaystyle d\) differenciájú számtani sorozat, amelyben az elemek relatív prímek \(\displaystyle d\)-hez, akkor

Bizonyítás. Azt fogjuk igazolni, hogy a két oldal hányadosa egész szám, így legalább \(\displaystyle 1\). (Azt is könnyű igazolni, hogy a jobboldal egész szám, de erre nem lesz szükségünk.) Vegyünk egy tetszőleges \(\displaystyle p\) prímet, ami osztója \(\displaystyle b_0,b_1,\ldots,b_m\) valamelyikének; a \(\displaystyle p\) kitevőjét akarjuk összehasonlítani a két oldal prímtényezős felbontásában. Legyen \(\displaystyle b_0,b_1,\ldots,b_m\) között \(\displaystyle b_k\) az egyik olyan, amelynek prímtényezős felbontásában a \(\displaystyle p\) maximális kitevővel szerepel.

Vegyük észre, hogy bármely, \(\displaystyle k\)-tól különböző \(\displaystyle 0\le i\le m\) indexre \(\displaystyle b_i=b_k+(i-k)d\)-ben a \(\displaystyle p\) kitevője pontosan akkora, mint \(\displaystyle i-k\) prímfelbontásában. Ez triviális akkor, ha \(\displaystyle v_p\big(i-k\big)<v_p(b_k)\); ha pedig \(\displaystyle v_p\big(i-k\big)= v_p(b_k)\), akkor \(\displaystyle v_p(b_i)\ge v_p(b_k)\), de a \(\displaystyle k\) definíciója miatt \(\displaystyle v_p(b_i)\le v_p(b_k)\) is teljesül. Végül \(\displaystyle v_p(i-k)>v_p(b_k)\) nem lehetséges, mert a \(\displaystyle b_i,\ldots,b_k\) számok között van olyan \(\displaystyle b_j\), ami osztható \(\displaystyle p^{v_p(i-k)}\)-vel. Ezért \(\displaystyle v_p(b_i)=v_p\big(i-k\big)=v_p\big(|i-k|\big)\) minden \(\displaystyle i\ne k\) esetén, így

\(\displaystyle v_p\big( [b_0,\ldots,b_m] \big) = v_p(b_k) = v_p\big(b_0\ldots b_m\big) - v_p\big( b_0\ldots b_{k-1} \cdot b_{k+1}\ldots b_m\big) = \)

\(\displaystyle = v_p\big(b_0\ldots b_m\big) - v_p\big(k!\cdot (m-k)!\big) \ge v_p\big(b_0\ldots b_m\big) - v_p\big( m! ). \)

(Az utolsó becslés azért igaz, mert \(\displaystyle \frac{m!}{k!(m-k)!}=\binom{m}{k}\) egész szám.) Ezzel a lemmát igazoltuk.

A lemma egy másik bizonyítása: ahogy az A. 652. feladat megoldásában láttuk,

\(\displaystyle \sum_{k=0}^m (-1)^k\frac{\binom{m}{k}}{b_k} = \frac{d^m \cdot m!}{b_0b_1\ldots b_m}. \)

A baloldalon álló törteknek \(\displaystyle [b_0,\ldots,b_m]\) egy közös nevezője; a jobboldalon a nevező relatív prím \(\displaystyle d\)-hez.

A továbblépéshez szükségünk van annak megbecslésére, hogy milyen nagy az \(\displaystyle m!\) ,,\(\displaystyle d\)-vel nem relatív prím része''. Minden egyes \(\displaystyle k\) kitevőre az \(\displaystyle 1,2,\ldots,m\) számok között \(\displaystyle \left[\frac{m}{d^k}\right]\) olyan van, ami osztható \(\displaystyle d^k\)-nal; ezért -- a Legendre-formulához hasonlóan -- \(\displaystyle m!\) osztható a \(\displaystyle d^{\left[\frac{m}{d}\right]+\left[\frac{m}{d^2}\right]+\left[\frac{m}{d^3}\right]+\cdots}\) számmal. A kitevőt megbecsüljük alulról:

\(\displaystyle \sum_{k=1}^\infty\left[\frac{m}{d^k}\right] \ge \sum_{k=1}^{[\log_d m]} \left(\frac{m+1}{d^k}-1\right) = \frac{m+1}{d} \cdot \frac{1-\frac1{d^{[\log_d m]}}}{1-\frac1d} - [\log_d m] \ge^{*} \)

\(\displaystyle \ge \frac{m+1}{d} \cdot \frac{1-\frac{d}{m+1}}{1-\frac1d} - \log_d m = \frac{m}{d-1} -1 -\log_dm . \)

(\(\displaystyle {}^{*}\)Vegyük észre, hogy \(\displaystyle d^{[\log_d m]+1}\ge m+1\), így \(\displaystyle d^{[\log_d m]}\ge \frac{m+1}{d}\).) Ezért

\(\displaystyle d^{\sum\limits_{k=1}^\infty \left[\frac{m}{d^k}\right]} \ge \frac{d^{\frac{m}{d-1}-1}}{m} > \frac{d^{\frac{m}{d-1}-1}}{m+1}, \)

A (2) becslést írjuk fel az \(\displaystyle a_2,\ldots,a_n\) számokra (tehát \(\displaystyle m=n-2\)). Alkalmazzuk az \(\displaystyle a_k>(k-1)d\) becslést is:

\(\displaystyle [a_1,\ldots,a_n] \ge [a_2,\ldots,a_n] > \frac{a_2\ldots a_n}{(n-1)!} \cdot d^{\frac{n-2}{d-1}-1} > \frac{d\cdot 2d \cdot\ldots\cdot (n-1)d}{(n-1)!} \cdot d^{\frac{n-2}{d-1}-1} = \Big(d^{\frac{d}{d-1}}\Big)^{n-2}. \)

Végül, minden \(\displaystyle d\ge2\)-re igaz, hogy \(\displaystyle d^{\frac{d}{d-1}}\ge4\). Ha \(\displaystyle d=2\), akkor \(\displaystyle d^{\frac{d}{d-1}}=4\); ha \(\displaystyle d=3\), akkor \(\displaystyle d^{\frac{d}{d-1}}=\sqrt{27}>4\); ha \(\displaystyle d\ge 4\), akkor \(\displaystyle d^{\frac{d}{d-1}}>d\ge4\). Ezzel bebizonyítottuk (B)-t.

Befejezés

Az (A) és (B) becslések szerint, ha \(\displaystyle n\ge4\), akkor

\(\displaystyle [a_1,\ldots,a_n] > 4^{n-2} > [1,\ldots,n], \)

vagyis az állítás teljesül.

Ha \(\displaystyle n\le 2\), akkor \(\displaystyle [a_1,\ldots,a_n]\ge a_n \ge n = L_n\).

Ha \(\displaystyle n=3\), akkor \(\displaystyle a_2\) és \(\displaystyle a_3\) relatív prímek, és így \(\displaystyle [a_1,a_2,a_3] \ge [a_2,a_3]=a_3a_5\ge 3\cdot 5=15>6=L_3\).

Megjegyzések. 1. A (2) becslést nem az összes \(\displaystyle [a_1,\ldots,a_n]\) számra alkamaztuk, mivel az \(\displaystyle a_1\)-re nincs használható alsó becslésünk; akár \(\displaystyle a_1=1\) is megengedett. Érdemes végiggondolni, mi történik, ha még kevesebb számot használunk a becsléshez: valamilyen \(\displaystyle m<n\) egésszel

\(\displaystyle [a_1,\ldots,a_n] \ge [a_{n-m},\ldots,a_n] > \frac{a_{n-m}\ldots a_n}{(m+1)!} \cdot d^{\frac{m}{d-1}-1} > \frac{(n-m)d\cdot\ldots\cdot (n-1)d}{(m+1)!} \cdot d^{\frac{m}{d-1}-1} = \binom{n-1}{m+1} \Big(d^{\frac{d}{d-1}}\Big)^{m}. \)

Az \(\displaystyle m\) megfelelő választásával (vagy az összes \(\displaystyle m\)-re kapott becslések átlagolásával) a (B) egyenlőtlenség jobboldalán a \(\displaystyle 4\)-es alap \(\displaystyle (5-\varepsilon)\)-ra növelhető.

2. Ismert, hogy tetszőlegesen kicsi \(\displaystyle \varepsilon>0\) esetén, ha \(\displaystyle n\) elég nagy \(\displaystyle n\), akkor \(\displaystyle e^{(1-\varepsilon)n} < L_n < e^{(1+\varepsilon)n}\); más szóval \(\displaystyle \lim \frac{\log L_n}{n}=1\); ez a prímszámtétel egyik ekvivalens alakja.

Statisztika:

5 dolgozat érkezett.
5 pontot kapott:	Williams Kada.
4 pontot kapott:	Bukva Balázs.
2 pontot kapott:	2 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2016. februári matematika feladatai