Задача 12.

[luboslav_p]

Ще се опитам да напиша решението по възможно най-кратък и ясен начин. Като начало да спомена, че има супер много начини за разположение на началните заразени клетки и може почти половината редове и стълбове да са без заразена клетка и пак да заразим целия квадрат. За пример-заразяваме клетките от 1-ви ред и 1-ви стълб през една.
Сега към решението. Като начало да отбележим, че без значение е редът на заразяване на клетките т.е. може да считаме някои първоначално заразени клетки за "замразени" и да не заразяваме техни съседни. Ще считаме ,че имаме a заразени клетка на безкрайна дъска. Да отбележим, че ако в даден момент не може да заразяваме нови клетки, то всички заразени клетки в този момент ще образуват съвкупност от правоъгълници. Това,което ще доказваме е, че сумата от периметрите на тези правоъгълници не надвишава 4a, а това ще ни реши задачата. В началото общата сума на периметрите, която ще бележим с П е точно 4a.
1)От две заразени клетки може да получим квадрат 2х2 или правоъгълник 3х1. И в двата случая П остава 4a.
2)От заразена клетка и заразен правоъгълник nxk можем в най-добрия случай (когато клетката е на разстояние 2 от някоя от страните или е съседна по диагонал на някои от 4-те върха на правоъгълника) да получим правоъгълник (n+2)xk ; nx(k+2) ; (n+1)x(k+1). Тъй като и 3-ти правоъгълника имат периметри с 4 по-големи от този на правоъгълника nxk, то П не се изменя или по-точно не се увеличава.
3) От заразени правоъгълници nxk и mxl можем в най-добрия случай (когато върховете им са съседни по диагонал или по вертикала(хоризонтала) имат общи стълбове(редове) на разстояние 1) да получим правоъгълник (n+m)x(k+l) ; (n+l)x(k+m) ; (n+m+1)x(k+l-1) ; (n+m-1)x(k+l+1) ; (n+l+1)x(k+m-1) ; (n+l-1)x(k+m+1). Във всички случаи П не се променя. С това задачата е решена.
Опитал съм се решението да бъде максимално ясно и кратко, но ако имате въпроси или забележки казвайте.

[Реклама]

[dgs]

Понеже си завършил поста си така:
... но ако имате въпроси или забележки казвайте.
пък на мен не ми стана много ясно,
та все пак да попитам: "Колко е най-малкия брой клетки ?"
Никъде в предишния пост, отговора на този въпрос не е написан в явен вид, а условието на задачата е:

[luboslav_p]

Интересно, но действително не съм написал отговора. В момента, в който не може да заразяваме повече клетки с описаната операция, периметърът на получената(ите) фигура(фигури) е не повече от 4n, където n е броя на първоначално заразените клетки. Това значи че за таблица nxn трябват поне n първоначално заразени клетки.

[MitkoS]

Още в началото на задачата, martosss показа, че ако в таблица с размери nxn заразим единия от диагоналите (диагонала се състои от n клетки), то след n-1 минути цялата таблица ще е заразена - т.е., n на брой заразени клетки в началото са предостатъчни.
И доколкото разбирам, оттук нататък стои въпроса може ли с по-малко на брой от n.

И понеже се обърках в твоето решение, интересува ме горе-долу следното - кое от двете е вярно:
1. Твоето решение казва, че n заразени клетки в началото са достатъчни
2. Твоето решение казва, че n заразени клетки в началото са необходими

Питам от интерес и любознателност, не е някаква заядливост. Още повече, че си разрешил да питаме ако нещо не е ясно.

[luboslav_p]

Решението ми казва, че n клетки са необходими, а вече се убедихме, че има не едно и две разположения на n-те първоначално заразени клетки, които изпълняват условието.

[krassi_holmz]

Ей, това с периметъра е много хитро (никога нямаше да се сетя).
През седмицата ми хрумна решение, което като идея е подобно (даже същото) като твоето, но използва различно средство (не периметъра).
Дефиниция 1: Нека Odd(a,b) е характеристичната функция на свойството : a и b са нечетни, т. е.
Odd(a,b) = 1, ако a, b са нечетни числа,
Odd(a,b) = 0, иначе.

Ще докажем следната

Теорема: За заразяването на таблица a x b първоначално е необходимо и достатъчно да заразим:
[tex]Cl(a,b) = \lceil \frac{a}{2} \rceil + \lceil \frac{b}{2} \rceil - Odd(a,b)[/tex]
клетки.

1. Достатъчност.
Нека е дадена правоъгълната таблица T(a x b) (в долния ляв ъгъл се намира клетка (1,1)). Да заразим клетките:
(1, b), (1, b-2), (1, b-4), ...
Това са всички клетки от първия ред на таблицата, които се намират на четно разстояние от долния десен ъгъл. Броят им е точно:
[tex]\lceil \frac{b}{2} \rceil [/tex] .
Сега да заразим клетките:
(a, 1), (a-2, 1), (a-4, 1), ...
Това са всички клетки от първата колона на таблицата, които се намират на четно разстояние от горния ляв ъгъл. Техният брой е:
[tex]\lceil \frac{a}{2} \rceil[/tex] .
Това заразяване е смъртоносно(всички клетки ще се заразят след време). Да намерим броят на първоначално заразените клетки в него: трябва да съберем заразените клетки от първия ред и диагонал. Но в случай, че a и b са неченти, сме бреброили клетката (1, 1) два пъти. Така броя на първоначално участващите клетки в заразяването е:
[tex]\lceil \frac{a}{2} \rceil + \lceil \frac{b}{2} \rceil - Odd(a,b)[/tex],
което е точно Cl(a,b).

2. Необходимост.
Тук най-важната идея е, че заразата се разпространява в правоъгълници, т.е. при произволно начално заразяване, след като заразата се разпространи, ще се образуват правоъгълници от заразени, всеки 2 от които са на разстояние поне 2 клетки. Това наблюдение ни позволява да разглеждаме процеса на заразяване като процес на обединяване на "съседни" вече заразени правоъгълници (на разтояние 0 или 1 клетка един от друг). Ако разглеждаме едно смъртоносно заразяване по този начин, на предпоследната стъпка от заразяването, ще имаме 2 заразени съседни правоъгълника. Така задачата се свежда до показване, че сумата на необходимите първоначално заразени клетки във двата правоъгълника е не-по малка от предположената минимална бройка за цялата таблица.

Нека имаме 2 съседни правоъгълни таблици с размери (a x b) и (c x d). Най-оптималния начин, по който могат да бъдат разположени, е първия ред на едната и последния рез на другата да са на 1 ниво (Останалите въжможности могат да бъдат сведени до тази чрез подходяща ротация).

Пример:

[Dian Atanasov<T1BLD>]

в крайна сметка не разбрах колко е отговорът

[martosss]