 
\magnification=\magstep1
\input amstex
\hsize=16truecm
\parskip=4pt plus 1pt
\parindent=18pt
\TagsOnRight
 
\define\({\left(}
\define\){\right)}
\define\e{\varepsilon}
\define\limm{\lim\limits}
 
\centerline{\bf A Secretary problem. Optim\'alis v\'alaszt\'as
megtal\'al\'asa.} \medskip
 
A Szindb\'ad probl\'em\'anak van egy szint\'en klasszikusnak
tekinthet\H{o}, tal\'an ter\-m\'e\-sze\-te\-sebb viszont nehezebb
v\'altozata. Ez a k\"ovetkez\H{o} ,,Secretary problem"-nak nevezett
k\'erd\'es: Egy \'all\'asra ismert $n$ sz\'am\'u jel\"olt jelentkezik,
akik v\'eletlen sorrendben jelennek meg a felv\'eteli interj\'ura,
\'es minden lehets\'eges sorrend egyforma val\'osz\'{\i}n\H{u}. Legyen
a legjobb jel\"olt rangja 1, a m\'asodik legjobb jel\"olt rangja 2,
\'es a $k$-ik legjobb jel\"olt rangja $k$, $k=1,2,\dots,n$. A
felv\'eteli interj\'u sor\'an az \'eppen jelentkez\H{o}
felv\'eteliz\H{o} j\'os\'ag\'at \"ossze tudjuk hasonl\'{\i}tani az
addig megjelentekkel, azaz meg tudjuk mondani az addig megjelentek
k\"oz\"otti relativ rangj\'at. Ezut\'an eld\"ontj\"uk, hogy a
jel\"oltet elfogadjuk vagy elbocs\'ajtjuk, \'es ezt a d\"ont\'est
k\'es\H{o}bb nem v\'altoztathatjuk meg. C\'elunk az, hogy
mi\-ni\-ma\-li\-z\'al\-juk a kiv\'alasztott jel\"olt rangj\'anak a
v\'arhat\'o \'ert\'ek\'et. K\'erd\'es, hogy ez a rang optim\'alis
v\'alaszt\'as eset\'en v\'egtelenhez tart-e, ha a jel\"oltek $n$
sz\'ama tart a v\'egtelenhez. Be lehet l\'atni, hogy optim\'alis
v\'alaszt\'as eset\'en l\'etezik v\'eges hat\'ar\'ert\'ek, \'es
annak \'ert\'eke is ismert. Ez a
$$
\prod_{j=1}^\infty\(\frac{j+2}j\)^{1/(j+1)}\sim 3.8695
$$
sz\'am. Ennek a t\'enynek azonban nincs olyan egyszer\H{u} indokl\'asa
mint annak, hogy Szindb\'ad probl\'em\'aj\'aban a sikeres v\'alaszt\'as
val\'osz\'{\i}n\H{u}s\'ege j\'o strat\'egia eset\'en nem tart
null\'ahoz $n\to\infty$ eset\'en.
 
A ,,Secretary problem"-nak csak
r\'eszleges megold\'as\'at \'{\i}rom le. Megadom minden
r\"ogz\'{\i}tett $n$-re az optim\'alis strat\'egi\'at, illetve azt a
rekurzi\'ot, melynek seg\'{\i}ts\'eg\'evel kisz\'am\'{\i}that\'o az
optim\'alis strat\'egia eset\'en a kiv\'alasztott jel\"olt rangj\'anak
a v\'arhat\'o \'ert\'eke. Ennek seg\'{\i}ts\'eg\'evel megmutatom,
hogy ennek a v\'arhat\'o \'ert\'eknek az \'ert\'eke minden
$n$ sz\'amra kisebb mint 8. Annak bizony\'{\i}t\'asa, hogy
l\'etezik a fent megadott hat\'ar\'ert\'ek a rekurzi\'o alaposabb
vizsg\'alat\'at ig\'enyli. Ez meglehet\H{o}sen f\'araszt\'o, a
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'eg\-sz\'a\-m\'{\i}\-t\'as\-hoz
k\"ozvetlen\"ul nem kapcsol\'od\'o probl\'ema. Ez\'ert ennek
r\'eszleteit nem t\'argyalom, csak egy heurisztikus indokl\'ast adok,
mely felhaszn\'alja az optim\'alis megold\'as megad\'as\'ahoz
sz\"uks\'eges sz\'amsorozat n\'eh\'any term\'eszetes, de
bizony\'{\i}t\'asra szo\-ru\-l\'o tu\-laj\-don\-s\'a\-g\'at. Az
\'erdekl\H{o}d\H{o}k a r\'eszleteket kidolgoz\'o, teljes
bizony\'{\i}t\'ast megtal\'alhatj\'ak Y. S. Chow, S. Moriguti,
H. Robbins \'es M. Samuels {\it Optimal Selection Based On Relative
Ranks}\/ (``the Secretary Problem") c\'{\i}m\H{u} az Israel Journal
of Mathematics (1964) 81--90 \'ujs\'agan megjelent cikk\'eben.
 
A secretary problem sokban hasonl\'{\i}t a Szindb\'ad probl\'em\'ahoz.
Az ott tanultak nagyon hasznosak, \'es l\'enyeg\'eben elegend\H{o}
inform\'aci\'ot adnak az optim\'alis strat\'egia kidolgoz\'as\'ahoz.
 
Legyen $Z_1,\dots,Z_n$ az egym\'as ut\'an megjelen\H{o} jel\"oltek a
megjelen\'es pillanat\'aban ismeretlen rangja, \'es legyen $\xi_i$ az
$i$-ik jel\"ult (megjelen\'ese ut\'an megismert) relativ rangja az
els\H{o} $i$ jel\"olt k\"oz\"ott. Ekkor, mint azt a Szindb\'ad
probl\'ema megold\'as\'aban l\'attuk a $\xi_1,\dots,\xi_n$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok f\"uggetlenek, \'es
$P(\xi_i=j)=\dfrac 1i$ minden $1\le j\le i$ sz\'amra. Tov\'abb\'a ki
tudjuk sz\'amolni annak felt\'eteles val\'osz\'{\i}n\H{u}s\'eg\'et,
hogy a $i$-edik jel\"olt rangja egy adott $k$ sz\'am felt\'eve az els\H{o}
$i$ megfigyel\'es \'ert\'ek\'et. Ez a
$$
P(Z_i=k|\xi_1=j_1,\dots,\xi_{i-1}=j_{i-1},\xi_i=j)=
\frac{\dbinom{k-1}{j-1} \dbinom{n-k}{i-j}}{\dbinom ni}. \tag1
$$
\'ert\'ek.
 
Ezt az azonoss\'agot p\'eld\'aul a k\"ovetkez\H{o}k\'epp l\'athatjuk
be:
$$
P(\xi_1=j_1,\dots,\xi_{i-1}=j_{i-1},\xi_i=j)=\dfrac{\dbinom ni
(n-i)!}{n!},
$$
aminek egyik lehets\'eges indokl\'asa a k\"ovetkez\H{o}:
A jel\"oltek \"osszesen $n!$ sorrendben jelenhetnek meg, \'es minden
sorrend egyform\'an val\'osz\'{\i}n\H{u}. Az olyan sorrendek sz\'ama,
melyekre teljes\"ulnek a $\xi_1=j_1,\dots,\xi_{i-1}=j_{i-1},\xi_i=j$
felt\'etelek $\dbinom ni (n-i)!$, mert $\dbinom ni$ f\'ele m\'odon
v\'alaszthatjuk meg az els\H{o} $i$ l\'ep\'esben megjelen\H{o}
jel\"oltek halmaz\'at, ezek bels\H{o} sorrendj\'et egy\'ertelm\H{u}en
meghat\'arozza a $\xi_1=j_1,\dots,\xi_{i-1}=j_{i-1},\xi_i=j$
felt\'etel, \'es ezut\'an a marad\'ek $n-i$ jel\"olt $(n-i)!$ sorrendben
jelenhet meg. M\'asr\'eszt
$$
P(Z_i=k,\xi_1=j_1,\dots,\xi_{i-1}=j_{i-1},\xi_i=j)
=\dfrac{\dbinom{k-1}{j-1}\dbinom{n-k}{i-j}(n-i)!}{n!}.
$$
Ez az azonoss\'ag az el\H{o}z\H{o}h\"oz hasonl\'oan indokolhat\'o. Azt
kell meg\'erten\"unk, hogy ekkor a lehets\'eges megjelen\'esi sorrendek
sz\'ama $\dbinom{k-1}{j-1}\dbinom{n-k}{i-j}(n-i)!$. Ugyanis ekkor az
els\H{o} $i$ l\'ep\'esben megjelen\H{o} jel\"oltek k\"oz\"ott ott
lennie annak a jel\"oltnek, akinek a rangja $k$, \'es ennek a relativ
rangja az els\H{o} $i$ jel\"olt k\"oz\"ott $j$ kell, hogy legyen. Ez
azt jelenti, hogy a legjobb $k-1$ jel\"olt k\"oz\"ul $j-1$ \'es
a legrosszabb $n-k$ jel\"olt k\"oz\"ul pedig $i-j$ r\'esztvev\H{o}
jelenik meg az els\H{o} $i$ l\'ep\'esben. Ez
$\dbinom{k-1}{j-1}\dbinom{n-k}{j-i}$ m\'odon lehets\'eges. Ezut\'an a
$Z_i=k,\xi_1=j_1,\dots,\xi_{i-1}=j_{i-1},\xi_i=j$ felt\'etel
egy\'ertelm\H{u}en
meghat\'arozza az els\H{o} $i$ jel\"olt bels\H{o} sorrendj\'et, a
marad\'ek $n-i$ jel\"olt pedig $(n-i)!$ m\'odon jelenhet meg.
 
Az (1) rel\'aci\'o speci\'alisan azt is jelenti, hogy
$$
\sum_{k=j}^n \dbinom{k-1}{j-1} \dbinom{n-k}{i-j}=\dbinom ni. \tag2
$$
Ez\'ert
$$
\aligned
&E(Z_i|\xi_1=i_1,\dots,\xi_{i-1}=j_{i-1},\xi_i=j)=
\sum_{k=j}^n k\frac{\dbinom{k-1}{j-1} \dbinom{n-k}{i-j}}{\dbinom ni}\\
&\qquad =\dfrac1{\dbinom ni}
\sum_{k=j}^n j \dbinom kj \dbinom{(n+1)-(k+1)}{(i+1)-(j+1)}
=j\dfrac {\dbinom {n+1}{i+1}}{\dbinom ni}=j\dfrac {n+1}{i+1}
\endaligned \tag3
$$
a (2) rel\'aci\'o alapj\'an (az $n$, $i$ \'es $j$ param\'eterek
helyett az $n+1$, $i+1$ \'es $j+1$ param\'eter v\'alaszt\'assal.
\medskip\noindent
{\it Feladat:}\/ Adjunk a (2) azonoss\'agra k\"ozvetlen kombinatorikus
bizony\'{\i}t\'ast. Egy lehet\H{o}s\'eg: Sz\'amoljuk \"ossze, h\'any
olyan $n+1$ hossz\'us\'ag\'u fej-\'{\i}r\'as sorozat van, melyben az
$n+1$-ik tag az $i+1$-ik fej. Sz\'amoljuk ezt \"ossze \'ugy is, hogy
el\H{o}\'{\i}rjuk a sorozatban szerepl\H{o} $j$-ik fejdob\'as
hely\'et, majd \"osszegez\"unk ennek a helynek a lehets\'eges
\'ert\'ekeire.
 
Egy m\'asik lehets\'eges indokl\'as: (A negat\'{\i}v binomi\'alis
eloszl\'asr\'ol tanultak alapj\'an) \'{\i}rjuk \'at a (2)
kifejez\'esben szerepl\H{o} tagokat mint alkalmas (negat\'{\i}v
sz\'amokat is meg\-en\-ge\-d\H{o}) binomi\'alis egy\"utthat\'okat.
 
P\'eld\'aul: $\dbinom ni=\dbinom
n{n-i}=(-1)^{n-i}\dbinom{-(i+1)}{n-i}$. Ezut\'an alkalmazzuk az
$(1-x)^{\alpha+\beta}=(1-x)^\alpha(1-x)^{\beta}$
azonoss\'agot, illletve annak k\"ovetkezm\'eny\'et e f\"uggv\'enyek
hatv\'anysorainak egy\"utthat\'oira alkalmas $\alpha$ \'es $\beta$
v\'alaszt\'assal. \medskip
A fenti eredm\'eny, illetve a Szindb\'ad probl\'ema megold\'as\'aban
tanultak alapj\'an a Secretary problem ekvivalens a k\"ovetkez\H{o}
k\'erd\'essel: Legyenek
$\xi_1,\dots,\xi_n$ f\"uggetlen val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'ok, melyek eloszl\'as\'at a $P(\xi_i=j)=\dfrac1i$. $1\le j\le
i$, $1\le i\le n$ k\'eplet adja meg.
Vezess\"uk be a $v_i(j)=v_{i,n}(j)=j\dfrac{n+1}{i+1}$
k\"olts\'egf\"uggv\'enyt. Keress\"uk meg azt az optim\'alis $\tau$
meg\'all\'asi szab\'alyt, mely minimaliz\'alja a
k\"olts\'egf\"uggv\'eny $Ev_\tau(\xi_\tau)$ v\'arhat\'o \'ert\'ek\'et.
Azt is megt\'argyaltuk, hogyan kell ezt a feladatot megoldani.
Defini\'aljuk a
$$
\aligned
c_{n-1}&=Ev_n(\xi_n)=\frac1n\sum_{j=1}^n j\frac{n+1}{n+1}=\frac{n+1}2
\\ c_{i-1}&=E\(\min\(\frac{n+1}{i+1}\xi_i,
c_i\)\)=\frac1i\sum_{j=1}^i\(\min\(\frac{n+1}{i+1}j, c_i\)\) ,\quad
i=n-1,n-2,\dots,1
\endaligned \tag4
$$
sz\'amsorozatot. Ekkor az optim\'alis meg\'all\'as az lesz, hogy a
$i$-ik id\H{o}pontban \'allok meg, $1\le i\le n-1$, ha nem \'alltam meg
el\H{o}bb, \'es $v_i(\xi_i)=\dfrac{n+1}{i+1}\xi_i\ge c_{i}$. Az $n$-ik
l\'ep\'esben mindenk\'epp meg\'allok.
A k\"olts\'eg v\'arhat\'o \'ert\'eke pedig (az optim\'alis strat\'egia
eset\'en) $c_0$. Ezek ut\'an a feladat a (4) rekurz\'{\i}v
elj\'ar\'assal megadott az $n$ megengedett l\'ep\'essz\'amt\'ol is
f\"ugg\H{o} $c_i=c_i^{(n)}$ sorozat kisz\'amol\'asa \'es a
$C=\limm_{n\to\infty}c_0^{(n)}$ hat\'ar\'ert\'ek meghat\'aroz\'asa
(felt\'eve, hogy ez a hat\'ar\'ert\'ek l\'etezik).
 
A $c_i$ sorozat vizsg\'alat\'aban \'erdemes bevezetni a
$t_i=\dfrac{i+1}{n+1}c_i$, $0\le i\le n-1$, \'es $s_i=[t_i]$
mennyis\'egeket, ahol $[x]$ jel\"oli az $x$ sz\'am eg\'esz
r\'esz\'et. Ezekkel a jel\"ol\'esekkel a (4) rekurzi\'os formula
n\'emileg egyszer\H{u}bb form\'aban \'{\i}rhat\'o fel:
$$
c_{i-1}=\frac1i\(\frac{n+1}{i+1}(1+\cdots+s_i)+(i-s_i)c_i\)
=\frac1i\(\frac{n+1}{i+1}\frac{s_i(s_i+1)}2+(i-s_i)c_i\),
$$
\'es $t_i=s_i+\alpha_i$, $0<\alpha_i<1$ jel\"ol\'essel
$$
t_{i-1}=\frac{s_i(s_i+1)+2t_i(i-s_i)}{2(i+1)}, \tag5a
$$
$$
t_{i-1}=\frac {t_i(1+2i-t_i)}{2(i+1)}-\frac{\alpha(1-\alpha)}{2(i+1)}.
\tag5
$$
A $t_i\to t_{i-1}$ transzform\'aci\'o viselked\'es\'enek jobb
meg\'ert\'ese \'erdek\'eben vezess\"uk be az annak a f\H{o} r\'esz\'et
le\'{\i}r\'o
$$
T(x)=T_i(x)=\dfrac{x(1+2i-x)}{2(i+1)}
$$
transzform\'aci\'ot. Egyszer\H{u} sz\'amol\'as adja, hogy
$$
T'(x)=\frac{1+2i-2x}{2(i+1)}\ge0, \quad\text{ha } x\le i+\frac12,
$$
ez\'ert $T(x)$ monoton n\H{o} $x\le i+\dfrac12$ eset\'en.
Tov\'abb\'a (5) alapj\'an
$$
T(t_i)\ge t_{i-1}. \tag6
$$
A fentiek alapj\'an bizony\'{\i}that\'o a
k\"ovetkez\H{o} \medskip\noindent
{\bf Lemma.}
$$
t_i\le \frac{2n}{n-i+3}. \tag7
$$
\medskip
A lemma bizony\'{\i}t\'asa el\H{o}tt mutassuk meg annak egy \'erdekes
k\"ovetkezm\'eny\'et. \medskip\noindent
{\bf K\"ovetkezm\'eny:} {\it
$$
c_0< 8,
$$
azaz a v\'arhat\'o nyerem\'eny optim\'alis strat\'egia eset\'en
b\'armely $n$ sz\'amra kisebb mint 8.}
\medskip\noindent
{\it A k\"ovetkezm\'eny bizony\'{\i}t\'asa.}
A $c_i$ sorozat definici\'oj\'ab\'ol kiolvashat\'o, hogy az monoton
n\H{o}. Ez\'ert v\'alasztva az $i=\left[\dfrac n2\right]$ sz\'amot
kapjuk a Lemma felhaszn\'al\'as\'aval, hogy
$$
c_0\le c_i=\frac{n+1}{i+1}t_i\le \frac{n+1}{i+1}\frac{2n}{n-i+3}\le
\frac{2n(n+1)}{\frac n2\(\frac n2+3\)}<8.
$$
\medskip\noindent
{\it A Lemma bizony\'{\i}t\'asa:}\/
A Lemma \'all\'{\i}t\'asa \'erv\'enyes $i=n-1$-re, mert $t_{n-1}=\dfrac
n2=\dfrac{2n}4$. Ez\'ert el\'eg bel\'atni, hogy amennyiben az
\'erv\'enyes $1\le i\le n-1$-re, akkor \'erv\'enyes $i-1$-re is. Ezt
\'ugy bizony\'{\i}tjuk, hogy felhaszn\'aljuk a  (7)-es formul\'at a
m\'ar bizony\'{\i}tott $i$ param\'eterrel, a (6)
egyenl\H{o}tlens\'eget valamint azt, hogy a $T(x)$ transzform\'aci\'o
monoton n\H{o} $t\le i+\dfrac12$ esetben. Tov\'abb\'a, mivel a
$c_i$ sorozat monoton n\H{o}, ez\'ert
$$
t_{i-1}=\frac i{n+1} c_{i+1}\le \frac
i{n+1}c_{n-1}=\frac i{n+1}\frac{n+1}2=\frac i2.
$$
Ez a becsl\'es t\'ul durva, m\'egis hasznos. Ugyanis vagy teljes\"ul
az $\dfrac i2\le \dfrac{2n}{n-i+4}$ azonoss\'ag, \'es az indukci\'os
feltev\'es teljes\"ul $i-1$-re is, (ez csak nagyon kis $i$ indexre
lehets\'eges) vagy $\dfrac i2> \dfrac{2n}{n-i+4}$, \'es ekkor
$i+\dfrac12\ge\dfrac{2n}{n-i+3}$, ez\'ert mind a $t_i$ mind a
$\dfrac{2n}{n-i+3}\ge t_i$ sz\'amok beleesnek abba az intervallumba,
ahol $T(\cdot)$ monoton n\H{o}. Ez\'ert
$$
t_{i-1}\le T(t_i)\le
T\(\frac{2n}{n-i+3}\)=\frac{n\{(1+2i)(n-i+3)-2n\}}{(i+1)(n-i+3)^2}\le
\dfrac{2n}{n-i+4},
$$
ami azt jelenti, hogy igaz az indukci\'os feltev\'es $i-1$-re is. Az
utols\'o azonoss\'ag az\'ert igaz, mert az ekvivalens a
$$
(n-i+3)^2+(2n-2i-10(n-i+3)+2n\ge0
$$
egyenl\H{o}tlens\'eggel, ami ny\'{\i}lv\'an \'erv\'enyes $n-i\ge 1$,
azaz $i\le n-1$ eset\'en.
\medskip
\centerline{\bf A $\limm_{n\to\infty} c^{(n)}_0$ hat\'ar\'ert\'ek
meghat\'aroz\'asa.}
\centerline{\it A r\'eszletek kidologz\'asa n\'elk\"ul.}
\medskip
Vezess\"uk be az $i_k=i_k^{(n)}$ mennyis\'egeket a k\"ovetkez\H{o}
m\'odon:
$$
i_k=\text{A legkisebb $j$ pozit\'{\i}v eg\'esz sz\'am, melyre $t_j\ge
k$}.
$$
Az $i_k$ mennyis\'egeket az\'ert \'erdemes bevezetni, mert
seg\'{\i}ts\'eg\"ukkel vizsg\'alhat\'o az optim\'alis meg\'all\'asi
szab\'aly. Ez a k\"ovetkez\H{o}: Az els\H{o} $i_1-1$ jel\"oltet
mindenk\'eppen elutas\'{\i}tjuk. Az $i_k\le j<i_{k+1}$-ik
megjelent jel\"oltet akkor fogadjuk el, ha annak $\xi_k$
relat\'{\i}v rangja kisebb vagy egyenl\H{o} mint $k$. A fenti
megjegyz\'esb\H{o}l az is k\"ovetkezik, hogy
$$
c_0=c_1=\cdots=c_{i_1-1}.
$$
(Eml\'ekeztet\H{o}\"ul, a $c_j$ mennyis\'eg annak a v\'arhat\'o
\'ert\'eke, hogy mekkora a k\"olt\-s\'eg\-f\"ugg\-v\'e\-nyem, ha
az els\H{o} $j$ l\'ep\'esben nem \'allhatok meg, \'es ezen felt\'etel
mellett az optim\'alis strat\'egi\'at folytatom.)
 
Be lehet l\'atni, hogy hogy l\'eteznek az
$\alpha_{k-1}=\limm_{n\to\infty}\dfrac {i_k^{(n)}}n$
hat\'ar\'ert\'ekek, $\alpha_0\le\alpha_1\le\cdots$, $\alpha_k<1$
minden $k=0,1,\dots$ sz\'amra, \'es $\limm_{k\to\infty}\alpha_k=1$.
\'Erdemes k\"ul\"on hangs\'ulyozni, hogy az $\alpha_0>0$ szigor\'u
egyenl\H{o}tlens\'eg \'erv\'enyes.
 
Ezenk\'{\i}v\"ul a $t_j=t_j^{(n)}$ sz\'amok a $j$ index
megv\'altoz\'as\'aval keveset v\'altoznak. Pontosabban megfogalmazva,
tetsz\H{o}leges $0<\alpha<\beta<1$ sz\'amra
$$
\lim_{n\to\infty} \sup_{\alpha n\le j\le \beta n}
(t_j^{(n)}-t_{j-1}^{(n)})=0.
$$
A fenti rel\'aci\'o azt sugallja, hogy a $t_{i_k}\sim t_{i_k-1}\sim k$
k\"ozel\'{\i}t\'essel kis hib\'at k\"ovet\"unk el. Speci\'alisan,
$$
c_0=c_1=\cdots=c_{i_1=1}=\frac {(n+1)t_{i_1-1}}i\sim \frac n{i_1},
$$
ez\'ert
$$
\lim_{n\to\infty} c_0^{(n)}=\lim_{n\to\infty}\frac n{i_1^{(n)}}
=\frac1{\alpha_0}.                            \tag8
$$
Ez\'ert a feladat megold\'asa \'erdek\'eben el\'eg a
$\limm_{n\to\infty}\frac{i_k^{(n)}}n=\alpha_{k-1}$ mennyis\'egeket
meg\-ha\-t\'a\-roz\-ni. Az\'ert, hogy ezeket a hat\'ar\'ert\'ekeket
kisz\'amoljuk vezess\"uk be a
$$
v_i=t_i-\frac k2,\quad\text{ha } i_k\le i<i_{k+1} \quad\text{azaz }
k\le t_i<k+1
$$
mennyis\'egeket, \'es \'{\i}rjuk fel mit jelentenek a $t_i$
mennyis\'egekre fenn\'all\'o rekurzi\'os formul\'ak a $v_i$
mennyis\'egekre. Azt kapjuk, hogy
$$
v_{i-1}+\frac k2=\frac{k(k+1)+2(i-k)\(v-\frac k2\)}{2(i+1)}=\frac k2
+\frac {v_i-k}{i+1} v_i,
$$
ahonnan
$$
v_i=\frac{i+1}{i-k}v_{i-1}\quad \text{ha } i_k\le i<i_{k+1}. \tag9
$$
(Hogyan lehet r\'aj\"onni, hogy a fent defini\'alt $v_i$
mennyis\'egekre ilyen egyszer\H{u} rekurzi\'os formula \'erv\'enyes?)
 
Alkalmazva a (8) rel\'aci\'ot szukcessziven a $i_k\le i<i_{k+1}$
sz\'amokra azt kapjuk, hogy
$$
\frac{v_j}{v_i}=\frac{(j+1-k)\cdots (j+1)}{(i+1-k)\cdots (i+1)},
\quad\text{ha } i_k\le i\le j<i_{k+1}.  \tag10
$$
Alkalmazzuk a (10) formul\'at $i=i_k$, $j=i_{k+1}$ v\'alaszt\'assal.
Azt kapjuk, hogy egyr\'eszt
$$
\lim_{n\to\infty} \frac{v_{i_{k+1}^{(n)}} }{v_{i_k^{(n)}} }
=\limm_{n\to\infty}\(\frac{i_{k+1}^{(n)}}{i_k^{(n)}}\)^{k+1}
=\(\frac{\alpha_k}{\alpha_{k-1}}\)^{k+1},
$$
m\'asr\'eszt
$$
\lim_{n\to\infty}\frac{v_{i_{k+1}^{(n)} }}{v_{i_k^{(n)} }}
\lim_{n\to\infty}\frac{\(t_{i_{k+1}^{(n)} }-\frac k2\)}
{\(t_{i_k^{(n)} }-\frac k2\)}
=\frac{k+1-\frac k2}{k-\frac k2}
=\dfrac{k+2}k.
$$
Innen
$$
\dfrac{k+2}k=\(\frac{\alpha_k}{\alpha_{k-1}}\)^{k+1},
$$
ez\'ert
$$
\frac{\alpha_0}{\alpha_k}=\prod_{j=1}^k\(\frac j{j+2}\)^{j+1},
$$
\'es $k\to\infty$ hat\'ar\'atmenettel (felhaszn\'alva, hogy
$\limm_{k\to\infty}\alpha_k=1$) kapjuk, hogy
$$
\limm_{n\to\infty}\frac{i_1^{(n)}}n=\alpha_0=\prod_{j=1}^\infty
\(\frac j{j+2}\)^{j+1}.
$$
Innen \'es a (8) formu\'ab\'ol k\"ovetkezik, hogy a keresett
v\'arhat\'o \'ert\'ek val\'oban a megadott sz\'am.
\bigskip
 
A fenti heurisztikus \'ervel\'es pontoss\'a t\'etele \'erdek\'eban
n\'eh\'any becsl\'esre van sz\"uks\'eg. Ezek k\"oz\"ul a legfontosabb
az, hogy a $t_j$ mennyis\'egekre ne csak (viszonylag durva) fels\H{o}
becsl\'est adjunk (ezt tett\"uk meg a Lemm\'aban), hanem megfelel\H{o}
als\'o becsl\'est is bizony\'{\i}tsunk. Ez kell p\'eld\'aul ahhoz,
hogy tudjuk: $\liminf\limits_{n\to\infty} \dfrac{i_1^{(n)}}n>0$.
 
 A $t_j$ mennyis\'egre adott fels\H{o} becsl\'es bizony\'{\i}t\'asa
azon alapult, hogy az (5) formula seg\'{\i}ts\'eg\'evel viszonylag
egyszer\H{u}, de j\'o $t_{i-1}\le T(t_i)$ alak\'u becsl\'est tudtunk
adni. Hasonl\'o elven egy als\'o becsl\'est is
lehet bizony\'{\i}tani. Be lehet l\'atni, hogy
$$
t_{i-1}\ge \frac{t_i}{i+1}\(1-\frac{t_i}{2(i+1)}\),
$$
\'es ennek alapj\'an
$$
t_i\ge \dfrac{3(i+1)}{2(n-i+2)}.
$$
A bizony\'{\i}t\'as r\'eszleteit elhagyjuk. Az megtal\'alhat\'o az
eml\'{\i}tett cikkben.
 
 
 
 
 \bye
