 |
Az A. 874. feladat (2024. február) |
A. 874. Nyihaha és Bruhaha két egymás melletti sziget, mindkettőn \(\displaystyle n\) ember él.
Nyihaha lakói mind Lovagok, akik mindig igazat mondanak, vagy Lókötők, akik mindig hazudnak. Bruhaha lakói normális emberek, akik azt modnanak amit akarnak. Mindkét szigeten hagyomány egy rituálé: amikor egy hajós érkezik a szigetre, akkor minden lakó véletlenszerűen (egyenletes eloszlással és egymástól függetlenül) rámutat egy másik szigetlakóra, és azt mondja ,,Ő Lovag'' vagy ,,Ő Lókötő''. Nyihaha szigetén a Lovagok az igazat, a Lókötők hazugságot mondanak arról, akire mutatnak. Bruhaha szigetén pedig mindenki, egymástól függetlenül \(\displaystyle 1/2\) valószínűséggel mondja ezt vagy azt.
Szindbád megérkezik Bruhaha szigetére, de eredetileg nem tudja, melyik szigeten van. Megfigyelve a rituálét, \(\displaystyle p_n\) valószínűséggel lát olyat, amiből egyértelműen meg tudja állapítani, hogy nem Nyihahán van. Igaz-e, hogy \(\displaystyle p_n \to 1\), ha \(\displaystyle n\to \infty\)?
Javasolta Matolcsi Dávid (Berkeley)
(7 pont)
A beküldési határidő 2024. március 11-én LEJÁRT.
Irányított gráfot képzünk a szigetlakók közt, ami azt jelzi, hogy ki mutat kire. A gráfban értelemszerűen mindenkinek \(\displaystyle 1\) a kifoka. Ha valaki lovagnak nevezett valaki mást, akkor \(\displaystyle 0\)-t írunk az élükre, ha lókötőnek, akkor \(\displaystyle 1\)-et. A csúcsokra is \(\displaystyle 0\) és \(\displaystyle 1\) értékeket írunk modulo \(\displaystyle 2\), és a csúcsok egy megszámozását jónak nevezzük, ha minden élre igaz, hogy ha \(\displaystyle A\)-ból él mutat \(\displaystyle B\)-be és az élen \(\displaystyle x\) érték szerepel, akkor \(\displaystyle b=a+x\), ahol \(\displaystyle a\) és \(\displaystyle b\) az \(\displaystyle A\) és \(\displaystyle B\) csúcsokra írt értékek.
Pontosan akkor történhet a mutatás Nyihahán, ha van jó számozása a csúcsoknak. Ugyanis pontosan akkor nincs ellentmondás a mutatásokkal, ha mindig, ha \(\displaystyle A\) lovagnak nevezi \(\displaystyle B\)-t, akkor ugyanolyan kasztba tartoznak, míg ha \(\displaystyle A\) lókötőnek nevezi \(\displaystyle B\)-t, akkor különböző kasztba. Így ha a lovagokat jelöljük az egyik számmal, és a lókötőket a másikkal, akkor pontosan akkor nincs ellentmondás a mutatásokkal, ha ez egy jó számozást ad.
Pontosan akkor lehet jól számozni a gráf csúcsait, ha minden irányított körben páros sok \(\displaystyle 1\)-es szerepel. Ugyanis világos, hogy ha egy körben páratlan \(\displaystyle 1\)-es szerepel, akkor a kör nem számozható jól, és ha nincs ilyen kör, akkor helyes számozás érhető el úgy, hogy minden összefüggőségi komponensben megválasztjuk tetszőlegesen az értékét az egyik csúcsnak, és a szabályok szerint meghatározzuk a szomszédjai értékét, majd azok szomszédjait, és végül a teljes öszefüggőségi komponensét.
Ha Bruhahán a mutatások gráfjában \(\displaystyle t\) darab irányított kör van, akkor minden kör diszjunkt (mert minden kifok \(\displaystyle 1\)). Minden körből kiválasztunk egy élt, és ezek kivételével a gráf minden élére ráírunk egy értéket. Bárhogy írtuk is be az értékekeket, a kiválasztott élek mindegyikének \(\displaystyle \frac{1}{2}\) valószínűsége van, hogy olyan értéket kap (azt mondja az az ember a mutatás után), ami párossá teszi a körében az \(\displaystyle 1\)-esek számát. A \(\displaystyle t\) kiválasztott élen független, hogy ez megtörténik-e, így \(\displaystyle \frac{1}{2^t}\) a valószínűsége, hogy minden él olyan értéket kap, hogy az összes körben páros sok \(\displaystyle 1\)-es szerepeljen.
Tehát ha Bruhahán a mutatások gráfjában \(\displaystyle t\) kör van, akkor \(\displaystyle \frac{1}{2^t}\) valószínűséggel hangzanak el olyan bemondások, hogy Szinbád azt hihesse, hogy ez akár Nyihahán is történhetne.
Azt látjuk be, hogy minden \(\displaystyle t\)-re igaz, hogy ahogy \(\displaystyle n\to \infty\), úgy Bruhaha szigetén \(\displaystyle 1\)-hez tart annak a valószínűsége, hogy legalább \(\displaystyle t\) kör van a gráfban. Ezzel megoldanánk a feladatot:
Tetszőleges \(\displaystyle \varepsilon>0\)-ra igaz, hogy létezik \(\displaystyle t\), amire \(\displaystyle \frac{1}{2^t}<\frac{\varepsilon}{2}\), és létezik \(\displaystyle N\), hogy ha legalább \(\displaystyle N\)-en laknak a szigeten, akkor \(\displaystyle \frac{\varepsilon}{2}\)-nél kisebb a valószínűsége, hogy \(\displaystyle t\)-nél kevesebb kör lesz a mutatási gráfban. Ekkor ha legalább \(\displaystyle N\)-en laknak a szigeten, akkor annak a valószínűsége, hogy a mutatásaik és bemondásaik nyihahainak tűnhetnek, az legfeljebb \(\displaystyle \frac{\varepsilon}{2}+1\cdot \frac{1}{2^t}<\varepsilon\). Mivel ez minden \(\displaystyle \varepsilon\)-ra igaz, ez azt jelenti, hogy valóban \(\displaystyle p\to 1\) ahogy \(\displaystyle n\to \infty\).
Most lássuk be, hogy valóban \(\displaystyle 1\)-hez tart annak a valószínűsége, hogy legalább \(\displaystyle t\) kör lesz.
Mivel mindenki egymástól függetlenül mutat egy másik lakóra egyenletes valószínűséggel, ezért lényegtelen, hogy milyen sorrendben mutatnak az emberek. Az alábbi módon szervezzük meg a mutatások sorrendjét:
Elindulunk egy véletlenszerű embertől. Ő rámutat valakire, az rámutat valakire, és így követjük a mutatások sorát, amíg vissza nem érünk egy olyan emberhez, aki már mutatott. Ezután újra véletlenszerűen választunk egy embert, aki még nem mutatott, és elkezdjük követni az általa indított mutatási láncot, amíg oda nem ér valakihez, aki már mutatott. És így tovább, amíg nem mutat az összes ember.
Ebben a sorrendben szakaszokra vágjuk a mutatások sorát. Azt mondjuk, hogy egy \(\displaystyle k\) hosszú szakasz során Esemény történik, ha a \(\displaystyle k\) ember egyike sem mutat vissza olyan emberre, aki már a szakasz előtt mutatott, de a szakasz második \(\displaystyle \frac{k}{2}\) embere közül legalább az egyik mutat valakire a szakasz első \(\displaystyle \frac{k}{2}\) embere közül.
Ha egy szakaszban Esemény történik, akkor van a második félben egy \(\displaystyle A\) ember, aki visszamutat egy, az első félben lévő \(\displaystyle B\) emberre. Ha \(\displaystyle B\)-ből lánc vezet \(\displaystyle A\)-ba, akkor ez egy kört alkot szakaszon belüli emberekből. Ha \(\displaystyle B\)-ből nem vezet lánc \(\displaystyle A\)-ba, az csak úgy lehet, ha a szakasz közben új láncot kellett kezdeni, azaz ha a szakasz egy tagja olyan emberre mutatott, aki mutatott már korábban. De az esemény definíciója szerint ez nem lehet a szakasz előtt sorra került ember, így ez is csak a szakaszon belüli embereket tartalmazó kör lehet. Tehát ha Esemény történik egy szakaszban, akkor van egy kör a szakasz embereiből, azaz legalább annyi kör van a gráfban, ahány szakaszban Esemény történik.
Vegyünk egy szakaszt, amely \(\displaystyle k\) hosszú, és \(\displaystyle r\) ember mutatott már a szakasz előtt. Annak a valószínűsége, hogy a szakaszból semelyik ember nem mutat egy szakasz előtti emberre, az \(\displaystyle (1-\frac{r}{n})^k\). Ha ez teljesül, akkor annak a feltételes valószínűsége, hogy a szakasz második felében senki sem mutat a szakasz első felébe az \(\displaystyle (1-\frac{\frac{k}{2}}{n-r})^{\frac{k}{2}}\). Így annk a valószínsége, hogy Esemény történik a \(\displaystyle r+1\)-edik emberrel kezdődő szakaszban az
\(\displaystyle \left(1-\frac{r}{n}\right)^k\left(1-\left(1-\frac{\frac{k}{2}}{n-r}\right)^{\frac{k}{2}}\right)\ge \left(1-\frac{r}{n}\right)^k\left(1-\left(1-\frac{\frac{k}{2}}{n}\right)^{\frac{k}{2}}\right)\)
Legyen a szakaszok hossza sorra \(\displaystyle \sqrt{n}, \frac{\sqrt{n}}{\sqrt{2}}, \frac{\sqrt{n}}{\sqrt{3}} \ldots\), amíg ezekkel el nem érjük az \(\displaystyle n\)-edik embert.
Az \(\displaystyle m\)-edik szakasz előtti emberek száma
\(\displaystyle r=\sqrt{n} \sum_{k=1}^{m-1} \frac{1}{\sqrt{k}}\le \sqrt{n} \left(1+\sum_{k=2}^{m-1} \frac{2}{\sqrt{k-1}+\sqrt{k}}\right)=\sqrt{n}\left(1+2\sum_{k=2}^{m-1} (\sqrt{k}-\sqrt{k-1})\right) < 2\sqrt{n}\sqrt{m}.\)
Így \(\displaystyle \frac{r}{n} < \frac{2\sqrt{m}}{\sqrt{n}}\).
Így annak a valószínűsége, hogy az \(\displaystyle m\)-edik szakaszban Esemény történik, az legalább
\(\displaystyle \left(1-\frac{2\sqrt{m}}{\sqrt{n}}\right)^{\frac{\sqrt{n}}{\sqrt{m}}}\left(1-\left(1-\frac{1}{2\sqrt{n}\sqrt{m}}\right)^{\frac{\sqrt{n}}{2\sqrt{m}}}\right).\)
Csak \(\displaystyle m\le \sqrt{n}\)-ig vizsgáljuk a szakaszokat. Ismert, hogy \(\displaystyle (1-x)^{\frac{1}{x}}\to e^{-1}\) ahogy \(\displaystyle x\to 0\). Ha \(\displaystyle m\le \sqrt{n}\) és \(\displaystyle n\) kellően nagy, akkor \(\displaystyle \frac{2\sqrt{m}}{\sqrt{n}}\) kellően kicsi, így \(\displaystyle (1-\frac{2\sqrt{m}}{\sqrt{n}})^{\frac{\sqrt{n}}{\sqrt{m}}}\) nagyon közel van \(\displaystyle e^{-\frac{1}{2}}\)-hez, amiről annyit használunk, hogy nagyobb, mint \(\displaystyle \frac{1}{2}\) (hiszen \(\displaystyle e<4\)).
Tehát az Esemény valószínűsége legalább
\(\displaystyle \frac{1}{2} \left(1-\left(1-\frac{1}{2\sqrt{n}\sqrt{m}}\right)^{\frac{\sqrt{n}}{2\sqrt{m}}}\right).\)
A zárójelen belül a kivonandót felülről becsülve
\(\displaystyle \left(1-\frac{1}{2\sqrt{n}\sqrt{m}}\right)^{\frac{\sqrt{n}}{2\sqrt{m}}}\le \frac{1}{\left(1+\frac{1}{2\sqrt{n}\sqrt{m}}\right)^{\frac{\sqrt{n}}{2\sqrt{m}}}}\le\frac{1}{1+\frac{1}{4m}},\)
ahol a második becslés a Bernoulli-egyenlőtlenség (azaz \(\displaystyle (1+x)^n\ge 1+xn\) ha \(\displaystyle n\) természetes szám és \(\displaystyle x\ge -1\) valós) alapján történt:
\(\displaystyle \left(1+\frac{1}{2\sqrt{n}\sqrt{m}}\right)^{\frac{\sqrt{n}}{2\sqrt{m}}}\ge 1+\frac{1}{4m}.\)
Végül pedig
\(\displaystyle \frac{1}{1+\frac{1}{4m}}\le 1-\frac{1}{5m},\)
így azt kapjuk, hogy az Esemény valószínűsége legalább
\(\displaystyle \frac{1}{2}\left(1-\left(1-\frac{1}{5m}\right)\right)=\frac{1}{10m}.\)
Az, hogy az egyes szakaszok során történik-e Esemény, független. Így tetszőleges \(\displaystyle d\) maradékra modulo \(\displaystyle t\), annak a valószínűsége, hogy \(\displaystyle m=\sqrt{n}\)-ig a \(\displaystyle t\)-vel osztva \(\displaystyle d\) maradékot adó sorszámú szakaszok egyikében sincs Esemény, az legfeljebb
\(\displaystyle \prod_{j=0}^{\frac{\sqrt{n}}{t}} \left(1-\frac{1}{10(jt+d)}\right)\le \sqrt[10t]{{\prod_{i=10t+1}^{10\sqrt{n}}} \left(1-\frac{1}{i}\right)}=\sqrt[10t]{\frac{10t}{10\sqrt{n}}}=\frac{\sqrt[10t]{t}}{\sqrt[20t]{n}}.\)
Tehát annak a valószínűsége, hogy mindegyik maradékosztályra történik Esemény olyan maradékú sorszámú szakaszban, az legalább
\(\displaystyle \left(1-\frac{\sqrt[10t]{t}}{\sqrt[20t]{n}}\right)^t\ge 1-\frac{t\sqrt[10t]{t}}{\sqrt[20t]{n}}\)
(az utóbbi egyenlőtlenség is a Bernoulli miatt teljesül).
Mivel \(\displaystyle t\) rögzített, ezért ahogy \(\displaystyle n\to \infty\), úgy
\(\displaystyle 1-\frac{t\sqrt[10t]{t}}{\sqrt[20t]{n}}\to 1.\)
Ezzel beláttuk, amit akartunk, hogy minden rögzített \(\displaystyle t\)-re igaz, hogy ahogy \(\displaystyle n\to 1\), úgy \(\displaystyle 1\)-hez tart annak a valószínűsége, hogy legalább \(\displaystyle t\) Esemény történik, tehát legalább \(\displaystyle t\) kör van a mutatások gráfjában.
Statisztika:
7 dolgozat érkezett. 7 pontot kapott: Wiener Anna. 4 pontot kapott: 1 versenyző. 3 pontot kapott: 1 versenyző. 2 pontot kapott: 1 versenyző. 1 pontot kapott: 1 versenyző. 0 pontot kapott: 2 versenyző.
A KöMaL 2024. februári matematika feladatai