Feladat:	B.4734	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Matolcsi Dávid
Füzet:	2016/május, 277 - 279. oldal		PDF  |  MathML
Témakör(ök):	Feladat, Logikai feladatok, Kombinatorikus geometria
Hivatkozás(ok):	Feladatok: 2015/október: B.4734

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   Megoldás. $a)$ A fertőzés teljes elterjedésének lehetségessé válásához kezdetben (legalább) $t^3$ fertőzött mező szükséges. Ennyi esetén valóban elő is fordulhat, hogy elterjed, például, ha kezdetben egy $t\times t\times t$-es részben helyezkednek el a fertőzött mezők. Ekkor ugyanis könnyen láthatóan 3 perc alatt minden mező megfertőződik: 1 perc után azok a sorok, amiket a $t\times t\times t$-es kocka sorai határoznak meg, 2 perc után azok a síkok, amiket a $t\times t\times t$-es kocka síkjai határoznak meg, végül 3 perc után a többi mező is. Annak bizonyítása, hogy ennél kevesebb fertőzött mező esetén nem lehetséges az elterjedés, a középiskolai tananyagon túlmutató bizonyítást igényel, lásd pl. a feladat internetes megoldásához betett cikket1.   Foglalkozzunk most a feladat $b)$ részével. ${2015}^3-{\left(2015-\left(t-1\right)\right)}^3$ fertőzött mező még nem biztos, hogy elegendő. Ha ennyi fertőzött mezőt úgy helyezünk el, hogy egy $\left(2015-\left(t-1\right)\right)$ élű kocka maradjon ki az egyik sarokban, akkor minden sorban (sor alatt a kocka valamelyik oldalélével párhuzamos sort értünk) csak $t-1$ fertőzött mező lesz, így a fertőzés nem terjed tovább. Ha viszont már ${2015}^3-{\left(2015-\left(t-1\right)\right)}^3+1$ mező fertőzött, akkor belátható, hogy biztosan megfertőződik az egész kocka. Nézzük meg, hány fertőzött mezőjétől fertőződik meg biztosan egy 2-dimenziós, $2015\times 2015$-ös ,,rétege'' a kockának. Ha lesz legalább $t$ darab olyan $x$ irányú sor, amiben legalább $t$ fertőzött mező van, akkor biztosan megfertőződik. Ha ez nem teljesül, az azt jelenti, hogy van legalább $2015-\left(t-1\right)$ darab $x$ irányú sor, amiben legfeljebb $t-1$ fertőzött mező van. A többi $t-1$ sorban legfeljebb 2015 fertőzött mező lehet, tehát ez összesen legfeljebb $\begin{array}{c}{\displaystyle \left(2015-\left(t-1\right)\right)\left(t-1\right)+2015\left(t-1\right)={2015}^2-{\left(2015-\left(t-1\right)\right)}^2\mathrm{.}}\end{array}$ Ha több $\left(t-1\right)$-nél kevesebb fertőzött mezőt tartalmazó sor van, az természetesen összességében még kevesebb fertőzött mezőt tesz lehetővé. Tehát ha ${2015}^2-{\left(2015-\left(t-1\right)\right)}^2$-nél több fertőzött mező van egy lapon, ott már muszáj legalább $t$ darab, legalább $t$ fertőzött mezőt tartalmazó sornak lennie, ezek az $x$ irányú sorok a következő percben teljesen megfertőződnek, így minden $y$ irányú sorban lesz legalább $t$ fertőzött mező, és így minden megfertőződik. Ugyanígy, ha van legalább $t$ darab olyan $x-y$ irányú ,,réteg'', amiben legalább ${2015}^2-{\left(2015-\left(t-1\right)\right)}^2+1$ fertőzött mező van, akkor biztosan megfertőződik az egész kocka, hiszen mint már megmutattuk, minden lap teljesen megfertőződik, és ezután minden $z$ irányú sorban lesz legalább $t$ fertőzött mező, így minden megfertőződik. Ha ez a feltétel nem teljesül, az azt jelenti, hogy van legalább $2015-\left(t-1\right)$ darab legfeljebb ${2015}^2-{\left(2015-\left(t-1\right)\right)}^2$ fertőzött mezőt tartalmazó lap, a többi $t-1$ pedig legfeljebb ${2015}^2$ fertőzött mezőt tartalmazhat, így összesen legfeljebb ${\displaystyle \begin{array}{c}\hfill {\displaystyle \left(2015-\left(t-1\right)\right)\left({2015}^2-{\left(2015-\left(t-1\right)\right)}^2\right)+{2015}^2\left(t-1\right)=}\hfill \\ \hfill {\displaystyle ={2015}^3-{\left(2015-\left(t-1\right)\right)}^3}\hfill \end{array}}$ fertőzött mező esetén nem lenne biztos, hogy minden mező megfertőződik. Tehát ${2015}^3-{\left(2015-\left(t-1\right)\right)}^3+1$ fertőzött mezőnél biztossá válik az egész kocka megfertőződése.   Megjegyzés. Az $a)$ részre maximum 1 pontot adtunk. A $b)$ rész 3 pontot ért, így a feladatra összesen 4 pontot lehetett legfeljebb kapni. A Versenyzőktől elnézést kér a matematika bizottság. 1Paul N. Balister, Béla Bollobás, Jonathan D. Lee, and Bhargav P. Narayanan: Line percolation; http://www.komal.hu/cikkek/egyeb/b4734cikk.pdf