 |
Az A. 908. feladat (2025. május) |
A. 908. Legyen \(\displaystyle n \geq 2\) egész szám. Piroska és a farkas egy olyan játékot játszanak, amelyben az \(\displaystyle \{1,2, \ldots ,n\}\) számokat színezik pirosra és kékre. Piroska minden körben mond egy \(\displaystyle (i,j)\) párt, ahol \(\displaystyle 1 \leq i < j \leq n\) és még \(\displaystyle i\) és \(\displaystyle j\) is színezetlen, majd farkas ezek egyikét kékre, a másikat pirosra színezi. A játék akkor ér véget, amikor az \(\displaystyle \{1,2, \ldots ,n\}\) számok közül legfeljebb egy kivétellel minden szám meg lett színezve. Mutassuk meg, hogy létezik egy olyan \(\displaystyle n\)-től nem függő \(\displaystyle c>0\) valós szám, és létezik Piroskának olyan stratégiája, amellyel biztosan el tudja érni, hogy a játék során valamikor legyenek olyan \(\displaystyle 1 \leq a \leq b \leq n\) számok, hogy az \(\displaystyle \{a, a+1, \ldots , b\}\) halmazban legalább \(\displaystyle c \cdot \sqrt[3]{n}\)-nel több szám legyen pirosra színezve, mint kékre.
Javasolta: Pálvölgyi Dömötör (Budapest)
(7 pont)
A beküldési határidő 2025. június 10-én LEJÁRT.
A megoldás során használjuk az \(\displaystyle [a,b]=\{a, a+1, \ldots , b\}\) jelölést tetszőleges \(\displaystyle a \leq b\) számokra, és az ilyen alakú halmazokat intervallumnak nevezzük. Először abban a speciális esetben oldjuk meg a feladatot, amikor \(\displaystyle n=k^3\) valamilyen \(\displaystyle k \geq 2\) egész számra. Azt állítjuk, hogy ebben az esetben \(\displaystyle c=\frac{1}{8}\) megfelelő. Ez nem éles, a megoldás során többször nagyvonalú becsléseket csinálunk, arra fókuszálunk, hogy minél kevésbé legyen technikás a bizonyítás.
Osszuk fel az \(\displaystyle [1,n]\) intervallumot \(\displaystyle k\) darab egyenlő méretű intervallumra, azaz legyen \(\displaystyle I_1=[1,k^2], I_2=[k^2+1, 2k^2], \ldots , I_k=[(k-1)k^2+1,k^3]\). Piroska csak arra fog figyelni, hogy melyik intervallumokból jelöl ki számokat, az intervallumokon belül teljesen mindegy melyik számra mutat. Legyen Piroska stratégiája a következő: megszámolja minden \(\displaystyle I_j\) intervallumba, hogy mennyi a színezett piros és a színezett kék pontok különbsége (előjelesen, azaz ez negatív, ha több kék pont van). Ha van két intervallum, amiben ez az érték ugyanannyi, és még mindkettőben van színezetlen pont, akkor választ egyet-egyet, és ezt adja a farkasnak. Amikor először nincs két ilyen intervallum, akkor Piroska megáll, azt állítjuk, hogy ezen a ponton lesznek megfelelő \(\displaystyle a \leq b\) értékek. (Ezek után tetszőlegesen befejezhetik a játékot, de ez már lényegtelen a feladat szempontjából.)
Megmutatjuk, hogy ez a stratégia tényleg működik. Tegyük fel, hogy lejátszottak egy játékot, amiben Piroska a fenti stratégiát követte. Legyen \(\displaystyle f_\ell(j)\) az az érték, hogy \(\displaystyle \ell\) lépés után mennyivel van több piros az \(\displaystyle I_j\) intervallumban, mint kék (előjelesen). A kulcs észrevétel a következő állítás:
\(\displaystyle \sum_{j=1}^k f_{\ell}(j)^2=\sum_{j=1}^k f_{\ell-1}(j)^2+2\)
minden \(\displaystyle \ell\) szám esetén, amíg Piroska nem állt meg (az \(\displaystyle f_0(j)\) értékeket definiáljuk 0-nak \(\displaystyle j=1,2,...,k\) esetén). Ez könnyen látható Piroska stratégiájából, mivel az \(\displaystyle \ell\). lépésben olyan \(\displaystyle I_i,I_j\) intervallumokból választ, melyekre \(\displaystyle f_{\ell}(i)=f_{\ell}(j)\). Legyen ez a szám \(\displaystyle x\). Bármit is lép a farkas, ezek közül az egyik \(\displaystyle x+1\) lesz, a másik \(\displaystyle x-1\). Tehát az
\(\displaystyle (x+1)^2+(x-1)^2-2x^2=2\)
azonosságból következik az állítás. Az állításnak a következő egyszerű következményére lesz szükségünk:
\(\displaystyle \sum_{j=1}^kf_\ell(j)^2\ge 2\ell, \)
ami könnyen bizonyítható teljes indukcióval.
Indirekt módon tegyük fel, hogy Piroska stratégiája nem működik, és gondoljuk meg mikor tud elakadni. Tegyük fel, hogy \(\displaystyle t\) lépés után akadt el, ekkor az indirekt feltevés szerint minden \(\displaystyle I_j\) intervallumban \(\displaystyle f_t(j) \leq \frac{k}{8}\). Továbbá az is látható, hogy \(\displaystyle f_t(j) \geq -\frac{k}{4}\), ugyanis \(\displaystyle t\) lépés után ugyanannyi piros szám van, mint kék, így ha az \(\displaystyle I_j\) intervallumban több, mint \(\displaystyle \frac{k}{4}\)-gyel több kék van, akkor vagy az \(\displaystyle I_1 \cup I_2 \cup \ldots \cup I_{j-1}\) vagy az \(\displaystyle I_{j+1} \cup I_{j+2} \cup \ldots \cup I_k\) intervallumban legalább \(\displaystyle \frac{k}{8}\)-nél több piros van, mint kék. Ebből következik, hogy az \(\displaystyle f_t(j)\) értékek (\(\displaystyle 1 \leq j \leq k)\) legfeljebb \(\displaystyle \frac{k}{2}\) különböző értéket vehetnek fel.
Nevezzünk egy \(\displaystyle I_j\) intervallumot telinek ha már minden szám színezett benne, különben használhatónak. Ha lenne két használható intervallum \(\displaystyle t\) lépés után, amin \(\displaystyle f_t(j)\) megegyezik, akkor Piroska még tudna lépni. Ezt összevetve az előző bekezdéssel azt kapjuk, hogy van legalább \(\displaystyle \frac{k}{2}\) teli \(\displaystyle I_j\) intervallum \(\displaystyle t\) lépés után, azaz legalább a számok fele be van színezve. Így \(\displaystyle t \geq \frac{n}{4}\), amiből
\(\displaystyle \sum_{j=1}^k f_{t}(j)^2 \geq \frac{n}{2}.\)
Azonban beláttuk, hogy \(\displaystyle |f_t(j)| \leq \frac{k}{4}\) minden \(\displaystyle 1 \leq j \leq k\) esetén, így
\(\displaystyle \sum_{j=1}^k f_{t}(j)^2 \leq k \cdot (k/4)^2=\frac{n}{16},\)
ami ellentmondás.
Gondoljuk meg, hogy ebből már a feladat állítása is következik, ha tovább csökkentjük a \(\displaystyle c\) konstanst. Legyen \(\displaystyle n \geq 8\) és legyen \(\displaystyle k\) az a legnagyobb szám, melyre \(\displaystyle k^3 \leq n\). Ekkor \(\displaystyle k \geq 2\). Az eddigiek alapján csak az \(\displaystyle [1,k^3] \subseteq [1,n]\) részintervallumot használva, Piroska tud garantálni \(\displaystyle \frac{k}{8}\)-cal több piros számot egy intervallumban, mint kéket. Azonban könnyen látható, hogy \(\displaystyle n<(k+1)^3<8k^3\), így
\(\displaystyle \frac{1}{16}\sqrt[3]{n} \leq \frac{k}{8},\)
tehát \(\displaystyle c=\frac{1}{16}\) választással igaz a feladat állítása minden \(\displaystyle n \geq 8\) esetén.
Végül \(\displaystyle c=\frac{1}{16}\) megfelelő az \(\displaystyle n \leq 7\) esetben is, ugyanis ekkor \(\displaystyle \frac{1}{16}\sqrt[3]{n}<1\), így az első lépés után tud Piroska egy egyetlen piros számot tartalmazó intervallumot választani.
Statisztika:
4 dolgozat érkezett. 7 pontot kapott: Bodor Mátyás, Tianyue DAI, Varga Boldizsár, Xiaoyi Mo.
A KöMaL 2025. májusi matematika feladatai