Покриващи оцветявания - най-много един съсед по страна
Колко е най-големият брой клетки, които можем да оцветим в правоъгълна дъска така, че всяка оцветена клетка да има най-много един оцветен съсед по страна?
Нека страните на дъската са с четна големина.
Да разгледаме дъска 4х4:
Всяка дъска с четни размери може да се раздели на квадрати 2х2, във всеки от които можем да оцветим най-много 2 квадратчета (в противен случай някоя от клетките ще има 2 черни съседа). От друга страна, шахматното оцветяване дава този максимален брой от 2 оцветени квадратчета, във всеки от квадратите 2х2:
Тогава в дъска с размери (2.m) x (2.n), максималният брой оцветени квадратчета, които изпълняват условието е 2.m.n.
Нека една от страните на дъската е с четна, а другата с нечетна големина.
Нека да разгледаме дъска 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