A B. 4440. feladat (2012. március)

B. 4440. Egy téli napon a szórakozott matematikus egy hosszú egyenes sétányon sétáltatta öreg tacskóját. Annyira elmélyedt a gondolataiban, hogy egyszer csak azt vette észre, hogy a kutya nincs mellette. A hóesés miatt a látótávolság csak 5 méter, a matematikus se maga előtt, se maga mögött nem látja kutyáját, és azt sem tudja, melyik irányba szökhetett el. Rövid töprengés után elindult, hogy megkeresse tacskóját. A kutya legfeljebb fele akkora sebességgel képes haladni, mint gazdája. A matematikus olyan keresési stratégiát választott, hogy a lehető legkisebb c konstans mellett teljesüljön az a feltétel, hogy ha a kutyája tőle x távolságra van, akkor legfeljebb cx hosszúságú utat kelljen megtennie, hogy megtalálja. Mi ez a c érték?

(5 pont)

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

Megoldás. Az egyszerűség kedvéért válasszuk meg mértékegységeinket úgy, hogy mind a látótávolság, mind a matematikus sebessége egységnyi legyen, és tegyük fel, hogy a matematikus a számegyenes origójában áll (a kutya pedig az $\displaystyle x$ vagy a $\displaystyle -x$ pontban van, ahol $\displaystyle x>1$). Ha egy adott keresési stratégia működik valamely $\displaystyle c$ konstanssal, akkor annak abban az esetben is működnie kell, ha a kutya folyamatos 1/2 sebességgel távolodik az origótól. Megfordítva, ha a keresési stratégia működik a $\displaystyle c$ konstanssal ebben az esetben, akkor működni fog minden más esetben is, hiszen minden más esetben a matematikus még hamarabb rá fog találni a kutyára. A továbbiakban tehát feltehetjük, hogy a kutya a fent említett módon viselkedik. A matematikus akkor fogja $\displaystyle s$ út megtétele után az $\displaystyle y$ pontban megtalálni a kutyáját, ha akkor éppen látótávolságnyira megközelíti, vagyis ha $\displaystyle x+s/2=|y|+1$.

Nyilván feltehető, hogy a matematikus először pozitív irányba indul el. Optimális keresési startégiája úgy kell kinézzen, hogy első lépésben választ egy $\displaystyle a_2,a_3, a_4,\ldots$ sorozatot, melyre

$\displaystyle 0<a_2<a_4<a_6<\ldots\quad {\rm és}\quad 0<a_3<a_5<a_7<\ldots,$

majd ezt követően az $\displaystyle i$-edik lépésben elmegy a $\displaystyle (-1)^ia_i$ pontba ($\displaystyle i=2,3,4,\ldots$). A továbbiak kedvéért vezessük be még az $\displaystyle a_0=a_1=0$ jelölést is. Optimális stratégiához a sorozatnak még további feltételeket is ki kell elégítenie, amint azt később látni fogjuk.

A matematikus akkor találja meg a második lépés során a kutyáját, ha az kezdetben az $\displaystyle x$ pontban volt, és $\displaystyle a_2+1\ge x+a_2/2$, vagyis ha

$\displaystyle \frac{a_2}{2}+1\ge x.$

Mivel $\displaystyle x>1$ értéke ismeretlen, ez $\displaystyle a_2$-re csak az $\displaystyle a_2>0$ feltételt szabja ki. Ebben az esetben a megtett útra $\displaystyle s_2=y_2\le a_2$ és

$\displaystyle y_2+1=x+\frac{s_2}{2},$

ahonnan

$\displaystyle \frac{s_2}{x}=2-\frac{2}{x}<2=:c_2.$

A matematikus akkor találja meg a harmadik lépés során a kutyáját, ha az kezdetben a $\displaystyle -x$ pontban volt, és $\displaystyle a_3+1\ge x+(2a_2+a_3)/2$, vagyis ha

$\displaystyle \frac{a_3}{2}-a_2+1\ge x.$

Ez $\displaystyle a_3$-ra az $\displaystyle a_3> 2a_2$ feltételt szabja ki; a megtett útra $\displaystyle s_3-2a_2=y_3\le a_3$ és

$\displaystyle y_3+1=x+\frac{s_3}{2},$

ahonnan

$\displaystyle \frac{s_3}{x}=2+\frac{4a_2-2}{x}<2+\frac{8a_2-4}{2}=:c_3.$

Tegyük fel most, hogy a matematikus a negyedik lépés során találja meg a kutyáját; ekkor kezdetben az az $\displaystyle x$ pontban volt. A feltétel most $\displaystyle a_4+1\ge x+ (2a_2+2a_3+a_4)/2$, vagyis

$\displaystyle \frac{a_4}{2}-(a_3+a_2)+1\ge x>\frac{a_2}{2}+1;$

a második egyenlőtlenség annak okán, hogy a második lépés során még nem került meg a kutya. Ez $\displaystyle a_4$-re az $\displaystyle a_4>2a_3+3a_2$ feltételt szabja ki; a megtett útra pedig $\displaystyle s_4-2a_3-2a_2=y_4\le a_4$ és

$\displaystyle y_4+1=x+\frac{s_4}{2},$

ahonnan

$\displaystyle \frac{s_4}{x}=2+\frac{4a_3+4a_2-2}{x}<2+\frac{8a_3+8a_2-4}{a_2+2}=:c_4.$

Ezek után $\displaystyle n\ge 3$ szerinti indukcióval már könnyen igazolhatjuk annak szükséges és elégséges feltételét, hogy a matematikus az $\displaystyle n$-edik lépésben találja meg a kutyáját. Ez pontosan akkor következik be, ha a kutya kezdetben a $\displaystyle (-1)^nx$ pontban volt, és

$\displaystyle \frac{a_n}{2}-(a_{n-1}+\ldots+a_3+a_2)+1\ge x> \frac{a_{n-2}}{2}-(a_{n-3}+\ldots+a_3+a_2)+1,$

ami az $\displaystyle (a_n)$ sorozatra az $\displaystyle a_n> 2a_{n-1}+3a_{n-2}$ feltételt szabja ki. A megtett útra pedig

$\displaystyle \frac{s_n}{x}=2+\frac{4a_{n-1}+\ldots+4a_3+4a_2-2}{x}<2+ \frac{8(a_0+a_1+\ldots+a_{n-1})-4}{a_{n-2}-2(a_0+a_1+\ldots+a_{n-3})+2}=:c_n,$

ahol $\displaystyle {s_n}/{x}$ értéke $\displaystyle c_n$-et tetszőlegesen megközelítheti.

A matematikusnak tehát első lépésben olyan $\displaystyle S=(a_n)$ sorozatot kell választania, amelyre $\displaystyle a_0=a_1=0$ és $\displaystyle a_n>2a_{n-1}+3a_{n-2}$ teljesül minden $\displaystyle n\ge 2$ esetén, máskülönben a stratégia tartalmaz felesleges lépést, így nem lehet optimális. Ahhoz, hogy ezzel a stratégiával minden lehetséges $\displaystyle x>1$ érték esetén véges sok lépésben megtalálja a kutyát, szükséges és elégséges, hogy a

$\displaystyle b_n=\frac{a_n}{2}-(a_{n-1}+\ldots+a_3+a_2)+1$

sorozat minden határon túl nőjön. Tegyük fel tehát, hogy az $\displaystyle S$ sorozat kielégíti ezeket a feltételeket. A stratégia pontosan akkor működik a $\displaystyle c$ konstanssal, ha a $\displaystyle c_2,c_3,c_4,\ldots$ számok egyike sem nagyobb, mint $\displaystyle c$. A továbbiakban megmutatjuk, hogy a legkisebb megfelelő $\displaystyle c$ konstans értéke $\displaystyle c=98$.

Először is legyen $\displaystyle a>0$ és tekintsük az $\displaystyle a_0=a_1=0$, $\displaystyle a_n=6^{n-2}a$ ($\displaystyle n\ge 2$) sorozatot, ez nyilván kielégíti a fenti feltételeket. Erre a sorozatra minden $\displaystyle n\ge 4$ esetén

$\displaystyle c_n=2+\frac{8\cdot\frac{6^{n-2}-1}{5}\cdot a-4}{6^{n-4}a-2\cdot\frac{6^{n-4}-1}{5}\cdot a+2}< 2+\frac{8\cdot6^{n-2}a}{3\cdot6^{n-4}a}=98.$

Továbbá $\displaystyle c_2=2<98$, és $\displaystyle a\le 24,5$ esetén $\displaystyle c_3=4a_2\le 98$ is teljesül. Ez azt jelenti, hogy ha a matematikus először valamelyik irányba elmegy legfeljebb 122,5 métert, majd azt követően a kiindulási pontja körül oda-vissza haladva mindig 6-szorosára növeli a kiindulási ponttól vett távolságot, akkor bármely $\displaystyle x$ esetén legfeljebb $\displaystyle 98x$ hosszúságú utat kell megtennie ahhoz, hogy megtalálja (megpillantsa) elveszett kutyáját.

Most már csak annak az igazolása van hátra, hogy ha $\displaystyle c<98$, akkor bármely, a fent említett feltételeknek eleget tevő $\displaystyle S$ sorozat esetén lesz olyan $\displaystyle n$, amelyre $\displaystyle c_n>c$. Tekintsük az $\displaystyle u_n=a_0+a_1+\ldots+a_n$ sorozatot. Erre teljesül, hogy $\displaystyle u_0=u_1=0<u_2<u_3<\ldots$ és $\displaystyle u_n$ minden határon túl nő, valamint $\displaystyle n\ge 3$ esetén

$\displaystyle c_n=2+\frac{8u_{n-1}-4}{u_{n-2}-3u_{n-3}+2}.$

Tegyük fel indirekt, hogy minden $\displaystyle n$-re $\displaystyle c_n\le c<98$; ekkor egy rögzített $\displaystyle c-2 <c'<96$ konstansra elég nagy $\displaystyle n_0$ mellett minden $\displaystyle n\ge n_0$ esetén teljesül, hogy

$\displaystyle \frac{8u_{n}}{u_{n-1}-3u_{n-2}}\le c',$

vagyis $\displaystyle u_{n-1}-3u_{n-2}\ge c''u_n$, ahol $\displaystyle c''=8/c'>1/12$. Ez azt jelenti, hogy a nemnegatív, $\displaystyle n\ge 2$ esetén pozitív $\displaystyle v_n=u_n/6^n$ számokra $\displaystyle n\ge n_0$ esetén $\displaystyle 2v_{n-1}-v_{n-2}\ge (1+\kappa)v_n$, ahol $\displaystyle \kappa=12c''-1>0$. Más szóval, $\displaystyle n\ge n_0$ esetén $\displaystyle v_n-v_{n-1}\le (v_{n-1}-v_{n-2})- \kappa v_n$, ahonnan

$\displaystyle v_n-v_{n-1}\le (v_{n_0-1}-v_{n_0-2})-\kappa(v_n+v_{n-1}+\ldots +v_{n_0}).$

Ekkor van egy $\displaystyle n_1\ge n_0$ index, melyre $\displaystyle v_{n_1}-v_{n_1-1}=-\alpha<0$. Ez nyilvánvaló, ha a pozitív számokból álló $\displaystyle v_n$ sorozat 0-hoz tart. Ellenkező esetben pedig azért igaz, mert $\displaystyle \kappa(v_n+v_{n-1}+\ldots +v_{n_0})$ minden határon túl nő. Mármost minden $\displaystyle n> n_1$ esetén $\displaystyle v_n-v_{n-1}<-\alpha$, ahonnan

$\displaystyle v_n-v_{n_1}<(n-n_1)(-\alpha),\quad v_n<v_{n_1}-(n-n_1)\alpha$

adódik, vagyis elég nagy $\displaystyle n$ esetén $\displaystyle v_n<0$. Ez az ellentmondás igazolja állításunkat.

Statisztika:

13 dolgozat érkezett.
5 pontot kapott:	Schultz Vera Magdolna.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	10 versenyző.

A KöMaL 2012. márciusi matematika feladatai