Регистрирайте сеРегистрирайте се

Задача 12.

Иди на страница Предишна  1, 2
 
   Форум за математика Форуми -> Задача на седмицата
Предишната тема :: Следващата тема  
Автор Съобщение
luboslav_p
Начинаещ


Регистриран на: 16 Feb 2008
Мнения: 33
Местожителство: София
Репутация: 12.6
гласове: 7

МнениеПуснато на: Wed Oct 15, 2008 1:57 pm    Заглавие:

Ще се опитам да напиша решението по възможно най-кратък и ясен начин. Като начало да спомена, че има супер много начини за разположение на началните заразени клетки и може почти половината редове и стълбове да са без заразена клетка и пак да заразим целия квадрат. За пример-заразяваме клетките от 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
Редовен


Регистриран на: 23 Jun 2008
Мнения: 228

Репутация: 25Репутация: 25Репутация: 25
гласове: 13

МнениеПуснато на: Thu Oct 16, 2008 7:48 pm    Заглавие:

Понеже си завършил поста си така:
... но ако имате въпроси или забележки казвайте.
пък на мен не ми стана много ясно,
та все пак да попитам: "Колко е най-малкия брой клетки ?"
Никъде в предишния пост, отговора на този въпрос не е написан в явен вид, а условието на задачата е:
Baronov написа:
Задача 12. Дадена е квадратна таблица с n реда и n стълба. ... Да се намери най-малкия брой клетки, които можем да "заразим", така че след известно време да се заразят всички клетки.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
luboslav_p
Начинаещ


Регистриран на: 16 Feb 2008
Мнения: 33
Местожителство: София
Репутация: 12.6
гласове: 7

МнениеПуснато на: Fri Oct 17, 2008 12:45 pm    Заглавие:

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


Регистриран на: 17 Apr 2008
Мнения: 2

Репутация: 3Репутация: 3Репутация: 3
гласове: 1

МнениеПуснато на: Fri Oct 17, 2008 7:07 pm    Заглавие:

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

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

Питам от интерес и любознателност, не е някаква заядливост. Още повече, че си разрешил да питаме ако нещо не е ясно.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
luboslav_p
Начинаещ


Регистриран на: 16 Feb 2008
Мнения: 33
Местожителство: София
Репутация: 12.6
гласове: 7

МнениеПуснато на: Fri Oct 17, 2008 8:20 pm    Заглавие:

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


Регистриран на: 05 Jan 2006
Мнения: 146
Местожителство: Ню Йорк, BG
Репутация: 57.9
гласове: 18

МнениеПуснато на: Sat Oct 18, 2008 10:29 pm    Заглавие:

Ей, това с периметъра е много хитро (никога нямаше да се сетя).
През седмицата ми хрумна решение, което като идея е подобно (даже същото) като твоето, но използва различно средство (не периметъра).
Дефиниция 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 ниво (Останалите въжможности могат да бъдат сведени до тази чрез подходяща ротация).

Пример:
Код:

            +--------.-+
            |        . |
            ............
            |        . |
            | (c x d). |
+-.-------+ +--------.-+
| .(a x b)|
| .       |
...........
| .       |
+-.-------+   


В този случай размерите на голямата таблица са (a + c + 1, b + d - 1).
Значи, за да докажем необходимостта, трябва да докажем неравенството:
[tex]Cl(a,b) + Cl(c,d) \geq Cl(a + c + 1, b + d - 1)[/tex]
[tex]\lceil \frac{a}{2} \rceil + \lceil \frac{b}{2} \rceil + \lceil \frac{c}{2} \rceil + \lceil \frac{d}{2} \rceil - Odd(a,b) - Odd(c,d) \geq \lceil \frac{a + c + 1}{2} \rceil + \lceil \frac{b + d - 1}{2} \rceil - Odd(a + c + 1, b + d - 1)[/tex]
Полагаме :
[tex]a = 2a' + \alpha[/tex]
[tex]b = 2b' + \beta[/tex]
[tex]c = 2c' + \gamma[/tex]
[tex]d = 2d' + \delta[/tex],
[tex]\alpha, \beta, \gamma, \delta \in \{0,1\} [/tex].

Получаваме :
[tex]a' + b' + c' + d' + \lceil \frac{\alpha}{2} \rceil + \lceil \frac{\beta}{2} \rceil + \lceil \frac{\gamma}{2} \rceil + \lceil \frac{\delta}{2} \rceil - Odd(\alpha, \beta) - Odd(\gamma, \delta) \geq a' + b' + c' + d' + \lceil \frac{\alpha + \gamma + 1}{2} \rceil + \lceil \frac{\beta + \delta - 1}{2} \rceil - Odd(\alpha + \gamma + 1, \beta + \delta - 1)[/tex]

За [tex]x \in \{0,1\} : \lceil \frac{x}{2} \rceil = x[/tex].
[tex]\alpha + \beta + \gamma + \delta - Odd(\alpha, \beta) - Odd(\gamma, \delta) \geq \lceil \frac{\alpha + \gamma + 1}{2} \rceil + \lceil \frac{\beta + \delta - 1}{2} \rceil - Odd(\alpha + \gamma + 1, \beta + \delta - 1)[/tex]
Също [tex]\lceil \frac{\alpha + \gamma + 1}{2} \rceil = \alpha + \gamma[/tex] и [tex]\lceil \frac{\beta + \delta - 1}{2} \rceil = b + d - 1[/tex]:
[tex]\alpha + \beta + \gamma + \delta - Odd(\alpha, \beta) - Odd(\gamma, \delta) \geq \alpha + \gamma + \beta + \delta - 1 - Odd(\alpha + \gamma + 1, \beta + \delta - 1)[/tex]
За [tex]x,y \in \{0,1\} : Odd(x,y) = xy[/tex]:
[tex]-\alpha \beta - \gamma \delta \geq - 1 - Odd(\alpha + \gamma + 1, \beta + \delta - 1)[/tex]
[tex]\alpha \beta + \gamma \delta \leq 1 + Odd(\alpha + \gamma + 1, \beta + \delta - 1)[/tex]

Изразът [tex]Odd(\alpha + \gamma + 1, \beta + \delta - 1)[/tex] приема стойност единица, тогава и само тогава, когато: [tex]\alpha = \gamma[/tex] и [tex]\beta = \delta[/tex]. В този случай получаваме:
[tex]2\alpha \beta \leq 2[/tex], което е вярно, тъй като [tex]\alpha,\beta \in \{0,1\}[/tex].
В другия случай нека за определеност [tex]\alpha \neq \gamma[/tex] :
[tex]\alpha \beta + \gamma \delta \leq 1[/tex], което е вярно, защото понеже [tex]\alpha \neq \gamma[/tex], някоe от двете събираеми от лявата страна задължително ще е 0.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Dian Atanasov<T1BLD>
Редовен


Регистриран на: 27 May 2009
Мнения: 132
Местожителство: ruse
Репутация: 6Репутация: 6Репутация: 6Репутация: 6Репутация: 6
гласове: 2

МнениеПуснато на: Fri May 29, 2009 7:11 pm    Заглавие:

в крайна сметка не разбрах колко е отговорът
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
martosss
VIP Gold


Регистриран на: 17 Mar 2007
Мнения: 3937
Местожителство: Somewhere over the rainbow
Репутация: 424.2Репутация: 424.2
гласове: 213

МнениеПуснато на: Sat May 30, 2009 9:54 pm    Заглавие:

T1BLD написа:
в крайна сметка не разбрах колко е отговорът
прочети трите поста на luboslav_p по-горе Wink
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Покажи мнения от преди:   
   Форум за математика Форуми -> Задача на седмицата Часовете са според зоната GMT + 2 Часа
Иди на страница Предишна  1, 2
Страница 2 от 2

 
Идете на:  
Не Можете да пускате нови теми
Не Можете да отговаряте на темите
Не Можете да променяте съобщенията си
Не Можете да изтривате съобщенията си
Не Можете да гласувате в анкети
You cannot attach files in this forum
Може да сваляте файлове от този форум
Copyright © 2005-2020 math10.com.