 |
Az A. 935. feladat (2026. május) |
A. 935. Egy bűnöző az origóból indul, és a sík egész koordinátájú pontjain mozogva menekül. Egy lépésben mindig egy szomszédos rácspontra lép úgy, hogy kétszer egymás után nem halad ugyanabba az irányba. Tudjuk, hogy az első lépését felfele teszi meg, továbbá minden rácspontot pontosan egyszer érint útja során. Egy ügynök szintén az origóból indul, viszont nem látja a bűnözőt. Szerencsére a központban tudják követni a bűnöző mozgását, de csak a következő módon tudnak kommunikálni az ügynökkel: adott egy előre meghatározott \(\displaystyle S\subseteq \mathbb{N}\) végtelen halmaz, amelyre minden \(\displaystyle s\in S\) esetén a bűnöző \(\displaystyle s\)-edik lépése után küldenek egy 1-est vagy egy 2-est az ügynöknek. Az ügynök csak akkor mozog, amikor üzenetet kap, és mindig pontosan annyit, amennyit a bűnöző az utolsó üzenet óta lépett.
Mennyi
\(\displaystyle I=\inf_{S} \left(\lim_{n\rightarrow \infty} \dfrac{|S\cap \{1,2,3,\ldots,n\}|}{n} \right) \)
értéke az olyan \(\displaystyle S\) halmazok felett, amelyekre az ügynök egyértelműen követni tudja a bűnöző mozgását?
A bűnöző mozgását korlátozó szabályokról az ügynök és a központ is tud.
Javasolta: Németh Márton (Budapest)
(7 pont)
A beküldési határidő 2026. június 10-én LEJÁRT.
Megmutatjuk, hogy az infimum értéke \(\displaystyle I=1/2\).
Felső becslés: \(\displaystyle I\leq 1/2\), ehhez belátjuk, hogy az \(\displaystyle S=\{2, 4, 6, 8, \ldots\}\) halmaz megfelelő.
Tegyük fel, hogy a bűnöző már lépett néhányat, és rendre az \(\displaystyle (x_0, y_0), (x_1, y_1), \ldots, (x_n, y_n)\) mezőket érintette. Világos, hogy \(\displaystyle (x_0, y_0) = (0, 0)\) és \(\displaystyle (x_1, y_1) = (0, 1)\). Egy \(\displaystyle 0\leq i\leq n-3\) értéket nevezzünk balcsavarnak , ha az \(\displaystyle (x_i, y_i), (x_{i+1}, y_{i+1}), (x_{i+2}, y_{i+2})\) rácspontok által meghatározott négyzet negyedik csúcsa nem szerepel az \(\displaystyle (x_j, y_j)\) rácspontok között, illetve a bűnöző az \(\displaystyle i+1\)-edik lépése után balra fordult, és lépett \(\displaystyle (x_{i+1}, y_{i+1})\)-ről. Hasonlóan nevezzük jobbcsavarnak, ha jobbra lépett.
Állítás: Ha van olyan \(\displaystyle (x_{n+1}, y_{n+1}), \ldots\) folytatása a bűnöző útvonalának, mely megfelel a feltételeknek, akkor \(\displaystyle (x_, y_0), \ldots, (x_n, y_n)\) nem tartalmaz bal- és jobbcsavart is.
Bizonyítás: Az általánosság elvesztése nélkül tegyük fel, hogy \(\displaystyle i\) jobbcsavar, \(\displaystyle j\) balcsavar, \(\displaystyle 0\leq i<j\leq n-3\).
Legyen \(\displaystyle (a, b)\) a \(\displaystyle i\)-vel indexelt jobbcsavar három rácspontja által meghatározott négyzet negyedik csúcsa, \(\displaystyle (c, d)\) a \(\displaystyle j\)-vel indexelt balcsavarhoz tartozó negyedik csúcs. Két eset lehetséges: az első esetben az \(\displaystyle (x_{n+1}, y_{n+1}), \ldots\) sorozatban \(\displaystyle (a, b)\) szerepel előbb. Vegyük észre, hogy a bűnöző a páratlanadik lépéseiben függőlegesen, a párosadik lépéseiben vízszintesen halad. Mivel az is teljesül, \(\displaystyle x+y\) paritása megegyezik a lépés sorszámának paritásával, mely során a bűnöző \(\displaystyle (x, y)\)-ra lép, egyértelműen meg tudjuk határozni, hogy \(\displaystyle (a,b)\)-re ugyanolyan irányból érkezünk, mint \(\displaystyle (x_{i+1}, y_{i+1})\)-re.
Ennek megfelelően az ábrán látható két eset egyike áll fenn; az első esetben (mivel feltettük, hogy \(\displaystyle j<n-3\)) a bűnöző már nem tudja érinteni a \(\displaystyle (c,d)\) mezőt, a második esetben pedig teljesen bezárta magát.
Hasonlóan ellentmondásra jutunk, ha feltesszük, hogy \(\displaystyle (c,d)\)-re előbb jutunk, mint \(\displaystyle (a,b)\)-re, ezzel az állítást igazoltuk.
Térjünk vissza az eredeti állításra: megmutatjuk, hogy a bünöző a \(\displaystyle 2k+1\) és \(\displaystyle 2k+2\)-edik lépését a szóba jövő \(\displaystyle 4\) lehetőség közül legfeljebb \(\displaystyle 2\)-féleképpen teheti meg, világos, hogy ezzel igazolnánk a felső becslést.
\(\displaystyle k=0\)-ra ez teljesül, hiszen tudjuk, hogy a bűnöző felfelé teszi meg első lépését.
\(\displaystyle k>0\) esetén mozgassuk illetve tükrözzük a koordináta-rendszert úgy, hogy a bűnöző \(\displaystyle 2k-1\) és \(\displaystyle 2k\)-adik lépése a \(\displaystyle (0,0)\to (0, 1)\) és a \(\displaystyle (0, 1)\to (1, 1)\) legyen. Ha az \(\displaystyle (1, 0)\), \(\displaystyle (1, 2)\) rácspontok közül valamelyiket a bűnöző korábban érintette, a \(\displaystyle 2k+1\)-edik lépés egyértelmű, így kész vagyunk, tegyük fel, hogy ez a két mező szabad. Vegyük észre, hogy mivel a következő két lépés nem lehet \(\displaystyle (1,1)\to (1, 0)\to (0, 0)\), eleve csak \(\displaystyle 3\) lehetőség van.
Vagyis az utolsó eset, melyet még nem vizsgáltunk, amikor a \(\displaystyle (0, 2)\) és \(\displaystyle (2, 2)\) mezők is szabadok. Ebben az esetben azonban az út \(\displaystyle (1, 1)\to (1, 2)\to (2, 2)\) folytatása létrehozza a \(\displaystyle \{(0, 0), (0, 1), (1, 1)\}\) és \(\displaystyle \{(0, 1), (1, 1), (1, 2)\}\) jobb- és balcsavarokat, így készen vagyunk.
Alsó becslés: \(\displaystyle I\geq 1/2\). Ennek igazolásához tegyük fel, hogy a bűnöző első \(\displaystyle s\) lépése során a \(\displaystyle P = (0, 0)\to (0, 1)\to (1, 1)\to (1, 0)\to (2, 0)\to (2, 1)\to \ldots\) cikk-cakk alakzat mentén halad.
Ha \(\displaystyle s\) páros, és \(\displaystyle s\in S\), \(\displaystyle s+1, s+2, s+3\notin S\), akkor azt állítjuk, hogy a \(\displaystyle P\) út első \(\displaystyle s\) lépését \(\displaystyle 3\)-féleképpen is ki lehet egészíteni \(\displaystyle 3\) lépéssel, és az így kapott útvonalakat ki lehet egészíteni a rács egy megfelelő bejárásává. Valóban, a tengely-szimmetria, és \(\displaystyle s\) általános volta miatt az alábbi minta mindhárom esetet lefedi:
Legyen \(\displaystyle S=\{s_0, s_1, s_2, \ldots\}\), ahol \(\displaystyle s_0<s_1<\ldots\). Ekkor tudjuk, hogy \(\displaystyle 2\,|\,s_{i}\implies s_{i+1}-s_{i}\leq 2\), illetve ugyanezzel a konstrukcióval \(\displaystyle s_{i+1}-s_{i}\leq 3\) bármely \(\displaystyle i\)-re.
Jelölje \(\displaystyle A_n^d = |\{1\leq i\leq n\,|\,s_i-s_{i-1} = d\}|\) ahol \(\displaystyle d=1,2,3\). Az általánosság elvesztése nélkül tegyük fel, hogy \(\displaystyle s_0 = 2\). Azt állítjuk, hogy bármely \(\displaystyle n\)-re \(\displaystyle A_n^1\geq A_n^3\), és ha \(\displaystyle s_{n}\) páratlan, akkor \(\displaystyle A_n^1 > A_n^3\).
Ezt indukcióval bizonyítjuk, \(\displaystyle n=1\)-re teljesül az állítás. \(\displaystyle n+1\)-re ha \(\displaystyle s_n\) páros, akkor \(\displaystyle s_{n+1}-s_n\leq 2\), tehát \(\displaystyle A_{n+1}^3 = A_{n}^3\), kész vagyunk. Ha \(\displaystyle s_n\) páratlan, akkor \(\displaystyle A_{n}^1 > A_{n}^3\), vagyis \(\displaystyle A_{n+1}^1\geq A_{n+1}^3\), és egyenlőség csak akkor állhat fenn, ha \(\displaystyle s_{n+1}-s_n = 3\), vagyis \(\displaystyle s_{n+1}\) páros, kész vagyunk.
Végül vegyük észre, hogy ha \(\displaystyle I\) létezik, akkor
\(\displaystyle I = \lim_{n\to \infty} \frac{n}{1\cdot A_n^1 + 2\cdot A_n^2 + 3\cdot A_n^3} \geq \lim_{n\to \infty} \frac{n}{2\cdot (A_n^1 + A_n^2 + A_n^3)} = \lim_{n\to \infty} \frac{n}{2n} = \frac{1}{2}. \)
Statisztika:
Az A. 935. feladat értékelése még nem fejeződött be.
A KöMaL 2026. májusi matematika feladatai