A B. 4901. feladat (2017. október)

B. 4901. Törpfalván járvány ütötte fel a fejét azt követően, hogy csúf kórság fertőzött meg néhány törpöt. Szerencsére a betegségből minden törp egy nap alatt meggyógyul, és ezután egy napig immunissá válik, ám sajnos ezt követően újra fertőződhet. Az állapot megváltozása mindig éjszaka, alvás közben következik be. Kellemetlen, hogy a törpök még betegen sem adják fel azt a megrögzött szokásukat, hogy minden egyes nap minden barátjukat meglátogatják. Márpedig ha egy beteg törp egy nem immunis, egészséges törppel találkozik, az utóbbi bizonyosan megfertőződik. Mutassuk meg, hogy ha Törpfalván 100 törp él, akkor a járványnak a kitörését követő 101. napon már biztosan vége van.

BME VIK folklór

(6 pont)

A beküldési határidő 2017. november 10-én LEJÁRT.

Megoldás. Vezessük be a törpök barátság-gráfját, mely egy olyan irányítatlan gráf, ahol a csúcsok a törpök, és két törp között pontosan akkor fut él a gráfban, ha barátok. Osszuk a törpöket (csúcsokat) csoportokba: az első csoportot alkossák azok, akik kezdetben (az 1. napon) fertőzöttek. A második csoportba azok kerülnek, akiknek van barátjuk az első csoportban (de ők maguk nem tartoznak az 1. csoportba). És így tovább, ha a \(\displaystyle k\)-adik csoportot már meghatároztuk, akkor a még nem besorolt törpök közül azok, akiknek van barátjuk a \(\displaystyle k\)-adik csoportban, a \(\displaystyle (k+1)\)-edik csoportba kerülnek. Mindezt úgy is megfogalmazzuk, hogy egy törp pontosan akkor kerül a \(\displaystyle k\)-adik csoportba, ha a gráfban hozzá legközelebbi fertőzött törp tőle \(\displaystyle k-1\) távolságra van, vagyis van olyan fertőzött törp, aki elérhető belőle \(\displaystyle k-1\) élből álló úton, de ennél rövidebb úton nem juthatunk el tőle fertőzött törpig. Ha a soron következő csoport üres lenne, akkor befejezzük a csoportba osztást. Elképzelhető, hogy bizonyos törpök nem kerültek egyik csoportba sem (azok, akik a gráf olyan komponensébe esnek, melyben egyetlen fertőzött törp sincsen), ők szerencsések, mert egyáltalán nem fognak megfertőződni a járvány során, így velük a továbbiakban nem foglalkozunk, ezeket a törpöket (és a belőlük induló éleket) a gráfból is töröljük.

Világos, hogy legfeljebb 100 csoport alakult ki, hiszen a csoportok nem üresek. Azt állítjuk, hogy a gráfban élek csak csoportokon belül és szomszédos indexű csoportokba tartozó csúcsok között futnak. Tegyük fel indirekten, hogy van él egy \(\displaystyle k\)-adik csoportba tartozó \(\displaystyle u\) és egy \(\displaystyle l\)-edik csoportba tartozó \(\displaystyle v\) csúcs között, ahol \(\displaystyle k+2\leq l\). Ekkor \(\displaystyle v\)-ből lenne \(\displaystyle k+1\) hosszú út fertőzött csúcsba: az első élen elmegyünk \(\displaystyle u\)-ba, majd onnan továbbhaladunk az \(\displaystyle u\)-hoz tartozó \(\displaystyle k\) élből álló fertőzött csúcshoz vezető úton. Ez azonban \(\displaystyle k+1<l\) miatt ellentmondana annak, hogy \(\displaystyle v\) az \(\displaystyle l\)-edik csoportba tartozik, ami állításunkat igazolja.

Ezen kívül az is igaz, hogy \(\displaystyle k>1\) esetén a \(\displaystyle k\)-adik csoport minden tagjából indul él valamely \(\displaystyle (k-1)\)-edik csoportba tartozó csúcsba (hiszen különben nem került volna a \(\displaystyle k\)-adik csoportba).

Vizsgáljuk meg, hogyan terjed a fertőzés.

Az 1. napon az 1. csoport tagjai fertőzöttek, mindenki más egészséges.

A 2. napon a 2. csoport minden tagja fertőzött lesz (hiszen van 1. csoportbeli barátjuk), az 1. csoport tagjai immunisak, a többiek egyelőre egészségesek, hiszen nincs 1. csoportbeli barátjuk.

A 3. napon az 1. csoportbeliek egészségesek lesznek (hiszen előző nap immunisak voltak), a 2. csoport tagjai immunisak, a 3. csoportbeliek fertőzöttek (hiszen van 2. csoportbeli barátjuk), a többiek egészségesek.

Ezután az eddigiekhez teljesen hasonlóan a fertőzés ,,tovább vonul'': az \(\displaystyle i\)-edik napon az \(\displaystyle i\)-edik csoport tagjai fertőzöttek, az \(\displaystyle (i-1)\)-edik csoport tagjai immunisak, mindenki más egészséges. Indukcióval megmutatjuk, hogy ha mindez teljesül az \(\displaystyle i\)-edik napon, akkor az \(\displaystyle (i+1)\)-ediken is. Az \(\displaystyle (i+1)\)-edik csoport tagjai valóban fertőzöttek lesznek, hiszen mindegyiküknek van szomszédja az \(\displaystyle i\)-edik csoportban. Az \(\displaystyle i\)-edik csoportbeliek immunissá válnak, hiszen előző nap fertőzöttek voltak. Az \(\displaystyle (i-1)\)-edik csoport tagjai egészségesek lesznek, hiszen előző nap immunisak voltak. Minden más csoport tagjai egészségesek maradnak, hiszen nincs szomszédjuk az \(\displaystyle i\)-edik csoportban. Ezzel megmutattuk, hogy a betegség valóban a fenti minta szerint vonul végig a törpökön.

Ha a (nemüres) csoportok száma \(\displaystyle k\), akkor a \(\displaystyle k\)-adik napon a \(\displaystyle k\)-adik csoport tagjai fertőzöttek, a \(\displaystyle (k-1)\)-edik csoport tagjai immunisak, mindenki más egészséges, majd végül a \(\displaystyle (k+1)\)-edik napon a \(\displaystyle k\)-adik csoport tagjai immunisak, mindenki más egészséges. A következő napon mindenki egészséges, és innentől az is marad.

Tehát legfeljebb \(\displaystyle k+1\leq 101\) nap után a járványnak biztosan vége van.

Statisztika:

138 dolgozat érkezett.
6 pontot kapott:	61 versenyző.
5 pontot kapott:	21 versenyző.
4 pontot kapott:	17 versenyző.
3 pontot kapott:	17 versenyző.
2 pontot kapott:	12 versenyző.
1 pontot kapott:	8 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2017. októberi matematika feladatai