Покриващи многоъгълници - най-голям брой оцветени клетки без правоъгълник
Дадена е дъска 4х4. Колко най-много клетки можем да оцветим така, че да не можем да намерим правоъгълник образуван от центровете на 4 клетки и страни успоредни на тези на дъската?
Забележете, че ако две двойки клетки се намират в едни и същи редове / стълбове, то тогава се образува правоъгълник от този вид:
Можем да забележим, че всеки ако разменим кои да е два реда или кои да е два стълба, то дадените четири клетки отново ще образуват правоъгълник.
В този тип нива, един подход който можем да разгледаме е да изберем стълба/реда с най-много оцветени клетки и да го поставим най-отляво.
Ако в този стълб има 4 клетки, то в останалите стълбове можем да поставим най-много по 1 клетка(в противен случай ще се образува правоъгълник) т.е. най-много 4+1+1+1= 7 клетки:
Когато в стълба с най-много оцветени клетки има 3, то във всеки от останалите 3 стълба има не повече от 2 оцветени клетки(в противен случай 2 от тях ще образуват правоъгълник с някои 2 от първия стълб). Така има общо най-много 3+3.2 = 9 клетки:
Ако в стълба с най-много оцветени клетки има не повече от 2 - общият брой на оцветените клетки не надминава 4.2 = 8:
Колко е най-големият брой оцветени клетки в дъска 7х7 така,че няма правоъгълник образуван от центровете на четири клетки и страни успоредни на тези на дъската?
При дъска 7х7 можем да видим, че броят на двойките редове е (7.6)/2 = 21. Това означава, че ако двойките оцветени клетки в стълбовете е повече от 22, то със сигурност 2 от тях ще съвпаднат по редове и ще се образува правоъгълник:
Колкото повече клетки оцветяваме в някой стълб, толкова по-малко възможни двойки остават. Например ако оцветим 5 клетки, то броят на заетите двойки вече е (5.4)/2 = 10 и ни остават още 11 "свободни".
Две клетки образуват 1 двойка, три клетки - 3 двойки, четири клетки - 6 двойки, пет клетки - 10 двойки и т.н. Можем да видим, че най-голям брой клетки, които можем да оцветим се получава когато броят на клетките в никои два стълба не се различава с повече от 1 - в противен случай при преместване на 1 клетка от колоната с повече клетки в тази с по-малко ще намали броят на заетите двойки. Тогава най-голям брой оцветени клетки се получава ако във всеки стълб са оцветени по 3 клетки:
Действително, нека дъската е с размери m x m, максималният брой оцветени квадратчета е К и във всеки стълб има по х1,х2,...,xm оцветени квадратчета. Тогава сумата от двойките по стълбове не може да надвишава общия брой двойки редове:
От друга страна използвайки неравенството на Коши-Буняковски-Шварц можем да намалим още повече сумата от квадратите в (1):
Така получаваме квадратно неравенство спрямо К:
Оттук получаваме:
Тогава най-голямата възможна стойност за броят на оцветените квадратчета К без хоризонтален правоъгълник е:
Тогава като заместим, при m=7 дейнствително се получава, че броят на оцветените квадратчета не надвишава 21. Също така неравенството на Коши-Буняковски-Шварц се превръща в равенство когато х1=х2=...=xm, което потвърждава, че търсим пример, при който квадратчетата са оцветени по стълбовете възможно най-поравно.
Този тип задачи са частен случай на задачата на Заранкевич за забранения подграф. Можете да видите, че при търсенето на граф с най-много ребра без К2,2 се достига до същата оценка. Защо?
За да изследвате, можете да го направите в обучителната тема "Покриващи правоъгълници част 2" в Покрития на дъска:
Copyright: Mladen Valkov