 |
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