Покриващи оцветявания - най-много един съсед по страна
Колко е най-големият брой клетки, които можем да оцветим в правоъгълна дъска, така че всяка оцветена клетка да има най-много един оцветен съсед по страна?
Нека страните на дъската са с четна големина.
Да разгледаме дъска \(4 \times 4\):
Всяка дъска с четни размери може да се раздели на квадрати \(2 \times 2\), във всеки от които можем да оцветим най-много \(2\) квадратчета (в противен случай някоя от клетките ще има \(2\) черни съседа). От друга страна, шахматното оцветяване дава този максимален брой от \(2\) оцветени квадратчета, във всеки от квадратите \(2 \times 2\):
Тогава в дъска с размери \((2m) \times (2n)\), максималният брой оцветени квадратчета, които изпълняват условието е \(2mn\).
Нека една от страните на дъската е с четна, а другата с нечетна големина.
Нека да разгледаме дъска 11х12:
Можем да отделим последния ред и да го разделим на правоъгълници 1х3. В дъската 10х12 от предишната задача знаем, че можем да оцветим най-много половината от квадратчетата. Във всеки от правоъгълниците 1х3, можем да оцветим най-много по 2 квадратчета (в противен случай едно от оцветените квадратчета ще има 2 черни съседа). Така можем да получим максималния брой оцветени квадратчета. В дъска (3.m+s) x (2.k+1), където s=0,1,2 и 3.k+s е четно, броят на квадратчетата ще е (3.m+s).k + 2.m + s.
Нека и двете страни на дъската са с нечетна големина.
За дъска с нечетни размери да започнем от дъска 3х3. Разделяме я на две правоъгълни дъски 2х3 и 1х3, които общо не могат да имат повече от 4+2 = 6 оцветени клетки. Единствения начин да оцветим 4 клетки в дъската 2х3 е показан, а при него в правоъгълника 1х3 може да има само една оцветена клетка. Тогава броят на оцветените клетки не надвишава 5:
При дъска 3x(3.k+1) максималния брой оцветени клетки е 5.k+2 и също така 4-те клетки в ъглите са оцветени. Наистина при дъска 3х7:
в правоъгълникът 2х3 и при двете разделяния трябва да има по 4 оцветени клетки, за които има само един възможен вариант – 2-те горни клетки и 2-те долни клетки. Така и 4-те ъглови клетки винаги са оцветени.
Ако дъската е 3х(3.k+2), то максималния брой оцветени клетки е 5.k+4, като трябва и 4-те ъглови клетки да бъдат оцветени. При дъска 3x11:
Ако дъската е 3х(3.k), то максималния брой оцветени е 5.k, като има пример, при който 2 от ъгловите клетки не са оцветени.
Друго наблюдение е, че ако вземем три последователни ивици с ширина 2, във всеки от трите почти-квадрата 3х3( с липсваща ъглова клетка) има не повече от 5 оцветени, както и в квадратите 2х2 има не повече от 2 оцветени.
С непосредствено изследване можем да видим, че два съседни почти-квадрата не могат да имат едновременно 5 оцветени квадратчета. Още повече – ако всички квадрати 2х2 имат по 2 оцветени, то най-много един от трите почти-квадрата има 5 оцветени (другите два имат по 4 оцветени).
За произволна дъска с нечетни размери можем да построяваме почти квадрати от долния ляв ъгъл докато не достигнем до дъска 3 x n. Нека да направим следното оцветяване - до по-малката от двете страни през ред оцветяваме двойки клетки във формата на домино. В 3-тия стълб оцветяваме клетки през ред, така че никоя от тях не се допира до двойките клетки. След това отново оцветяваме двойки клетки във формата на домино в 4-тия и 5-тия ред и т.н. Така във всеки квадрат 2х2 има максимален брой клетки и се достига максималният брой оцветени клетки в почти квадратите:
Важно е да се отбележи, че когато броят на почти квадратите дава остатък 1 при деление на 3 и получената дъска 3 х n е от вида 3 x (3.k+1) или 3 x (3.k+2) не е възможно едновременно да се достигне до максималния брой почти-квадрати с 5 оцветени квадратчета и едновременно с това максималния брой оцветени квадратчета в дъската 3 x n:
Това е така понеже (вижте по-горе) в случаите за дъски 3 x (3.k+1) или 3 x (3.k+2) видяхме, че и 4-те ъглови квадратчета трябва да са оцветени, за да се достигне максималния брой оцветени квадратчета в тях т.е. максимален брой оцветени квадратчета(5) ще им или почти квадратът долепен до дъската 3 x n, или дъската 3 x n. И в двата случая, общият брой оцветени квадратчета не се променя.
Изследвайте сами различни дъски с нечетни размери (можете да го направите в обучителната тема "Покриващи оцветявания - един оцветен съсед" в Покрития на дъска):
Copyright: Mladen Valkov