Az A. 624. feladat (2014. október)

A. 624. \(\displaystyle a)\) Bizonyítsuk be, hogy tetszőleges \(\displaystyle x_1,x_2,\ldots\in[0,1]\) végtelen számsorozathoz létezik olyan \(\displaystyle C>0\) szám, hogy bármely \(\displaystyle r\) pozitív egészhez vannak olyan \(\displaystyle n\), \(\displaystyle m\) pozitív egészek, amikre

\(\displaystyle |n-m|\ge r \quad\text{és}\quad |x_n-x_m|<\frac{C}{|n-m|}. \)

\(\displaystyle b)\) Mutassuk meg, hogy minden olyan \(\displaystyle C>0\) számhoz létezik olyan \(\displaystyle x_1,x_2,\ldots \in[0,1]\) végtelen számsorozat és olyan \(\displaystyle r\) pozitív egész, hogy

\(\displaystyle |x_n-x_m|>\frac{C}{|n-m|} \)

teljesül minden olyan \(\displaystyle n\), \(\displaystyle m\) pozitív egész párra, amikre \(\displaystyle |n-m|\ge r\).

CIIM6, Costa Rica

(5 pont)

A beküldési határidő 2014. november 10-én LEJÁRT.

1. megoldás az (a) részre.

Az első két megoldásban felhasználjuk a következő előkészítő lépést.

1. lemma. Tegyük fel, hogy létezik egy olyan \(\displaystyle x_1,x_2,\ldots\in[0,1]\) sorozat, amire a feladat állítása nem teljesül, azaz bármely \(\displaystyle C>0\) számhoz van olyan \(\displaystyle r(C)\) pozitív egész, hogy bármely \(\displaystyle n,m\ge 1\) indexekre, amikre \(\displaystyle |n-m|\ge r\), igaz, hogy \(\displaystyle |x_n-x_m|\ge \frac{C}{|n-m|}\). Ekkor a sorozatnak létezik olyan \(\displaystyle y_1,y_2,\ldots\) részsorozata, ami szintén ellentmond a feladat állításának, és létezik hozzá olyan \(\displaystyle c>0\) pozitív szám, hogy tetszőleges, egymástól különböző \(\displaystyle n,m\) indexekre \(\displaystyle |y_n-y_m|\ge\frac{c}{|n-m|}\).

Bizonyítás. Legyen \(\displaystyle p=r(1)\), és tekintsük az \(\displaystyle y_n=x_{pn}\) sorozatot. Az \(\displaystyle (y_n)\) sorozat is ellentmond a feladat állításának: tetszőleges \(\displaystyle C>0\) és \(\displaystyle |n-m|>r(pC)\) esetén

\(\displaystyle |y_n-y_m| = | x_{pn}-x_{pm} | \le \frac{pC}{|pn-pm|} = \frac{C}{|n-m|}. \)

A második állítás például a \(\displaystyle c=1/p\) választással teljesül: ha \(\displaystyle n,m\) különböző indexek, akkor \(\displaystyle |pn-pm|\ge p=r(1)\), és így

\(\displaystyle |y_n-y_m| = | x_{pn}-x_{pm} | \ge \frac1{|pn-pm|} = \frac{1/p}{|n-m|} = \frac{c}{|n-m|}. \)

Ezzel a Lemma kész.

A feladat megoldásához minden \(\displaystyle r>0\) valós számra legyen

Ez a függvény monoton nő, mert ha \(\displaystyle r\)-et növeljük, akkor a jobboldalon álló halmazt egy részhalmazára szűkítjük, és így a halmaz imfimuma nem csökken.

Ha valamilyen \(\displaystyle r\)-re és \(\displaystyle C\) számra \(\displaystyle K(r)<C\), akkor \(\displaystyle C\) nem alsó korlátja az (*) jobboldalán álló halmaznak, így vannak olyan \(\displaystyle n,m\) indexek, amelyekre \(\displaystyle |n-m|\ge r\) és \(\displaystyle |x_n-x_m|\cdot|n-m|<C\). Ha pedig \(\displaystyle C\le K(r)\), akkor \(\displaystyle C\) alsó korlátja a halmaznak, így bármely \(\displaystyle n,m\) indexpárra \(\displaystyle |n-m|\ge r\) esetén \(\displaystyle |x_n-x_m|\cdot|n-m|\ge C\). A feladat állítása ezért azzal ekvivalens, hogy van olyan \(\displaystyle C\) szám, hogy \(\displaystyle K(r)<C\) teljesül minden \(\displaystyle r\)-re; más szóval, a \(\displaystyle K\) függvény felülről korlátos. Az állítás tagadása pedig az, hogy \(\displaystyle \lim_{r\to\infty}{K(r)}=\infty\).

A feladat állítását indirekten igazoljuk: a \(\displaystyle \lim_{r\to\infty}{K(r)}=\infty\) feltevésből fogunk ellentmondásra jutni. Az 1. lemma szerint azt is feltehetjük, hogy \(\displaystyle K(1)>0\).

Definiáljuk a következő intervallumokat:

\(\displaystyle I_n = \left(x_n-\frac1n; x_n+\frac1n \right) \cap [0,1] \quad(n=1,2,\ldots). \)

Könnyű meggondolni, hogy az \(\displaystyle I_n\) intervallum hossza legalább \(\displaystyle \frac1n\).

Legyen \(\displaystyle N\) nagy pozitív egész (később pontosan definiáljuk), és vegyük az első \(\displaystyle N\) intervallumot. Az első \(\displaystyle N\) intervallum hosszának összege

\(\displaystyle |I_1|+|I_2|+\ldots+|I_N| \ge 1+\frac12+\ldots+\frac1N > \ln N, \)

így a skatulya-elv miatt biztosan van olyan \(\displaystyle t\in[0,1]\) szám, ami több, mint \(\displaystyle \ln N\) intervallumnak eleme. Vannak tehát olyan \(\displaystyle 1\le n_1<n_2<\ldots<n_L\le N\) indexek, amikre \(\displaystyle t\in I_{n_k}\) minden \(\displaystyle k=1,2,\ldots,n\)-re, és \(\displaystyle L>\ln N\).

Tetszőleges \(\displaystyle 1\le k<L\)-re, a háromszög-egyenlőtlenség és az intervallumok definíciója szerint

\(\displaystyle |x_{n_{k+1}}-x_{n_k}| \le |x_{n_{k+1}}-t| + |t-x_{n_k}| < \frac1{n_{k+1}}+\frac1{n_k} < \frac2{n_{k}}, \)

továbbá a \(\displaystyle K\) függvény definícióját alkalmazva,

\(\displaystyle |x_{n_{k+1}}-x_{n_k}| \ge \frac{K(n_{k+1}-n_k)}{n_{k+1}-n_k}. \)

A kettőt összevetve, a \(\displaystyle K\) monotonitását és az \(\displaystyle n_k\ge k\) becslést alkalmazva,

\(\displaystyle n_{k+1}-n_k > \frac12 K(n_{k+1}-n_k) \cdot n_k \ge \frac{K(1)}2 \cdot k ; \)

\(\displaystyle n_{k+1}-n_k > \frac12 K(n_{k+1}-n_k) \cdot n_k > \frac12 K\left( \frac{K(1)}2 \cdot k \right)\cdot n_k. \)

Mivel \(\displaystyle K(1)>0\) és \(\displaystyle \lim_{r\to\infty}K(r)=\infty\), van olyan \(\displaystyle k_0\) pozitív egész, hogy \(\displaystyle k\ge k_0\) esetén \(\displaystyle \frac12 K(\tfrac{K(1)}2 k) >2\). (Ez a \(\displaystyle k_0\) szám független \(\displaystyle N\)-től, csak a \(\displaystyle K\) függvény divergenciájának sebességtől függ.) Így hát \(\displaystyle k_0\le k<L\) esetén

\(\displaystyle n_{k+1}-n_k > \frac{K(\tfrac{K(1)}2 k)}2 n_k > 2 n_k, \)

\(\displaystyle n_{k+1} > 3n_k. \)

Ebből látjuk, hogy \(\displaystyle L>k_0\) esetén

\(\displaystyle N \ge \frac{n_L}{n_{k_0}} = \frac{n_{k_0+1}}{n_{k_0}} \cdot \frac{n_{k_0+2}}{n_{k_0+1}} \cdot\ldots\cdot \frac{n_L}{n_{L-1}} \ge 3^{L-k_0} > 3^{\ln N-k_0} \)

(\(\displaystyle \ln N<L\le k_0\) esetén ugyanez triviálisan teljesül), így

\(\displaystyle \ln N > (\ln N-k_0) \ln 3 \)

\(\displaystyle \ln N < \frac{k_0 \ln3}{\ln3-1}. \)

De ez ellentmondás, mert \(\displaystyle k_0\) független \(\displaystyle N\)-től, és \(\displaystyle N\)-et tetszőlegesen nagynak választhatjuk.

2. megoldás az (a) részre (Williams Kada megoldása alapján).

Tegyük fel indirekt, hogy az állítás nem igaz. Vagyis tegyük fel, hogy van olyan végtelen \(\displaystyle x_1,x_2,\ldots\in[0;1]\) számsorozat, amelyre teljesül, hogy bármely \(\displaystyle C>0\) esetén van olyan \(\displaystyle r\) pozitív egész úgy, hogy bármely legalább \(\displaystyle r\) eltérésű \(\displaystyle n,m\) pozitív egészekre fennáll \(\displaystyle |x_n-x_m|\ge \frac{C}{|n-m|}\). Az 1. megoldásban látott módon feltehetjük, hogy alkalmas \(\displaystyle c>0\) konstanssal, tetszőleges \(\displaystyle n\ne m\) esetén

Válasszunk egy alkalmas \(\displaystyle C\) számot, és jelöljünk ki hozzá egy olyan \(\displaystyle r\)-et, hogy

Válasszunk ki ezután egy alkalmasan nagy \(\displaystyle N\) pozitív egész számot. (A \(\displaystyle C\) és \(\displaystyle N\) pontos értékét később határozzuk meg.)

Tekintsük az \(\displaystyle x_1,x_2,\dots,x_{N^2+1}\) számokat. Az Erdős-Szekeres-tétel szerint ekkor lesz olyan \(\displaystyle 1\le i_1\le i_1<\dots<i_N\le N^2+1\) indexsorozat, amelyre az \(\displaystyle (x_{i_j})_{j=0,1,\dots,N}\) sorozat monoton növekvő vagy monoton csökkenő.

Legyen \(\displaystyle d_j:=|x_{i_j}-x_{i_{j-1}}|\) minden \(\displaystyle j=1,2,\dots,N\)-re, és legyen \(\displaystyle d=|x_{i_N}-x_{i_0}|\), ahol a monotonitás miatt

\(\displaystyle d=d_1+d_2+\dots+d_N. \)

Az \(\displaystyle (1)\) és \(\displaystyle (2)\) feltételeket egyaránt szeretnénk kiaknázni, ehhez megkülönböztetjük a következő két halmazt:

\(\displaystyle J_{kis} = \left\{j:1\le j\le N,i_{j}-i_{j-1}<r\right\}, \)

\(\displaystyle J_{nagy} = \left\{j:1\le j\le N,i_{j}-i_{j-1}\ge r\right\}. \)

Most \(\displaystyle (1)\) és \(\displaystyle (2)\) szerint

\(\displaystyle \forall j\in J_{kis} ~~ d_j\ge \frac{c}{i_j-i_{j-1}}, \)

\(\displaystyle \forall j\in J_{nagy} ~~ d_j\ge \frac{C}{i_j-i_{j-1}}. \)

Mivel \(\displaystyle \{x_i\}\subset [0;1]\), ezért biztosan \(\displaystyle d\le 1\). Ezek szerint még az is igaz, hogy

Ezután a számtani és harmonikus közepek közötti egyenlőtlenséget felhasználva fogunk becsülni.

\(\displaystyle (3)\)-at folytatva, és felhasználva \(\displaystyle J_{kis}\) definícióját:

Majd pedig \(\displaystyle (4)\)-et folytatjuk, először felhasználva, hogy

\(\displaystyle \sum_{j\in J_{nagy}}(i_j-i_{j-1})\le \sum_{j=1}^N (i_j-i_{j-1})=i_N-i_0\le N^2:\)

Ezután rendezzük át \(\displaystyle (5)\)-öt és \(\displaystyle (6)\)-ot, és adjuk össze a két kapott becslést:

\(\displaystyle |J_{kis}|< \frac{r}{c},\qquad |J_{nagy}|\le \frac{N}{\sqrt{C}} \)

\(\displaystyle N=|J_{kis}|+|J_{nagy}| < \frac{r}{c}+\frac{N}{\sqrt{C}}. \)

Ez viszont ellentmondáshoz vezet, amennyiben \(\displaystyle C=4\), majd pedig \(\displaystyle N\ge \frac{2r}{c}\). választással élünk.

3. megoldás az (a) részre (Carlos Gustavo T. De A. Moreira megoldása).

Két esetet különböztetünk meg:

1. eset: minden \(\displaystyle \delta>0\)-hoz vannak olyan \(\displaystyle n, k\) pozitív egészek, amelyekre

\(\displaystyle \bigg|\Big\{1\le s\le k : \exists j, 1\le j\le k, x_{n+j}\in \big[\tfrac{s-1}k,\tfrac sk\big] \Big\}\bigg| < \delta k. \)

Megmutatjuk, hogy bármely \(\displaystyle C>1\) megfelelő. Vegyünk egy tetszőleges \(\displaystyle r\)-et.

Legyen \(\displaystyle \delta=1/r\); a feltétel szerint ehhez is vannak olyan \(\displaystyle n, k\) pozitív egészek, hogy \(\displaystyle |\{1\le s\le k : \exists j, 1\le j\le k, x_{n+j}\in [\frac{s-1}k,\frac sk]\}|<\delta k=k/r\). A halmazban kevesebb, mint \(\displaystyle k/r\) érték van; van tehát olyan \(\displaystyle 1\le s\le k\), amihez több, mint \(\displaystyle r\) különböző lehetséges \(\displaystyle j\) is létezik, amire \(\displaystyle x_{n+j}\in [\frac{s-1}k,\frac sk]\). A legkisebb és legnagyobb legyen \(\displaystyle j_1\), illetve \(\displaystyle j_2\); ekkor tehát \(\displaystyle 1\le j_1<j_2\le k\) és \(\displaystyle j_2-j_2\ge r\) és

\(\displaystyle |x_{n+j_2}-x_{n+j_1}|\le \frac1k \le \frac1{j_2-j_1} < \frac{C}{(n+j_2)-(n+j_1)}. \)

2. eset: van olyan \(\displaystyle \delta\in(0,1)\) úgy hogy tetszőleges \(\displaystyle n, k\) pozitív egészekre

\(\displaystyle \bigg|\Big\{1\le s\le k : \exists j, 1\le j\le k, x_{n+j}\in \big[\tfrac{s-1}k,\tfrac sk\big] \Big\}\bigg| \ge \delta k. \)

Ebben az esetben \(\displaystyle C>1+\frac2\delta\) megfelelő. Legyen \(\displaystyle r\) ismét tetszőleges.

Legyen \(\displaystyle v=\lfloor 1/\delta \rfloor\). Vizsgáljuk \(\displaystyle 0\le i\le v\) esetén az \(\displaystyle A_i=\{2ir+j, 1\le j\le r\}\) és \(\displaystyle X_i=\{1\le s\le r;\exists t \in A_i, x_t\in [\frac{s-1}r,\frac sr]\}\) halmazokat. Mivel \(\displaystyle |X_i|\ge \delta r\) és \(\displaystyle (v+1)\delta r>r\), léteznek olyan \(\displaystyle 0\le i_1<i_2\le v\) indexek, amelyekre \(\displaystyle X_{i_1}\cap X_{i_2}\neq \emptyset\). Ha \(\displaystyle s\in X_{i_1}\cap X_{i_2}\), akkor létezik olyan \(\displaystyle t_1\in A_{i_1}, t_2\in A_{i_2}\), amire \(\displaystyle x_{t_1}, x_{t_2}\in [\frac{s-1}r,\frac sr]\), és így \(\displaystyle |x_{t_2}-x_{t_1}|\le 1/r\). A halmazok konstrukciója miatt \(\displaystyle r\le t_2-t_1\le (2v+1)r\), és így \(\displaystyle (t_2-t_1)|x_{t_2}-x_{t_1}|\le 2v+1\le 1+2/\delta<C\).

Megoldás a (b) részre.

2. lemma: Tetszőleges \(\displaystyle p,q\) pozitív egész számokra \(\displaystyle \big|p\sqrt2-q\big|>\frac1{4p}\).

Bizonyítás: Ha \(\displaystyle \big|p\sqrt2-q\big|\ge1\), akkor az állítás triviális. Egyébként pedig

\(\displaystyle \big|p\sqrt2-q\big| = \frac{|2p^2-q^2|}{p\sqrt2+q} \ge \frac1{p\sqrt2+q} = \frac1{2p\sqrt2-\big(p\sqrt2-q\big)} > \frac1{2p\sqrt2+1} > \frac1{4p}. \)

Ezek után legyen \(\displaystyle r=[8C]+1\), és definiáljuk az \(\displaystyle (x_n)\) sorozatot így:

\(\displaystyle x_n = \left\{\bigg[\frac{n-1}r\bigg]\cdot\sqrt2\right\}. \)

Más szóval, \(\displaystyle x_1=x_2=\ldots=x_r=0\), \(\displaystyle x_{r+1}=x_{r+2}=\ldots=x_{2r}=\big\{\sqrt2\big\}\), \(\displaystyle x_{2r+1}=x_{2r+2}=\ldots=x_{3r}=\big\{2\sqrt2\big\}\), \(\displaystyle x_{3r+1}=x_{3r+2}=\ldots=x_{4r}=\big\{3\sqrt2\big\}\), ... Tekintsünk most két tetszőleges \(\displaystyle n,m\) indexet, amelyekre \(\displaystyle n-m\ge r\). Legyen \(\displaystyle a=[(n-1)/r]\), \(\displaystyle b=[(m-1)/r]\), \(\displaystyle c=[A\sqrt2]\) és \(\displaystyle d=[B\sqrt2]\). Ekkor tehát \(\displaystyle x_n=a\sqrt2-c\) és \(\displaystyle x_m=b\sqrt2-d\), továbbá

\(\displaystyle a-c > \frac{n-1}r - \left(\frac{m-1}r+1\right) = \frac{n-m}r-1 \ge 0 \)

és

\(\displaystyle a-c < \left(\frac{n-1}r+1\right) - \frac{m-1}r < 2\frac{n-m}r, \)

ezért

\(\displaystyle |x_n-x_m| = \big|(a-c)\sqrt2-(b-d)\big| > \frac1{4(a-c)} > \frac{r}{8(n-m)} > \frac{C}{n-m}. \)

Statisztika:

5 dolgozat érkezett.
5 pontot kapott:	Williams Kada.
2 pontot kapott:	2 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2014. októberi matematika feladatai