Покрития на дъска - Г-тримино
Когато плочка е съставена от три квадратчета образуващи фигура с формата на буквата Г, тя се нарича Г-Тримино:
Възможно ли е да покрием дъска 3х3 с плочки от този вид (без да се застъпват или излизат от дъската)?
Ще са ни нужни 9 : 3 = 3 плочки. Нека да разгледаме следното оцветяване на дъската:
Забелязваме, че всяка плочка покрива или 1 или 0 оцветени квадратчета. Тогава трите плочки заедно няма как да покрият и 4-те оцветени квадратчета - дъската не може да се покрие.
Нека да премахнем показаното квадратче от дъска 5х5. Може ли оставащата дъска 5х5 да се покрие с плочки Г-Тримино?
Отново да направим оцветяване през ред и колона. Броят на квадратчетата, които трябва да покрием е 5.5-1 = 24 т.е. ни трябват 24 : 3 = 8 плочки, с които няма как да покрием 9 оцветени квадратчета:
Можем да забележим, че което и от белите квадратчета да премахнем от дъската 5х5 оставащата дъска не може да се покрие с плочки Г-Тримино.
Вярно ли е, че ако премахнем кое да е от черните квадратчета, оставащата дъска може да се покрие с плочки Г-Тримино?
В случай, че премахнем ъглово квадратче от дъската 5х5 оцветените квадратчета остават 8:
Така ако всяка плочка покрива точно по едно оцветено квадратче, можем да покрием дъската с плочки Г-Тримино:
Опитайте сами да намерите покрития на следните дъски (което ще означава, че което и от деветте черни квадратчета да премахнем оставащата дъска може да се покрие):
Маршал Аш и Соломон Голомб доказват, че ако е дадена дъска m x n, такава че m и n са по-големи от 1, различни от 2 и 5 и m.n-1 се дели на 3, то което и квадратче да премахнем от дъската, оставащата дъска може да се покрие с плочки Г-Тримино.
Нека m x n е дъска, за която m.n се дели на 3. Тогава дъската може да се покрие с Г-Тримино винаги освен, ако едно от двете е равно на 3, а другото е нечетно.
- Нека дъската е от вида 3х(2k+1). Тогава след като направим горепосоченото оцветяване, ще имаме 2(k+1) оцветени квадратчета и 2k+1 плочки, които трябва да поставим. Всяка плочка покрива не повече от 1 оцветено т.е. ще можем да покрием най-много 2k+1 оцветени квадратчета - дъската не може да се покрие изцяло.
- Нека дъската има една страна, която се дели на 3, а другата е четно число. Тогава дъската може да се раздели на правоъгълници 2х3. Например, ако дъската е 2x15, то може да я разбием на 5 правоъгълника 2x3.
- Нека е дадена произволна дъска (2k+1) x (3s), където 2k+1 е поне 5, а 3.s е поне 6. Ако 3.s е четно, то можем да отделим една ивица 3х(3s) и няколко ивици 2х(3s) всяка от които може да се раздели на правоъгълници 2х3:
Ако (3s) е нечетно число, то от целия правоъгълник отделяме ивица 5х(3s), която можем да разделим на правоъгълник 5х9 и няколко правоъгълника 5х6. Всяка от получените части може да се покрие с Г-Тримино:
Едно квадратче от дъска 5 х (3k+2) ще наричаме интересно, ако след премахването му останалата дъска НЕ може да се покрие с плочки Г-Тримино. Колко са интересните квадратчета върху дъската?
По-горе вече видяхме, че върху дъска 5х5 има 9 квадратчета, след премахването на всяко от които останалата част от дъската може да се покрие с Г-Тримино.
Нека дъската е от вида 5 х (6k+2). Да разгледаме дъска 5х8. Можем да видим, че след премахването на всяко от двете квадратчета останалата дъска не може да се покрие с Г-Тримино.
Забележете, че ако премахнатото квадратче е в някой от двата квадрата 2х2, които са показани по-долу, то останалата част от дъската може да се покрие с Г-Тримино.
Тогава от съображение за симетрия, можем да кажем, че никое квадратче от горните два реда и долните два реда не е интересно.
Към тях можем да добавим първото, третото и четвъртото квадратче (а значи и петото, шестото и осмото) като квадратчета след премахването, на които получаваме дъска, която може да се покрие с Г-Тримино:
Разглеждайки дъска 5х(6k+2), за която знаем че дъска 5х(6k-4) може да бъде покрита има само четири възможни интересни квадратчета (на примера имаме дъска 5х20 и има 2 интересни квадратчета във всяка от двете дъски 5х14 в левия и десния край на дъската):
Двете квадратчета от 4-те, които са във вътрешността на дъската не са интересни за единия от двата правоъгълника 5х(6к-4):
Така интересни квадратчета за дъската 5х(6k+2) остават само това във втория и предпоследния стълб:
В някои задачи се изследва въпрос свързан с броя на покритията на дъска с Г-Тримино.
Каква е четността на броя на покритията на дъска 6 х 100 с Г-Тримино?
Можем да забележим, че всяко покритие на дъската, което НЕ е симетрично спрямо и хоризонталната и вертикалната права, която разполовява дъската, то за него можем да намерим или 2, или 4 различни покрития.
Тогава четността на покритията се определя от броя на покритията на всяка от 4-те дъски 3х50, които се образуват при разделянето на дъската от 2-те оси на симетрия. Единствените покрития се състоят от 25 правоъгълника 2х3 разположени вертикално, като за всеки от тях има по 2 възможности т.е. общия брой им е 2 на степен 50 - четен брой.
Каква е четността на броя на покритията на дъска 6 х 1000 с Г-Тримино след като са изключени 2-ро,3-то и 4-то квадратче в първата колона? (Н.Белухов, контролни БОМ, България, 2011)
Можем да забележим, че ако при някое покритие се срещне правоъгълник 2х3, то то има едниствено съответно покритие, при което правоъгълникът 2х3 е симетричен.
Има само два случая да започнем да покриваме дъската в долния ляв ъгъл, без веднага след това да следва правоъгълник 2х3.
В случай 1) можем да видим, че следните стъпки са задължителни (без да имаме правоъгълник 2х3):
От него достигаме до две възможности. а) 6х994 (която няма симетрични покрития спрямо хоризонталната и вертикалната ос на симетрия на дъската, тъй като дъска 3х497 не може да се покрие с Г-Тримино) - тук броят на покритията е четен, тъй като покритията могат да се разбият на двойки симетрични; б) до същата задача само, че с дъска 6х996 с 3 премахнати квадратчета:
Така продължавайки по начин 1б) стигаме до едно единствено покритие, което няма симетричн покритие:
Започвайки по начин 2) стигаме до дъска 6х996, за която броят на покритията е четен.
Взимайки покритията от двата случая получаваме, че общият брой на покритията е нечетен.
Свойствата на това оцветяване се запазват, когато преминем към тримерни дъски.
Може ли куб 3х3х3 да се покрие с плочки Г-Тримино?
В куба 3х3х3 да оцветим 8-те кубчета по върховете, както и кубчето във вътрешността на големия куб - 9 е най-големият брой оцветени кубчета, при който всяка плочка тримино покрива най-много по 1 оцветено кубче:
Броят на плочките, които ни трябват е 27 : 3 = 9. Тогава можем да видим, че тримерната дъска може да се покрие:
(Артур Бефумо и Джонатан Ленхнер) Тук може да се види, че ако премахнем, което и да е кубче от тримерна дъска m x n x k, за която m.n.k-1 се дели на 3 и m,n,k > 1, то оставащата дъска може да се покрие с Г-Тримино.
Да изследваме горното за дъска 2х4х5.
Дясното покритие на дъска 4х10 може да се преобразува в покритие на дъската 2х4х5. Покриваме първо десния слой на дъската 2х4х5, след това поставяме преходното Г-Тримино между двата слоя и довършваме левия слой. (Каквито са и трите части на покритието на дъската 4х10 с липсващо квадратче).
За да изследвате, можете да го направите в обучителната тема "Покритие с домино" в Покрития на дъска:
Copyright: Mladen Valkov