Покриващи оцветявания - поне 3 неоцветени съседа
Колко е най-големият брой клетки, които можем да оцветим в правоъгълна дъска така, че всяка оцветена клетка да има поне 3 неоцветени съседни клетки?
Дъските 1xn не могат да имат оцветяване, което да изпълнява условието - всяка клетка има не повече от 2 съседа.
Нека единия от размерите на дъската е 2 (т.е. е от вида 2 х n).
Нека дъската е от вида 2 x n. За пример ще използваме дъска 2 х 7. Разделяме цялата дъска на вертикални доминота(правоъгълници 1х2):
В двете крайни доминота не можем да имаме оцветени квадратчета - в която и да е дъска ъгловите квадратчета не могат да са оцветени. Във всяко от останалите имаме не повече от 1 оцветено - можем да ги оцветим шахматно. Тогава броят на оцветените квадратчета в дъска 2 х 7 не надвишава 7 - 2 = 5. В дъска 2 x n аналогично получаваме, че този брой е n - 2.
Нека единия от размерите на дъската е 4 (т.е. е от вида 4 х n).
Нека дъската е от вида 4 x n. За пример ще използваме дъска 4х8. Ъгловите квадратчета не могат да са оцветени. Останалата част на дъската я разделяме на доминота(правоъгълници 1х2) по следния начин:
Всяко от доминотата има не повече от 1 оцветено квадратче. Можем да ги оцветим шахматно, както е показано т.е. тук най-големият брой оцветени квадратчета е (4.n-4):2=2.n-2, в частност 14 оцветени за дъска 4х8.
Нека дъската е с два нечетни размера - (2.n+1) x (2.m+1).
Разделяме дъската на n x m квадрата 2 х 2, n + m правоъгълника 1x2 и едно ъглово квадратче. В примера 5х7 това са 2.3 = 6 квадрата 2х2, 2+3=5 правоъгълника 1х2 и ъгловото квадратче:
Всеки квадрат 2х2 съдържа не повече от 2 оцветени квадратчета (вижте сами защо), всяко от доминотата по краищата има не повече от 1, а ъгловото квадратче 1х1 не е оцветено със сигурност. Виждаме, че показаното шахматно оцветяване ни дава максималния брой оцветени във всяка от частите - 2.m.n+m+n. В частност на дъската 5х7 това е 2.2.3+2+3=17.
Нека дъската е с два четни размера по-големи от 4 - (2.n) x (2.m), като 2.n>4 и 2.m>4.
Разделяме дъската между първия и последния стълб на квадрати 2х2. Първия и последния стълб ги разделяме на доминота 1х2, като изключваме ъгловите клетки. Следното почти-шахматно оцветяване ни дава максималният брой оцветени квадратчета във всяка от получените части:
Тук най-големият брой оцветени клетки е 2.n.m - 2. В частност на дъската 6х8 това е 2.3.4 - 2 = 22.
Нека дъската е с един четен размер по-голям от 4 и един нечетен размер - (2.n) x (2.m+1), като 2.n>4.
За пример ще използваме дъска 8х11. Разделяме дъската на n.m квадрата 2х2 и последния стълб на доминота 1х2 (без двете ъглови квадратчета, тъй като те не могат да са оцветени).
За да постигнем максималният брой оцветени във всяка от частите оцветяваме шахматно всяка от частите с изключение на един ред от квадрати 2х2 в които двете оцветени образуват вертикален правоъгълник 1х2 (с оранжевите звезди).В този случай максималният брой оцветени са 2.m.n+n-1 или в частност, за дъската 8х11 това е 2.4.5+4-1=23.
Сами изследвайте различни дъски с един четен и един нечетен размер, например 3х8 (състезание Акад. Кирил Попов 2019, 4 клас), 6х11, 9х6. Можете да го направите в изследователската част на темата за "Покрития на дъска" или в обучителната тема "Покриващи оцветявания - три неоцветени съседа":
Copyright: Mladen Valkov