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 file
Témakör(ök): Feladat, Logikai feladatok, Kombinatorikus geometria
Hivatkozás(ok):Feladatok: 2015/október: B.4734

Egy 2015 oldalélű kockarács néhány mezőjét (egységkockáját) ismeretlen fertőzés támadta meg. A fertőzés úgy terjed, hogy ha a kocka valamelyik oldalélével párhuzamos sorában legalább t mező fertőzött (1t2015), úgy egy perccel később a sorban minden mező fertőzötté válik. Határozzuk meg, hány, kezdetben fertőzött mező esetén
a) válik lehetségessé,
b) lehetünk biztosak benne,

hogy a fertőzés a kocka valamennyi mezőjét eléri.

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) t3 fertőzött mező szükséges. Ennyi esetén valóban elő is fordulhat, hogy elterjed, például, ha kezdetben egy t×t×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×t×t-es kocka sorai határoznak meg, 2 perc után azok a síkok, amiket a t×t×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.
20153-(2015-(t-1))3 fertőzött mező még nem biztos, hogy elegendő. Ha ennyi fertőzött mezőt úgy helyezünk el, hogy egy (2015-(t-1)) é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 20153-(2015-(t-1))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×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-(t-1) 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
(2015-(t-1))(t-1)+2015(t-1)=20152-(2015-(t-1))2.
Ha több (t-1)-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 20152-(2015-(t-1))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 20152-(2015-(t-1))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-(t-1) darab legfeljebb 20152-(2015-(t-1))2 fertőzött mezőt tartalmazó lap, a többi t-1 pedig legfeljebb 20152 fertőzött mezőt tartalmazhat, így összesen legfeljebb
(2015-(t-1))(20152-(2015-(t-1))2)+20152(t-1)==20153-(2015-(t-1))3


fertőzött mező esetén nem lenne biztos, hogy minden mező megfertőződik. Tehát 20153-(2015-(t-1))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