![]() |
Az A. 943. feladat (2026. október) |
A. 943. Legyenek \(\displaystyle a_n\), \(\displaystyle b_n\) és \(\displaystyle c_n\) valós sorozatok, amelyekre a \(\displaystyle \vert a_n \vert\), \(\displaystyle \vert b_n \vert\), \(\displaystyle {\vert c_n \vert \leq d}\). Létezik-e olyan \(\displaystyle c>0\) valós, amelyre tetszőleges ilyen sorozatok mellett létezik előjelek olyan \(\displaystyle s_n\) sorozata (vagyis \(\displaystyle s_n\in \{1, -1\}\) minden \(\displaystyle n\)-re), hogy
\(\displaystyle \left\vert\sum_{n=1}^{N}s_na_n \right\vert, \quad\left\vert\sum_{n=1}^{N}s_nb_n\right\vert,\quad\left\vert\sum_{n=1}^{N}s_nc_n\right\vert \leq c \)
teljesül minden \(\displaystyle N\) pozitív egészre?
Javasolta: Németh Márton Tamás és Simon László Bence (Cambridge)
(7 pont)
A beküldési határidő 2026. november 10-én LEJÁRT.
Megoldás A válasz igen, van ilyen előjelezés. Fogalmazzuk át kicsit a feladatot: legyen \(\displaystyle \textbf{v}_n = \begin{pmatrix} a_n & b_n & c_n\end{pmatrix}^T\). Tudjuk, hogy \(\displaystyle \vert \textbf{v}_n \vert \leq \sqrt{3} d\). Ha létezik olyan \(\displaystyle s_n\) előjelezés, hogy
\(\displaystyle \left\vert\sum_{n=1}^{N}s_n\textbf{v}_n \right\vert \leq C\)
minden \(\displaystyle N\) pozitív egészre, akkor a feladatban megadott összegek mind kisebbek, mint \(\displaystyle C\), mivel \(\displaystyle \sum_{n=1}^{N}s_na_n\) éppen \(\displaystyle \sum_{n=1}^{N}s_n\textbf{v}_n\) \(\displaystyle x\) tengelyre való vetülete, tehát abszolút értéke legfeljebb \(\displaystyle C\).
Az általánosság megsértése nélkül tegyük fel, hogy \(\displaystyle d = 1/\sqrt{3}\), ekkor \(\displaystyle \vert \textbf{v}_n \vert \leq 1\). Jelölje a zárt egységgömböt \(\displaystyle B^3\).
Lemma: Léteznek olyan \(\displaystyle A_1, ..., A_k\) halmazok, amelyek uniója lefedi \(\displaystyle B^3\)-öt, és bármely \(\displaystyle \textbf{x}, \textbf{y} \in A_i\) pontokra \(\displaystyle \vert \textbf{x} - \textbf{y} \vert \leq 1\).
Bizonyítás: Minden \(\displaystyle \textbf{x} \in B^3\) pontra legyen \(\displaystyle B_x\) a tőle kisebb, mint \(\displaystyle \frac12\) távolságra levő pontok halmaza. Ekkor \(\displaystyle B_x\) nyílt és teljesül rá a fenti feltétel, és \(\displaystyle B_x\) halmazok uniója lefedi \(\displaystyle B^3\)-at. Mivel \(\displaystyle B^3\) zárt és korlátos ezért kompakt, tehát van véges sok \(\displaystyle B_x\) halmaz, ami fedi \(\displaystyle B^3\)-at, tehát az állítást beláttuk.
Most megmutatjuk, hogy \(\displaystyle C=k\) megfelelő. Ehhez először belátjuk, hogy minden \(\displaystyle m\) pozitív egészre tudunk választani olyan jó \(\displaystyle s_1, ..., s_m\) előjelezést, hogy
\(\displaystyle \left\vert\sum_{n=1}^{N}s_n\textbf{v}_n \right\vert \leq k\)
teljesül minden \(\displaystyle N \leq m\)-re. Az előjelek megállapításához a következő algoritmust adjuk: legyen \(\displaystyle V=\{\}\) kezdetben üres halmaz. Lépkedjünk végig az \(\displaystyle j=1, 2, \ldots, m\) indexeken. A \(\displaystyle j\)-edik lépésben sorrendben
- Adjuk hozzá \(\displaystyle V\)-hez a \(\displaystyle (\textbf{v}_j,j,-,0)\) értéket.
- Ha \(\displaystyle V\)-ben éppen nem található két olyan \(\displaystyle U=(\textbf{u},\alpha,-,\beta)\) és \(\displaystyle W=(\textbf{w},\gamma,-,\delta)\) érték, melyekre \(\displaystyle \textbf{u}\) és \(\displaystyle \textbf{w}\) vektorok ugyanabba az \(\displaystyle A_i\) halmazba esnek, akkor lépjünk a következő \(\displaystyle j\) indexre azonnal, különben
- vegyük ki \(\displaystyle U\)-t és \(\displaystyle W\)-t a \(\displaystyle V\) halmazból, és adjuk hozzá az \(\displaystyle (\textbf{u}-\textbf{w}, U, -, W)\) értéket \(\displaystyle V\)-hez.
- Előfordulhat, hogy egy ilyen módosítás után újra keletkezik két vektor \(\displaystyle V\)-ben, melyek egyazon \(\displaystyle A_i\) halmazba esnek, ilyenkor az előző lépést ismételjük addig, amíg lehet. Ez a folyamat véges, hiszen a \(\displaystyle V\)-ben található vektorok száma minden lépésben csökken.
Legyen \(\displaystyle S\) azon értékek halmaza, melyek a folyamat során szerepeltek a \(\displaystyle V\) halmazban (vagyis \(\displaystyle S\)-ben a közben kitörölt értékek is szerepelnek). Konstruáljuk meg az \(\displaystyle f: S\to \{\pm 1\}\) függvényt a következőképpen:
- Ha \(\displaystyle U\in V\) szerepel \(\displaystyle V\)-ben a folyamat végén, akkor legyen \(\displaystyle f(U)=1\).
- Ha \(\displaystyle U\)-t és \(\displaystyle W\)-t egy lépésben töröltük ki \(\displaystyle V\)-ből, akkor legyen \(\displaystyle f(U) = f\left[ (\textbf{u}-\textbf{v}, U, -, W) \right]\) illetve \(\displaystyle f(W) = -f\left[ (\textbf{u}-\textbf{v}, U, -, W) \right]\).
Könnyű látni, hogy a feltételek egyértelműen meghatározzák az \(\displaystyle f\) függvényt. Megjegyzendő, hogy \(\displaystyle f(U)=1\) helyett a \(\displaystyle V\)-beli értékekhez rendelt előjelek tetszőlegesek is lehetnek, a második feltétel fontos.
Legyen \(\displaystyle s_j = f\left[ (\textbf{v}_j, j, -, 0) \right]\). Azt állítjuk, hogy ez az előjelezés eleget tesz a feltételnek. Valóban, hiszen a konstrukció szerint
\(\displaystyle \sum_{n=1}^j s_n\textbf{v}_n \)
éppen egyenlő a \(\displaystyle V\)-ben a \(\displaystyle j\)-edik lépés befejezése után található vektorok (előjelezett) összegével. Mivel \(\displaystyle V\) mérete ekkor legfeljebb \(\displaystyle k\), és az \(\displaystyle A_i\) halmazok konstrukciója szerint a benne szereplő vektorok legfeljebb egységhosszúak, az állítást beláttuk.
Most tekintsük azt a fát, amelynek csúcsai az \(\displaystyle M\)-edik szinten az \(\displaystyle M\) hosszú \(\displaystyle \pm1\) sorozatok, amelyekre igaz, hogy ez a sorozat jó előjelezése az első \(\displaystyle M\) vektornak (a \(\displaystyle 0.\) szinten álljon egy csúcs, ami össze van kötve az első szinten levő csúcsokkal). Az \(\displaystyle s_1, \ldots, s_m\) csúcsból egy szinttel feljebb pontosan az \(\displaystyle s_1, \ldots, s_{m-1}\) csúcsba megy él (ez a csúcs is része a fának, mert a fenti definícióból következik, hogy ha \(\displaystyle s_1, ..., s_m\) jó előjelezés, akkor \(\displaystyle s_1, ..., s_{m-1}\) is egy jó előjelezés).
A kapott gráf egy fa, ahol csak szomszédos szintek közt mennek élek, és minden csúcsnak van pontosan \(\displaystyle 1\) eggyel feljebbi szinten levő szomszédja, és legfeljebb \(\displaystyle 2\) eggyel lentebbi szomszédja, tehát a fokszámok végesek. A fa végtelen, mivel a fentiek szerint van minden szinten legalább egy csúcsa. Ekkor a König-lemma szerint létezik végtelen hosszú, lefele haladó út a gyökérből, ami pont azt jelenti, hogy létezik a feladat feltételeinek megfelelő előjelezés.
Statisztika:
Az A. 943. feladat értékelése még nem fejeződött be.
A KöMaL 2026. októberi matematika feladatai
