Покриващи оцветявания - не повече от 5 оцветени в квадрат 3х3
Колко е най-големият брой клетки, които можем да оцветим в правоъгълна дъска така, че всеки квадрат 3х3 да съдържа не повече от 5 оцветени клетки?
Темата е базирана на въпрос от Math Stack Exchange
Нека първо да разгледаме няколко примера за малки дъски.
Нека дъската е 4х5.
Нека в два противоположни ъгъла на дъската на вземем 2 квадрата 3х3. Фигурата образувана от тях има не повече от 10 оцветени квадратчета. В останалите 2 правоъгълника 1х2 можем да оцветим най-много 4 квадратчета.
Фигурата образувана от тях има не повече от 10 оцветени квадратчета. В останалите 2 правоъгълника 1х2 можем да оцветим най-много 4 квадратчета т.е. 10+4=14 е най-големият брой оцветени квадратчета за дъската 4х5:
Нека дъската е 5х5.
Отново в двата противоположни ъгъла на дъската взимаме два квадрата 3х3 и фигурата в тях има не повече от 10 оцветени.
В останалите 2 квадрата 2х2 има общо не повече от 8 оцветени квадратчета. Така получаваме, че най-големият брой оцветени квадратчета тук е 18. Намерете пример, който изпълнява условието сами.
Изследвайте в СтруниМа и други дъски - напр. 4х4, 4х7, 3х8. Можем да забележим, че "максималното" оцветяване зависи от остатъкa при деление на 3 на размерите на дъската. Ще разгледаме следните случаи:
Нека дъската е от вида (3.n)x(3.m).
За пример ще използваме дъска 6х9. Нека да я разделим на 6 квадрата 3х3, като във всеки има не повече от 5 оцветени т.е. общия им брой не надвишава 6.5=30.
Достигат се със следното оцветяване (забележете, че във всеки квадрат 3х3 има не повече от 5 оцветени):
Аналогично, дъската (3.n)x(3.m) може да се раздели на n.m квадрата 3х3 т.е. броят на оцветените квадратчета не надвишава n.m.5, като този брой се достига с горното оцветяване.
Нека дъската е от вида (3.n)x(3.m+1).
За пример ще използваме дъска 6х10. Нека да я разделим на 6 квадрата 3х3, като остане една колона. Общият брой на оцветените не надвишава 6.5+6=36.
Достигат се със следното оцветяване, като последната колона е изцяло оцветена:
Аналогично, дъската (3.n)x(3.m+1) може да се раздели на n.m квадрата 3х3 и един стълб от n квадратчета т.е. броят на оцветените квадратчета не надвишава 5.n.m+3.n, като този брой се достига с горното оцветяване.
Нека дъската е от вида (3.n)x(3.m+2).
За пример ще използваме дъска 6х11. Нека да я разделим на 6 квадрата 3х3 и 2 правоъгълника 2х3. Общият брой на оцветените не надвишава 6.5+2.5=40, тъй като в правоъгълниците 2х3 има не повече от 5 оцветени квадратчета(като части от квадрати 3х3).
Аналогично, дъската (3.n)x(3.m+2) може да се раздели на n.m квадрата 3х3 и n правоъгълника 2х3 т.е. броят на оцветените квадратчета не надвишава 5.n.m+5.n, като този брой се достига с горното оцветяване.
Нека дъската е от вида (3.n+1)x(3.m+1).
За пример ще използваме дъска 7x10. Нека да я разделим на 6 квадрата 3х3 и ивица съставена от последния ред и стълб. Тогава общият брой на оцветените не надвишава 6.5+(7+10-1)=46, тъй като цялата ивица може да е оцветена(като части от квадрати 3х3).
За дъска (3.n+1)x(3.m+1) може да се раздели на n.m квадрата 3х3 и ивица от m+n-1 квадратчета т.е. броят на оцветените квадратчета не надвишава 5.n.m+3.m+3.n+1, като този брой се достига с горното оцветяване.
Нека дъската е от вида (3.n+2)x(3.m+2).
За пример ще използваме дъска 8x11. Започваме от долния десен ъгъл на дъската и отделяме фигура съставена от 2 правоъгълника 2х3. Над нея долепена построяваме същата фигура и продължаваме докато е възможно. Останалата дъска се разделя на квадрати 3х3, правоъгълници 2х3 и един квадрат 2х2.
Забележете, че фигурите съставени от два правоъгълника 2х3 имат най-много по 9 оцветени - всеки правоъгълник 2х3 има не повече от 5 оцветени, но ако и двата имат едновременно по 5 оцветени, то ще съществува квадрат 3х3 с 6 оцветени.
Със следното оцветяване се достига максималния брой оцветени квадратчета във всяка от получените части.
Нека дъската е от вида (3.n+1)x(3.m+2).
Нека 3.n+1<3.m+2. За пример ще използваме дъска 10х14.
Започваме от долния десен ъгъл на дъската и отделяме фигура съставена от правоъгълник 2х3 и правоъгълник 1х3. Над нея долепена построяваме същата фигура и продължаваме докато е възможно. Останалата дъска се разделя на квадрати 3х3 и една ивица 1х5.
Фигурите съставени от правоъгълник 2х3 и правоъгълник 1х3 имат най-много по 7 оцветени.
Със следното оцветяване се достига максималния брой оцветени квадратчета във всяка от получените части - 4.14+3.10=86.
В общия случай, това оцветяване ни дава максималният брой оцветени квадратчета - (n+1).(3.m+2)+n.(2.m+2)=5.m.n+4.n+3.m+2.
Нека 3.n+1>3.m+2. За пример ще използваме дъска 13х8.
Отново започвайки от долния десен ъгъл поставяме фигури съставени от правоъгълник 2х3 и правоъгълник 1х3 докато е възможно. Останалата дъска се разделя на квадрати 3х3, правоъгълници 2х3 и един правоъгълник 1х2.
Със следното оцветяване се достига максималния брой оцветени квадратчета във всяка от получените части - 3.13+3.9=66.
В общия случай, това оцветяване ни дава максималният брой оцветени квадратчета - (m+1).(3.n+1)+(m+1).(2.n+1)=(m+1)(5.n+2)=5.n.m+5.n+2.m+2.
Copyright: Mladen Valkov