Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem B. 4901. (October 2017)

B. 4901. An epidemic broke out in Smurf village after a few residents contracted a disease. Luckily, every smurf recovers from the illness in one day, and then they will be immune to the disease for another day. However, from the following day onwards they may catch the disease again. The transition between the sick and healthy states always occurs at night when the smurfs are sleeping. Unfortunately, the smurfs never give up their habit of visiting all their friends every day, not even when they are ill. So when a sick smurf meets a healthy but not immune one, the latter will inevitably catch the disease. Given that Smurf village has 100 inhabitants, show that the epidemic will necessarily terminate by the 101th day following the outbreak.

Collected at the Budapest Univ. Technology and Economics

(6 pont)

Deadline expired on November 10, 2017.


Sorry, the solution is available only in Hungarian. Google translation

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.


Statistics:

138 students sent a solution.
6 points:61 students.
5 points:21 students.
4 points:17 students.
3 points:17 students.
2 points:12 students.
1 point:8 students.
0 point:2 students.

Problems in Mathematics of KöMaL, October 2017