Покриващи оцветявания - не повече от \(5\) оцветени в квадрат \(3 \times 3\)
Колко е най-големият брой клетки, които можем да оцветим в правоъгълна дъска, така че всеки квадрат \(3 \times 3\) да съдържа не повече от \(5\) оцветени клетки?
Темата е базирана на въпрос от Math Stack Exchange
Нека първо да разгледаме няколко примера за малки дъски.
Нека дъската е \(4 \times 5\).
Нека в два противоположни ъгъла на дъската на вземем \(2\) квадрата \(3 \times 3\). Фигурата образувана от тях има не повече от \(10\) оцветени квадратчета. В останалите \(2\) правоъгълника \(1 \times 2\) можем да оцветим най-много \(4\) квадратчета.
Фигурата образувана от тях има не повече от \(10\) оцветени квадратчета. В останалите \(2\) правоъгълника \(1 \times 2\) можем да оцветим най-много \(4\) квадратчета т.е. \(10+4=14\) е най-големият брой оцветени квадратчета за дъската \(4 \times 5\):
Нека дъската е \(5 \times 5\).
Отново в двата противоположни ъгъла на дъската взимаме два квадрата \(3 \times 3\) и фигурата в тях има не повече от \(10\) оцветени.
В останалите \(2\) квадрата \(2 \times 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)(3n+1)+(m+1)(2n+1)=(m+1)(5n+2)=5nm+5n+2m+2\).
Copyright: Mladen Valkov