Problem B. 4440. (March 2012)
B. 4440. On a winter's day, an absent minded mathematician went on a walk with his old poodle along a long straight alley. He was so absorbed in his thoughts that when he finally thought of his dog, he had to realize that it was not near him. In the snowfall, he did not see further than 5 metres. He did not see the dog in front of him, he did not see it behind either, and he did not know which direction it had gone. After a little thinking, he went to look for his poodle. The old poodle can only walk half as fast as its master. The mathematician chose a searching strategy, such that the following condition should hold for the smallest possible value of the constant c: if the dog is at a distance x from him then he needs to cover a distance of at most cx to find it. What is this smallest value of c?
(5 pont)
Deadline expired on April 10, 2012.
Sorry, the solution is available only in Hungarian. Google translation
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.
Statistics:
13 students sent a solution. 5 points: Schultz Vera Magdolna. 2 points: 1 student. 1 point: 1 student. 0 point: 10 students.
Problems in Mathematics of KöMaL, March 2012