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