A B. 4734. feladat (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 \(\displaystyle t\) mező fertőzött \(\displaystyle (1 \le t \le 2015)\), ú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

\(\displaystyle a)\) válik lehetségessé,

\(\displaystyle b)\) lehetünk biztosak benne,

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

Javasolta: Mészáros Gábor (Budapest)

(6 pont)

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

Megoldási ötlet. Használjuk a feladat 2 dimenziós változatában (B. 4392. és B. 4403. feladatok) szereplő ötleteket.

Megoldásvázlat. a) A fertőzés teljes elterjedésének lehetségessé válásához kezdetben (legalább) \(\displaystyle 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 \(\displaystyle 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 \(\displaystyle t\times t\times t\)-es kocka sorai határoznak meg, 2 perc után azok a síkok, amiket a \(\displaystyle 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 lenti cikket. Erre a részre ezért maximum 1 pontot adtunk.

b) Vegyünk egy olyan elrendezést, amelyben a lehető legtöbb fertőzött mező van, de nem fertőződik meg minden. Ekkor nyilván már az első percben sem fertőződik meg új mező, ugyanis különben az egy perc utáni állapotban még több fertőzött mező lenne, de szintén nem terjedne el később sem teljesen a fertőzés. Vegyünk egy mezőt, ami nem fertőzött. Ennek \(\displaystyle x\) irányú sorában kell lennie legalább \(\displaystyle 2016-t\) nem fertőzött mezőnek, különben a mező rögtön megfertőződne. Az előbbi (legalább) \(\displaystyle 2016-t\) mező közül mindegyiknek az \(\displaystyle y\) irányú sorában kell lennie legalább \(\displaystyle 2016-t\) nem fertőzött mezőnek, különben egyből megfertőződnének. Ezek az \(\displaystyle y\) irányú sorok természetesen páronként diszjunktak, így kaptunk legalább \(\displaystyle (2016-t)^2\) nem fertőzött mezőt (ezek ugyanabban az \(\displaystyle x-y\) irányú síkban helyezkednek el), amelyek mindegyikének \(\displaystyle z\) irányú sorában kell lennie legalább \(\displaystyle 2016-t\) nem fertőzött mezőnek, vagyis a nem fertőzött mezők száma legalább \(\displaystyle (2016-t)^3\). Ebből következik, hogy ha kezdetben legalább \(\displaystyle 2015^3-(2016-t)^3+1\) fertőzött mező van, akkor a fertőzés biztosan elterjed mindenhova.

Ha viszont csak \(\displaystyle 2015^3-(2016-t)^3\) fertőzött mező van, akkor nem lehetünk biztosak abban, hogy minden megfertőződik, például ha kezdetben a nem fertőzött mezők egy \(\displaystyle (2016-t)\times (2016-t)\times (2016-t)\)-s kockát alkotnak, akkor már az első percben sem (és így később sem) fertőződik meg egyetlen mező sem.

Tehát a b) kérdésre az a válasz, hogy (legalább) \(\displaystyle 2015^3-(2016-t)^3+1\) fertőzött kocka esetén lehetünk biztosak abban, hogy minden megfertőződik.

Ez a 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.

Paul N. Balister, Béla Bollobás, Jonathan D. Lee, and Bhargav P. Narayanan: Line percolation

Statisztika:

61 dolgozat érkezett.
4 pontot kapott:	12 versenyző.
3 pontot kapott:	10 versenyző.
2 pontot kapott:	14 versenyző.
1 pontot kapott:	15 versenyző.
0 pontot kapott:	8 versenyző.
Nem versenyszerű:	2 dolgozat.

A KöMaL 2015. októberi matematika feladatai