Покриващ път - ход на коня
Нека е дадена следната дъска 4х4 и да изберем произволна клетка от нея. Ход на коня ще наричаме всяко преместване с 2 клетки в някоя посока и след това още 1 клетка в посока перпендикулярна на предишната:
Съществува ли покриващ път, с ход на коня, за дъската 4x4? (Покриващ път на дъската е такъв, който преминава през всяка клетка точно по веднъж).
Нека да направим следното оцветяване на дъската:
Забелязваме, че ако се намираме в черна клетка, то на следващия ход задължително ще бъдем на бяла клетка. Това означава, че можем да имаме оцветяване на пътя, което сменя черни и бели квадратчета алтернативно:
Ч Б Ч Б Ч Б Ч Б Ч Б Ч Б Ч Б Ч Б
или да има един ход, при който се отива от бяло в бяло квадратче - всички останали ходове сменят цвета алтернативно. Например:
Ч Б Ч Б Б Ч Б Ч Б Ч Б Ч Б Ч Б Ч
Нека да разположим шахматно сини точки в дъската:
На дъската има 4 черни клетки с точка, 4 черни клетки без точка, 4 бели клетки с точка и 4 бели клетки без точка. При всеки ход на коня сменяме от клетка с точка в клетка без точка (и обратното). Затова преминаването от Бяло - > Бяло поле трябва да стане точно по средата на пътя (в противен случай няма да имаме точно по 4 от посочените 4 вида):
Ч Б Ч Б Ч Б Ч Б Б Ч Б Ч Б Ч Б Ч
Нека да оцветим този път първата и последната колона от дъската:
Разсъждавайки аналогично - пътят трябва да е оцветен по същия начин Ч Б Ч Б Ч Б Ч Б Б Ч Б Ч Б Ч Б Ч. Така 8-та и 9-тата клетка и в двата пътя трябва да са бели. Това означава, че са някои 2 от 4-те клетки по средата:
Но никои две от тези клетки не са свързани с ход на коня - не е възможно за дъската да се намери път.
Нека да премахнем някои от клетките и да оставим дъска 3х4. Да оцветим в черно първата и последната колона:
Отново можем да съобразим, че 6-тата и 7-тата клетка от пътя ще бъдат бели - Ч Б Ч Б Ч Б Б Ч Б Ч Б Ч. Така получаваме пътя:
Кои са правоъгълните дъски, които нямат покриващ път с ход на коня?
Теоремата на Швенк казва, че всички дъски дъски освен:
- дъски с дължина на някоя от страните 1 или 2:
- дъски 3х3, 3х5 и 3х6:
- дъска 4х4:
имат покриващ път с ход на коня.
Кои дъски имат покриващ цикъл с ход на коня? ( Това е път, при който от последната клетка можем с ход на коня да се върнем в началната клетка.)
Ако дъската има нечетни размери и я оцветим шахматно, то на всеки ход се сменя цвета на текущата клетка:
Първата и последната клетка от пътя ще бъдат в един и същи цвят (броят на клетките е нечетен) т.е. няма как от последната клетка от пътя да се върнем в началната.
Ако дъската има дължина 4 на някоя от страните си, то вече видяхме, че ако оцветим първия и последния ред в черно, то първата и последната клетка от пътя ще бъдат черни:
а от черна клетка не можем да направим ход към друга черна клетка.
Също така можем да изключим и дъската 3х6 - тя няма покриващ път, следователно няма и покриващ цикъл.
Дъската 3х8 има покриващ път:
но няма покриващ цикъл. Бързо виждаме, че оранжевите и сините пътища показани на изображението, трябва да бъдат част от цикъла:
Това означава, че сивите пътища трябва да бъдат части от цикъла:
Оттук имаме 3 възможности - или четирите сиви точки са свързани помежду си - при което сивия път е самозатворен (не може да бъде част от покриващ цикъл):
или 4-те сиви точки са свързани с 4-те сиви - но така се образуват два цикъла от сини и сиви точки.
Остава третата възможност - 2 от сивите точки са свързани помежду си, а другите 2 със синя точка:
Оттук две от оранжевите точки могат да бъдат свързани само с двете централни клетки на дъската:
Така другите две оранжеви клетки, трябва да бъдат свързани с две от сините, а двете клетки по средата не са свързани с ход на коня:
което ни дава покриващ път, но не и цикъл.
Използвайки подобни разсъждения можем да намерим покриващ цикъл за дъска 3х10:
Алън Швенк доказва, че дъските, които имат покриващ цикъл са всички дъски без тези:
- със страна по-малка от 3;
- с две нечетни страни;
- с някоя от страните 4;
- дъски 3х6,3х8;
Намерете покриващ цикъл с ход на коня за дъска 5х6.
Дадения път до момента покрива половината от дъската, като двете вериткални половини от дъската са антисиметрични - на белите отговарят черни, а на черните -бели:
За да изследвате, в темата за Покрития на дъска изберете Покриващ път, от падащото меню вляво - Ход на коня и направете път по дъската:
За да преминете през обучителните стъпки изберете:
Copyright: Mladen Valkov