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

Задача 12.

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


Регистриран на: 05 Jun 2008
Мнения: 316

Репутация: 55.4
гласове: 39

МнениеПуснато на: Sat Sep 27, 2008 2:18 pm    Заглавие: Задача 12.

Задача 12. Дадена е квадратна таблица с n реда и n стълба. Някои от квадратчетата в нея са "заразени" с вирус. Всяка минута вирусът се разпространява. Ако някоя клетка има 2 съседни (по страна) "заразени" клетки, то тя също става заразена (заразените вече клетки също остават заразени). Да се намери най-малкия брой клетки, които можем да "заразим", така че след известно време да се заразят всички клетки.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Реклама







Пуснато на:     Заглавие: Реклама

Върнете се в началото
martosss
VIP Gold


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

МнениеПуснато на: Sat Sep 27, 2008 5:55 pm    Заглавие:

Нека разгледаме квадрат 1х1, очевидно се нуждаем от 1 клетка
Нека разгледаме квадрат 2х2, ако заразим произволно една клетка, то ни трябва поне още 1, която да е поставена по диагонал на първата заразена клетка.
Ако разгледаме квадрат 3х3 и заразим произволна клетка, то отново ако заразим съседна на нея по диагонал ще получим 4 заразени клетки, ще ни остане още 1 колона и 1 редица, които имат обща клетка. От тук най-ефективният избор ще е да изберем точно тази обща клетка и да заразим нея, което ще ни даде общо 3 клетки за квадрат 3х3.

Тоест при таблица n x n ни трябват поне n заразени клетки - пример за заразяване на квадрат с n клетки е да заразим всяка една клетка от единият му диагонал.

Да допуснем че е възможно да заразим таблицата с n-1 клетки.

Да разгледаме таблица 2х2, която трябва да заразим само с 1 клетка.
Която и клетка да изберем, останалите 3 ще имат най-много 1 съседна заразена клетка, с което няма да се заразят, с което задачате е решена.

Отговор - нужни са ни n клетки.

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


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

МнениеПуснато на: Sat Sep 27, 2008 11:14 pm    Заглавие:

Още по-формално чаже да се докаже по индукция, като забележим, че трябва да има поне 1 заразена клетка в реда или колоната, с която разширяваме таблицата с 1.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
martosss
VIP Gold


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

МнениеПуснато на: Sun Sep 28, 2008 9:43 am    Заглавие:

да, това си го мислех, но пък ако примерно празният ред е по средата може от двете му страни да има заразена клетка, с което да се зарази и той, въпреки че няма нито една заразена клетка, примерно
1-1-1-0-0
1-1-1-0-0
0-0-0-0-0
0-0-1-1-1
0-0-1-1-1

Сега в 3-ти ред няма нито 1 заразена, но въпреки това целият ред рано или късно се заразява, друг е въпросът, че за да се разшири квадрат трябва да има единица по единият му диагонал... ама не ми се занимаваше... то всъщност най-лесно щеше да е ако кажем,
1) достатъчно е по единият диагонал да имаме само заразени клетки, за да заразим цялата фигура.

2) ако имаме с 1 клетка по-малко разглеждаме клетка 2х2 и доказваме, че е невъзможно Wink

Ама аз малко се поомотах в началото и го обясних прекалено надълго и нашироко Wink
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Baronov
Напреднал


Регистриран на: 05 Jun 2008
Мнения: 316

Репутация: 55.4
гласове: 39

МнениеПуснато на: Sun Sep 28, 2008 4:34 pm    Заглавие:

Честно казано, съмнявам се, че задачата може да се реши по индукция. Отговорът наистина е толкова. Ама това доказателство за оценката по индукция не ме кефи. Някак си идеята на индукцията е да правиш обратното. В смисъл от пример за по-малко да направиш пример за по-голямо. Тук ти трябва да докажеш, че нещо е невъзможно. Според мен не става с индукция. Всички разъждения от типа: "Това е най-оптимално", " като вземем разположението за н-1" и т.н. са неприложими. По индукция може би (казвам може би) може да се докаже някакво по - силно твърдение от типа "може най - малко с н и то само по тоя и тоя начин", ама и това изглежда сложно, защото начините да го направите с н са поне 2.
Това, което се опитвам да кажа с всичките тея глупости е, че горното решение е грешно ( или поне супер непълно). Дори и да разгледате подтаблица н-1хн-1, то там, може да има по-малко от н-1 заразени клетки и да се използват някои заразени клетки от останалия ред и стълб. Т.е. тук индукционното предположение според мен е безполезено.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
martosss
VIP Gold


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

МнениеПуснато на: Sun Sep 28, 2008 7:02 pm    Заглавие:

Така е, но все пак ако едно твърдение е вярно за една таблица от 10 000 реда и 10 000 колонки, то трябва да е вярно и за таблица от 2 реда и 2 колонки, нали? Laughing Това е... индукция по обратен ред... пък и какво лошо има? щом не става с малък квадрат не може да стане и с голям, не виждам нищо противоречиво в това Wink В случая мисля че няма смисъл да утежняваме решението допълнително, по-кратко е по-добре Confused
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Baronov
Напреднал


Регистриран на: 05 Jun 2008
Мнения: 316

Репутация: 55.4
гласове: 39

МнениеПуснато на: Sun Sep 28, 2008 10:51 pm    Заглавие:

martosss написа:
Така е, но все пак ако едно твърдение е вярно за една таблица от 10 000 реда и 10 000 колонки, то трябва да е вярно и за таблица от 2 реда и 2 колонки, нали?


Не!!! Не е задължително.
Мисля, че решението ти не е вярно. Crying or Very sad
Ще трябва да го напишеш доста подробно, за да му повярвам. Според мен въобще не е индукция идеята.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
r2d2
VIP


Регистриран на: 28 Feb 2007
Мнения: 1936
Местожителство: in the galaxy (Far Far Away)
Репутация: 311.2Репутация: 311.2
гласове: 179

МнениеПуснато на: Mon Sep 29, 2008 12:23 pm    Заглавие:

martosss написа:
Така е, но все пак ако едно твърдение е вярно за една таблица от 10 000 реда и 10 000 колонки, то трябва да е вярно и за таблица от 2 реда и 2 колонки, нали? Laughing ?


Това е безумно!
Пример: Броят на квадратчетата се дели на 10 е вярно за тази таблица и не е вярно са 2х2,3х3..
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
martosss
VIP Gold


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

МнениеПуснато на: Mon Sep 29, 2008 7:32 pm    Заглавие:

В крайна сметка аз доказвам, че твърдението е изпълнено за n.. след това отричането може да стане дори с 1 пример, в случая с n=2 Wink щом не е изпълнено при n=2, значи не може да е вярно и в общия случай(понеже n=2 е част от общия случай !) с което n остава решение Wink

Даже Г-жа Трупчева потвърди Laughing

r2d2 написа:
Това е безумно!
Пример: Броят на квадратчетата се дели на 10 е вярно за тази таблица и не е вярно са 2х2,3х3..


Вие искате да докажете някое твърдение, вярно за ВСИЧКИ такива таблици, откъдето то трябва да е вярно и за таблица 2x2, в случая щом не е вярно за нея, то значи не е вярно в общия случай, тоест n заразени клетки не е долната граница.

Надявам се да съм бил достатъчно ясен.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Methuselah
VIP


Регистриран на: 17 Feb 2007
Мнения: 1057
Местожителство: София
Репутация: 105.9
гласове: 20

МнениеПуснато на: Mon Sep 29, 2008 8:06 pm    Заглавие:

Леко си се пообъркал.
Ти доказваш, че за n имаме решение винаги, и допускаш, че може да стане и за n-1 в общия случай и даваш пример за 2х2. Доказваш, че n-1 не е решение. Кой ти казва, че отговорът е линейна функция на n?

Аз имам една идея за решение, ще я напиша довечера
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Baronov
Напреднал


Регистриран на: 05 Jun 2008
Мнения: 316

Репутация: 55.4
гласове: 39

МнениеПуснато на: Mon Sep 29, 2008 8:24 pm    Заглавие:

Да пратиш поздрави на Трупчева. Ей, тя ли ти е по математика. Ако е така трябва да се радваш.
За задачата. Не знам, ти верно ли си мислиш, че това е решение? Гледай сега какво трябва да докажеш. Имаш таблица нхн. Трябва да докажеш, че които и н-1 клетки да заразиш винаги ще има незаразени клетки. Това трябва да докажеш, пич. Не знам ти точно какво доказваш, но не е това. Ти ми казваш, понеже е вярно за н=2, то следва по индукция. НЕ!!!! Не знам как си излъгал Трупчева. Браво за това, аз не успях да я излъжа за никоя задача за 4-5 години.

П.С. Март, сори, че така те нареждам, ама ти си ми надеждата за задачата. Аз нямам време да я мисля, а ми е супер интересна.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Baronov
Напреднал


Регистриран на: 05 Jun 2008
Мнения: 316

Репутация: 55.4
гласове: 39

МнениеПуснато на: Mon Sep 29, 2008 8:36 pm    Заглавие:

Ето ги моите идеи (за 5-те минути, които мислих, докато писах задачата).
Наистина мисля, че индукцията не е начина. Пробвайте да оцветите таблицата в някви цветове или да пишете някви числа в клетките, които да събирате (умножавате после). Нещо такова трябва да е. Освен това диагоналът не е единственото разположение за н клетки. Можем да заразим всички черни клетки (при шахматно оцветяване с горна лява клетка черна) във най-горния ред и най-левия стълб, при нечетно н и белите клетки при четно н. Пак получаваме пример с н заразени начални клетки. Имайте го предвид като решавате ( ако докажете, че само по диагонал става няма да е вярно).
Сега трябва да ходя тука на няква работа и няма да мога да мисля по задачата.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
martosss
VIP Gold


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

МнениеПуснато на: Mon Sep 29, 2008 9:36 pm    Заглавие:

ок, ето моите по-обобщени разсъждения:
1. Ясно е, че диагонал от n заразени клетки определя квадрат от заразени клетки със страна n.
Нека имаме заразен правоъгълник от n*k клетки
За ново заразяване имаме два варианта:
1- да заразим клетка на разстояние 1 стена от правоъгълника, при което получаваме нов "заразен" правоъгълник с измерения (n+2)*k или n(k+2)
2- да заразим клетка по някой диагонал, при което получаваме нов правоъгълник с размери (n+1)(k+1).
3- ако приложим "1" два пъти върху различни стени получаваме правоъг. със страни (n+2)(k+2) - същото ще приложим и при прилагане на "2" два пъти, тоест двата варианта дават еднакъв резултат ако бъдат приложени четен брой пъти, като първият е приложен равен брой пъти върху не-успоредните страни на правоъгълника.

Нека започнем с произволна клетка, може да я считаме за квадрат 1х1.

Тъй като трябва да заразим фигура квадрат е безразлично дали ще приложим "2" или "1" два пъти - и при двете резултатът е един и същ.

Сега нека започнем с произволно заразена клетка(квадрат със страна 1), показахме, че при заразяване не е от значение къде ще сложим клетка, така че нека слагаме по диагонал.

Нека ни е дадена клетка - която е на разстояние k и m от страните на квадрата(k и m са разстоянията до по-близката страна, разбира се! ).

Нека k и m са четни числа, като n-k-1 и n-m-1 cъщо са четни числа.

Достатъчно е да поставим клетки през 1 квадратче от дадената, докато стигнем до стените на големия квадрат. това ни дава [tex]\frac{m}{2}+\frac{n}{2}+\frac{n-k-1}{2}+\frac{n-m-1}{2}[/tex] клетки, тоест n-1 клетки, като отбележим и началната стават точно n.

Ако едно (или три) от тези числа е нечетно, в крайна сметка ще получим отново квадрат, който от едната си страна ще е на разстояние 1 клетка

Мисля че това е по-добро обяснение, как от произволна клетка да заразим целия квадрат - като слагаме клетка през 1 квадратче докато стигнем стените на големия квадрат... макар че за диагоналите да се докаже същото като че ли е по-добре...

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


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

МнениеПуснато на: Thu Oct 02, 2008 1:03 pm    Заглавие:

off ne mojelo po induktsiq - vsi4ko moje da se dokaje po induktsiq. Kato sedna na kompa she pisha dokazatelstvoto.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Baronov
Напреднал


Регистриран на: 05 Jun 2008
Мнения: 316

Репутация: 55.4
гласове: 39

МнениеПуснато на: Thu Oct 02, 2008 1:59 pm    Заглавие:

krassi_holmz написа:
off ne mojelo po induktsiq - vsi4ko moje da se dokaje po induktsiq. Kato sedna na kompa she pisha dokazatelstvoto.


Офф, добре де, това е моето мнение. Пиши, ще четем, ама гледай да не е като на марто. Изобщо решение с индукция, което използва думата "достатъчно" вместо "необходимо" е грешно и въобще няма смисъл да се гледа (тук визирам последното решение на мартос).
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
martosss
VIP Gold


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

МнениеПуснато на: Thu Oct 02, 2008 8:19 pm    Заглавие:

Добре де, аз съм казал, че не съм сигурен в решението си, сега осещам и че сте прави относно х, то наистина може да не е линейна функция на х, така че наистина не ми е пълно решението Confused

Впрочем много поздрави и от Трупчева Very Happy Тя наистина не усети този недостатък Smile Ама наистина работата е тънка...
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
krassi_holmz
Редовен


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

МнениеПуснато на: Fri Oct 03, 2008 9:00 pm    Заглавие:

ПРЕПОРЪКА - ако ще четете това по-добре си вземете лист и химикал.
2ПРЕПОРЪКА - това не е истинско решение, защото съм мързелив (май препоръката е към мене)
3ПРЕПОРЪКА - ГРЕШНО Е!
Първо да въведа малко терминология - приемаме, че в nxn таблица А клетка (1,1) е в долния ляв ъгъл. Обединението на n-тия ред и стълб да наречем коса на А, а (n-1)x(n-1) таблицата, получена от А след отстраняване на косата й - тяло на А. Нашата индукция ще се базира на релациите между косата и тялото в произволна таблица.
Първо да си формулираме индукционната хипотеза - това че n заразени стигат и за заразяването на nxn таблица ми се струваше малко слабо твърдение за индукционната хипотеза (просто не позволява да се извлече повечко информация за таблица с по-голям ред), както и по-нататък в процеса на разсъжденията се оказа, и понеже примера с диагоналите направо се набива на очи, и диагоналите ми се струват достатъчно екстремна конфигурация в nxn таблица, реших малко да усиля индукционното предположение, а именно че минималния брой заразени за заразяването на nxn таблица е n, и че това става само ако заразените са по диагонала. Първите случаи дават солидна база на индукцията.
Да приемем, че сме доказали твърдението за n по индукция. Съжалявам, но няма да се стремя да формализирам и доказвам достатъчно аргументите си, чрез което тотално развенчавам това като нормално "доказателство". Да вземем една таблица (n+1)x(n+1) B и да я разделим на коса и тяло. Има два начина да се опитаме по оптимален начин да заразим В. Първо, можем да опитаме да заразим тялото по оптимален начин и да се надяваме че и косата ще прихване от заразата. И тук идва характерното свойство на разделянето на таблицата на тяло и коса, а именно, че всяка клетка от косата има максимум една съседна клетка от тялото и обратно. Това означава, че косата не може да се зарази само от тялото, и че в косата има поне една предварително заразена клетка. Другия вариант, на който можем да се надяваме, е като заразим ключови клетки от косата, те да ни помогнат, да ни "облекчат" работата по заразяването на тялото. Оказва се, че и това не е възможно. За да се убедим в това, използваме "отражение" на косата върху тялото. Нека имаме произволно заразяване на В. Всеки заразен от косата на В го отразяваме в тялото на В по следния начин: ако заразеният се намира в (n+1)x(n+1), преместваме го в nxn, ако се намира в n+1-вия ред го сваляме на n-тия (в същата колона), а ако се намира в n+1-вата колона, го местим наляво по реда в n-тата. Оставям на вас доказателството, че една такава операция не увеличава общия брой първоначално заразени квадратчета (може да го намали, ако след операцията 2 заразени са се оказали в едно квадратче, което е развосилно на 1 заразен в квадратчето), и не намаля броя здрави клетки в тялото на В след заразяването. Тази операция може също така да се разглежда като изображение инекция на всички възможни заразявания на (n+1)x(n+1) таблица върху всички възножни заразявания на nxn таблица. Понеже операцията може само да намали броя на начално заразените и да увеличи крайния брой на заразените, следва, че ако искаме да заразим с n първоначално заразени таблицата B, трябва, след като приложим операцията върху тази наша хипотетична екстремална зараза, да получим екстремална зараза на тялото на В. Но то има размер nxn. Тук идва на помощ индуктивното предположение, и по-точно усилената му форма - вече знаем точно как изглеждат екстремалните заразявания за тялото на В. Остава да разгледаме няколко случая и да проверим, че не можем да разширим екстремалните заразявания на тялото върху цялата В, като използваме само n зарази. Окончателно, стигаме до противоречие, че с n зарази не може да се зарази В, и индукцията се затваря.


Последната промяна е направена от krassi_holmz на Fri Oct 03, 2008 10:36 pm; мнението е било променяно общо 1 път
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
krassi_holmz
Редовен


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

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

Baronov написа:
Честно казано, съмнявам се, че задачата може да се реши по индукция. Отговорът наистина е толкова. Ама това доказателство за оценката по индукция не ме кефи. Някак си идеята на индукцията е да правиш обратното. В смисъл от пример за по-малко да направиш пример за по-голямо. Тук ти трябва да докажеш, че нещо е невъзможно. Според мен не става с индукция. Всички разъждения от типа: "Това е най-оптимално", " като вземем разположението за н-1" и т.н. са неприложими. По индукция може би (казвам може би) може да се докаже някакво по - силно твърдение от типа "може най - малко с н и то само по тоя и тоя начин", ама и това изглежда сложно, защото начините да го направите с н са поне 2.
Това, което се опитвам да кажа с всичките тея глупости е, че горното решение е грешно ( или поне супер непълно). Дори и да разгледате подтаблица н-1хн-1, то там, може да има по-малко от н-1 заразени клетки и да се използват някои заразени клетки от останалия ред и стълб. Т.е. тук индукционното предположение според мен е безполезено.

Е Баронов, не ти бях дочел мнението докрай, затова да ме извиняваш че съм обяснявал втори път че условието на задачата е слабо за индукция.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
zhivko_sh
Начинаещ


Регистриран на: 22 Feb 2008
Мнения: 37

Репутация: 20.5Репутация: 20.5
гласове: 12

МнениеПуснато на: Fri Oct 03, 2008 9:34 pm    Заглавие: diagonal

Съжалявам, брато, обаче примера с диагоналите далеч не е единствен. Действително вземи таблица 5 на 5 и сложи заразени клетки в единия диагонал ама без централната, вместо нея сложи в съседна по другия диагонал, т.е.:

0 0 0 0 1
0 1 0 1 0
0 0 0 0 0
0 1 0 0 0
1 0 0 0 0

където 1 е заразена клетка, а 0 не е. Според мен е някво отцветяване, но не съм я мислил по-подробно.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
zhivko_sh
Начинаещ


Регистриран на: 22 Feb 2008
Мнения: 37

Репутация: 20.5Репутация: 20.5
гласове: 12

МнениеПуснато на: Fri Oct 03, 2008 9:36 pm    Заглавие:

Tova, koeto se opitvam da ti kaja e, 4e nqma kak da si vzeme6 podobno indukcionno predpolojenie, za6toto to ne e vqrno, koeto predpolaga, 4e cqloto ti re6enie se precakva. Sad
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Methuselah
VIP


Регистриран на: 17 Feb 2007
Мнения: 1057
Местожителство: София
Репутация: 105.9
гласове: 20

МнениеПуснато на: Sun Oct 05, 2008 12:48 pm    Заглавие:

Деф. Ред = Хоризонтал или вертикал.

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

Показваме, че за n първоначално заразени клетки има решение.

Допускаме, че има решение за n-1 клетки.
Тогава съществуват най-малко един вертикал и един хоризонтал, на които няма заразени клетки. Празният хоризонтал и празният вертикал разделят таблицата на 4 подтаблици. (Не може да имаме празни редове в началото и края на таблицата).
Твърдение 1: за да може да премине заразата от една подтаблица в нейна съседна (да се зарази поле от празния хоризонтал/вертикал) е необходимо в началната позиция да съществува вертикал/хоризонтал с поне 2 заразени клетки на него.
Доказателството не мисля, че е трудно, ще го напиша после, ако е нужно.
Твърдение 1 и максималният брой начални заразени клетки показват, че съществува поне още един празен ред от таблицата.
Прилагайки същите разсъждения, ще получим, че сме в случай 1) или 2)
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
zhivko_sh
Начинаещ


Регистриран на: 22 Feb 2008
Мнения: 37

Репутация: 20.5Репутация: 20.5
гласове: 12

МнениеПуснато на: Sun Oct 05, 2008 1:07 pm    Заглавие:

4esno kazano ne razbrah mnogo tvurdenie 1 kakvo iska6 da kaje6, no ako e tova, koeto si mislq, ne sum siguren 4e e vqrno, zatova ako moje6 pi6i kratko dokazatelstvo na tova tvurdenie.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
zhivko_sh
Начинаещ


Регистриран на: 22 Feb 2008
Мнения: 37

Репутация: 20.5Репутация: 20.5
гласове: 12

МнениеПуснато на: Sun Oct 05, 2008 1:33 pm    Заглавие:

mejdu drugoto martosss daje i otgovora da e lineina funkciq, tova pak ne ti dava pravo da kaje6 6tom za 10000x10000 e taka, zna4i i za 2x2 e taka. Moje prosto otgovora da e nqkva funkciq(dori i lineina), no tq da e v sila da kajem za n>10, a v drugite slu4ai otgovora da ne otgovarq na tazi funkciq i za seki slu4ai se namira otdelno. tipi4en primer e 4 zada4a na JBMO 2006.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Methuselah
VIP


Регистриран на: 17 Feb 2007
Мнения: 1057
Местожителство: София
Репутация: 105.9
гласове: 20

МнениеПуснато на: Sun Oct 05, 2008 2:06 pm    Заглавие:

Ок.
Имаме правоъгълна таблица с един празен хоризонтал (k-ти) , който разделя таблицата на 2 (горна част и долна част).
Казвам, че за да се зарази все някога клетка от празния хоризонтал е необходимо в началната позиция да съществува ред с поне 2 заразени клетки на него.
Д-во:
Индукция.
За таблица 3х1 е очевидно.
Допускаме , че е вярно за таблица с размери по-малки от mxn.
Доказваме за mxn.
Нека клетка j е първата клетка от празния k-ти хоризонтал, която ще се зарази след известно време.
За да се случи това е необходимо да са заразени клетка j от к-1ви хоризонтал и клетка j от к+1ви хоризонтал. Aко тези две клетки са първоначално заразени твърдението е вярно (има две първоначално заразени клетки на j-ти вертикал).
В противен случай, например няма заразена клетка от (1,j) до (к-1, j) получаваме таблица k-1 на n с празен j-ти вертикал ( взимаме горната част) , за която прилагаме индукционното предположение и получаваме, че има поне две първоначално заразени клетки на 1 ред.


П.п. хора, нямате ли кирилица? Ще е удобно да се сложи един кирилизатор на форума както във forum.uni-sofia.bg например.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
zhivko_sh
Начинаещ


Регистриран на: 22 Feb 2008
Мнения: 37

Репутация: 20.5Репутация: 20.5
гласове: 12

МнениеПуснато на: Sun Oct 05, 2008 8:24 pm    Заглавие:

Добре де, да кажем, че от k-1,j и k+1,j поне едната не е първоначално заразена. Как оттам следва, че целия вертикал от 1,j до k-1,j няма заразена клетка. Ти това го имаш само за k-1,j , че не е заразена. А и след това да кажем, че докажеш, че има ред с поне 2 пурвоначално заразени клетки. И какво? Как ще продължиш? Сори, че така те питам за някои неща, които на теб сигурно са ти ясни, но само ти си знаеш решението и е ясно, че не можеш да го пишеш много подробно, затова обясни, за да се оформи ясно и пълно решение. Wink
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Methuselah
VIP


Регистриран на: 17 Feb 2007
Мнения: 1057
Местожителство: София
Репутация: 105.9
гласове: 20

МнениеПуснато на: Sun Oct 05, 2008 9:33 pm    Заглавие:

zhivko_sh написа:
Добре де, да кажем, че от k-1,j и k+1,j поне едната не е първоначално заразена. Как оттам следва, че целия вертикал от 1,j до k-1,j няма заразена клетка?
Или в (1,j) : (k-1,j) няма зараза, или в (k+1,j) : (n,j) няма. Ако и на двете места има, то твърдението е вярно. Понеже на едно от двете места няма, прилагам индукционната хипотеза и доказвам твърдението. Няма проблеми за въпросите - нали е форум
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Baronov
Напреднал


Регистриран на: 05 Jun 2008
Мнения: 316

Репутация: 55.4
гласове: 39

МнениеПуснато на: Tue Oct 07, 2008 10:25 am    Заглавие:

Methuselah написа:
Ок.
Имаме правоъгълна таблица с един празен хоризонтал (k-ти) , който разделя таблицата на 2 (горна част и долна част).
Казвам, че за да се зарази все някога клетка от празния хоризонтал е необходимо в началната позиция да съществува ред с поне 2 заразени клетки на него.


Дори и това да е така, може да имаш 2 празни реда и само един ред с 2 заразени клетки в него.
Т.е. общо пак имаш n-1 заразени клетки.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
zhivko_sh
Начинаещ


Регистриран на: 22 Feb 2008
Мнения: 37

Репутация: 20.5Репутация: 20.5
гласове: 12

МнениеПуснато на: Tue Oct 07, 2008 10:56 am    Заглавие:

Да, и аз точно това щях да напиша. Wink
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Methuselah
VIP


Регистриран на: 17 Feb 2007
Мнения: 1057
Местожителство: София
Репутация: 105.9
гласове: 20

МнениеПуснато на: Tue Oct 07, 2008 2:36 pm    Заглавие:

Baronov написа:
Methuselah написа:
Ок.
Имаме правоъгълна таблица с един празен хоризонтал (k-ти) , който разделя таблицата на 2 (горна част и долна част).
Казвам, че за да се зарази все някога клетка от празния хоризонтал е необходимо в началната позиция да съществува ред с поне 2 заразени клетки на него.


Дори и това да е така, може да имаш 2 празни реда и само един ред с 2 заразени клетки в него.
Т.е. общо пак имаш n-1 заразени клетки.

Ако имаш 2 празни реда, тогава или имаш най-малко два реда с най-малко две заразени клетки, или един ред с най-малко 3 заразени клетки, което ни върши абсолютно същата работа за разсъжденията.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Baronov
Напреднал


Регистриран на: 05 Jun 2008
Мнения: 316

Репутация: 55.4
гласове: 39

МнениеПуснато на: Tue Oct 07, 2008 3:06 pm    Заглавие:

Methuselah написа:
Baronov написа:
Methuselah написа:
Ок.
Имаме правоъгълна таблица с един празен хоризонтал (k-ти) , който разделя таблицата на 2 (горна част и долна част).
Казвам, че за да се зарази все някога клетка от празния хоризонтал е необходимо в началната позиция да съществува ред с поне 2 заразени клетки на него.


Дори и това да е така, може да имаш 2 празни реда и само един ред с 2 заразени клетки в него.
Т.е. общо пак имаш n-1 заразени клетки.

Ако имаш 2 празни реда, тогава или имаш най-малко два реда с най-малко две заразени клетки, или един ред с най-малко 3 заразени клетки, което ни върши абсолютно същата работа за разсъжденията.

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

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