Много трудна

[1089]

Задачата е давана на състезанието "Акад. Кирил Попов", град шумен, 2008г., отборно състезание за 6 клас. Все още не съм намерил решение, нито познавам някои които да я е решил. Надявам се че вие ще помогнете(както винаги). Задачата е следната:
Дадена е квадратна дъска със страна 12, разделена на единични квадратчета. Дефинираме "ъгълче" като фигура, получена от квадрат със страна 2, след премахване на произволно единично квадратче. Да се намери минималния брой ъгълчета, които могат да се сложат върху дъската, така че да не може да се сложи нито едно повече, без да се застъпва с някои от поставените, или да стърчи извън дъската?

[martosss]

Ето нещо като идея - на поле 2х2 с 1 "запълнено квадратче" може да се постави "ъгълче", но на поле 2х2 с 2 запълнени квадратчета не може. Ако разделим мрежата на 6х6 плочки всяка с размери 2х2 , то във всяка плочка трябва да има поне две "запълнени" квадратчета, тоест общо 72 запълнени квадратчета, тоест 24 "ъгълчета". Това означава, че минималната теоретична бройка е 24, сега въпросът е дали може да я постигнем, тоест има ли наредба от 24 ъгълчета, при която във всяка "плочка" 2х2 има точно 2 използвани квадратчета и са така наредени, че не може да се сложи никъде другаде ъгълче.
Ако успееш да намериш такава подредба, то задачата ти е решена, аз ще си помисля, надявам се да открия

[allier]

Каква задача само ... лесно условие, ама голяма мъка да се направи пример. От един час търся начин с 24 фигурки, ама все не се получава.

[1089]

i az sam stigal do razsajdeniqta na martosss i sam namiral pokriwane s 25

[martosss]

Да, наистина покриването с 25 не е много трудно, но остава въпросът за 24 - дали това по средата може да го махнем ? Аз си мисля, че 25 ще е минимумът, защото ако разгледаме поле 4х12, не можем да го напълним с точно 8 ъгъла(или 24 квадратчета, които да са части от ъгълчета)-просто трябва да използваме повече. оттам ще ни трябва поне едно допълнително ъгълче.

Сега се сещам и за друго представяне - първоначално са пълни половината диагонали - така условието е изпълнено, само че нямаме ъгълчета. Сега трябва да "преместим" 24 от точките в съседна клетка, така че да се образуват ъгли със всички точки. Това би трябвало да не е възможно

[allier]

Проблемът е че задачата е за 6-ти клас .... Подобен пример за 25 намерих след 1-2 часа търсене А това в Шумен, доколкото си спомням, има точно 2 часа за целия отборен кръг. Да не говорим, че трябва и да се докаже, че 24 не става, което досега не съм измислил как става.

По принцип с твоите разсъждения, мартос, няма как да се направи доказателство. Аз се пробвах да тръгна от единия край и да стигна до конфигурация в квадрат 2 на 2, която задължава в съседния квадрат да има цяла фигурка (това автоматично гарантира, че са нужни поне 25 ф.) но като гледам твоя пример, проблемът се появява чак по средата, т.е. с такива директни разсъждения няма как да стане. Трябва да се състави друго разбиване на фигурки, в които броят на заетите от фигурки клетки, е поне определено число, и оттук да се стигне до изводът, че не може във всеки квадрат 2 на 2 от оригиналното разбиване да има точно по 2 заети от фигурки клетки.

[martosss]

След неколкодневно гледане моето шестокласно съзнание му дойде следната идея:
Нека разделим решетката на 2 секотра.
Първият е червен, в него трябва да има поне 18 запълнени квадратчета, тоест 6 ъгълчета, което съм показал как може да стане.

Вторият сектор е по-интересен. Интересното за него е, че има "външен ръб", по който ако сложим квадратчета "губим" от възможностите си. За да поясня какво имам предвид, ще изследвам покривателната способност на едно ъгълче.

Общо погледнато на решетката имаме 11 реда и 11 колони от области 2х2, общо 121, които се припокриват на места. Във вътрешността на решетката всяко квадратче участва в 4 области, а по контура на решетката - в 2 области.
Тъй като във всяка област трябва да има поне 2 квадратчета, то във тези 121 области ни трябват поне 242 квадратчета, за да е възможно да се покрият на теория. Ако имаме 3 или 4, ние "губим", защото запълваме вече пълни области, така че стремежът ни е да запълним решетката достатъчно рехавот по такъв начин, че да има точно по 2 квадратчета във всяка област.

Ако разгледаме едно ъгълче, то е съставено от 3 квадратчета, в общия случай всяко квадратче участва в 4 области, тоест едно ъгълче покрива 12 квадратчета от области, част от които се припокриват. Само че една от областите винаги съдържа цялото ъгълче. В тази област ние "губим" едното квадратче, тъй като за всяка област е достатъчно да има 2 пълни квадратчета, всяко следващо е "загуба", а в областта, която съдържа целия ъгъл, ние имаме 3 квадратчета. Затова от тази област ние ще го вадим от общия брой "полезни". По този начин за всяко ъгълче имаме 11 "полезни" квадратчета, които запълваме в общия брой.
На картинката всяка област, която е запълнена с 1 квадратче, е оцветена с тънко кръгче - 5 на брой
Всяка област с 2 пълни кавдратчета е оцветена с дебело кръгче. - 3*2 = 6 на брой
Средната област съдържа 3 квадратчета - от нея вадим едното, защото то не е полезно - областта се пълни от 2.
Така получаваме общо 11 полезни квадратчета от всяко ъгълче.

Така с 24 ъгълчета може да запълним общ брой от 24х12=264 квадратчета.
Трябва да имаме поне 242.
Засега всичко теоретично е наред - възможно е да се направи, но за в бъдеще няма да е така.

Идеята е да разделим полето на няколко части, в повечето от които може да наредим искания брой ъгълчета, но в някоя от тях не можем.
В случая в 1 част можем да наредим 6 ъгълчета - там сме използвали 18 квадратчета.

Остават ни 18 ъгълчета, или 198 "полезни" квадратчета, с които трябва да запълним втория сектор
Във 2 част обаче не можем да нередим 18, така че да я запълним.
Това ще се опитаме да докажем.

Ако дадено квадратче се намира във външния слой от клетки, то това квадратче покрива 2 вместо 4 области, тоест губим 2 области. Това означава, че ако имаме над 11 квадратчета по периферията, нашата задача става теоретично невъзможна, защото ще имаме 242 квадратчета за запълване и под 242 теоретично възможни.

Нека разгледаме най-добрият случай - нямаме нито едно квадратче по периферията - тогава обаче в ъглите се образуват 4 ъгълчета. Затова по периферията трябва да имаме поне 4 квадратчета - по едно, което да блокира всяко едно от тези потенциални ъгълчета в четирите края на решетката.
Нека всички други квадратчета освен тези 4 са празни.
Тогава следващия по-вътрешен слой от клетки трявба да е пълен, защото всеки две съседни клетки от периферията, заедно с някоя от съседните им клетки от по-вътрешния слой, образуват потенциално ъгълче.
Това означава, че трябва да имаме 40 квадратчета - 4 по периферията и 36 от по-вътрешния слой. Обаче тези 36 квадратчета могат да се образуват от поне 18 ъгълчета, защото едно ъгълче може да обхваща най-много две клетки от тези 36(в ъглите трябва да имаме ъгълче, което с едно квадратче "излиза" по периферията заради гореспоменатите потенциални ъгълчета в крайните области от решетката).
И така трябва да имаме поне 18 ъгълчета, 2 по две квадратчета на всяко от тях участва в по-вътрешния слой. 4 от останалите 18 квадратчета са по периферията, а останалите 14 си пречат. Ще го обясня по малко по-прост начин.

Всяко ъгълче може да се представи като две черти - една вертикална и една хоризонтална, които се допират в самото ъгълче. В случая ако погледнем хоризонталните редове, те са изградени от 6 хоризонтални черти, като съответно трябва да има и 6 вертикални, които да сочат към вътрешността(защото външния слой вече е "неутрализиран").
Тогава всяка от тези вертикални линии ще се допира до една от хоризонталните от чуждо ъгълче, с което в тази област 2х2 ще има 3 квадратчета, тоест трябва да извадим 1, и така за всеки от 14-те линии, които "стърчат".
Дотук получихме -8 от крайните квадратчета и -14 от стърчащите, общо -22, тоест от 264 ни остават точно 242.
Само е има и още нещо - на хоризонталните редове поне 2 от вертикалните линии се допират - имаме 6 вертикални линии, които се разполагат на 12 квадратчета и в крайните две няма, с което трява да извадим още 2, с което общата сметка става 240 квадратчета, с които трябва да запълним 242, което явно не става.
Това означава, че този случай не е възможен с 24 ъгълчета - трябват ни 25.
Би трябвало аналогично да се разгледат и другите случаи, при които имаме от 1 до 7 квадратчета по периферията, но тогава резултатите са същите, тъй като дори и да имаме такива квадратчета, то във вътрешния слой пак трябва да имаме почти всички запълнени квадратчета, така че сметката не излиза.

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

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

Надявам се всичко да е ясно, че никак не ме бива в обясненията - големи есета пиша.

[1089]

no martoss, zadaljitelno li e da e takowa pokriwaneto na watre6niq kwadrat?

[martosss]

Не е задължително, идеята е, че за покриването на вътрешния квадрат ни трябват ПОНЕ 6 ъгълчета(6 ъгълчета или повече), тоест поне 18 квадратчета. Това е така, защото ако разделим вътрешния квадрат на 3х3 области с площ 2х2, то във всяка от тези площи трябва да има ПОНЕ 2 квадратчета(2 или повече). Ако има 5 триъгълника и още 2 квадратчета "стърчат отвън" не може, теоретично не е възможно да се покрие.

А иначе това подреждане на вътрешния квадрат съм го дал като примерно, за да покажа, че с 6 ъгълчета Е ВЪЗМОЖНО да се покрие.
Принципно може с 6 да е теоретично възможно, но на практика да няма такава подредба(както става с квадрат 12х12), но при 6х6 има такова подреждане и аз го показвам. Но въпреки, че има, то за външния квадрат няма.
И е важно да се отбележи, че двете области са независими една от друга, тоест дори и от вътрешния квадрат да "стърчат" ъгълчета към външния, те не играят в запълването на крайните два слоя от цялата решетка.