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