Cтраница 2
Всяка от описаните игри поставя и една стандартна задача - да се съста-ви алгоритъм за подреждането и. [16]
Понеже това е една от най-трудните главоблъсканици, разглеждани засега в книгата, ще опишем по-подробно алгоритъма за подреждането. Той се състои от пет етапа. [17]
Тази игра принциптю не се различава от играта 75, но благодарение на една незабележима на пръв поглед особеност подреждането на пулчетата е възможно при произвол-но начално разбъркване. В този смисъл пулчетата с цифрите 6 и 9 са еднакви и точно това прави задачата винаги решима. Сле-дователно, ако Лойд беше предложил 1000 долара за такава форма на своя-та задача, то някой сигурно би се се-тил да завърти наопаки 6 и 9, когато се налага. [18]
И върху игрално-то поле със свободна клетка 5 ( те са точно 8.7.6 336), а след това за все-ки един от тези 336 случаи търсим най-кратката формула, която извър-шва подреждането. [19]
За този етап не са необходими спе-циални формули, защото с малко съ-образителност всеки може да го из-пълни. При подреждането се стремим да запазим ориентацията на централ-ните квадратчета. По този начин по-строяваме бял кръст, като странич-ните четири стени на ръбните кубчета съвпадат по цвят с централните квадратчета на четирите околни стени. [20]
Подреждането на кулата до петия стаж не представлява трудност. За подреждането на шестия стаж е доста-тъчно да се убедим, че движението на петия и шестия етаж с прехвърляне на едно топче от единия в другия всъщност не се различава от играта две шесторки от фиг. [21]
А сега да разгледаме варианта на играта 75, в който вместо числа върху пулчетата са написани последовател-но буквите на думата главобльсканица, като до последното А е поставена точка ( фиг. При подреждането на пулчетата обикновено лесно се стига или до пълното решение, или до раз-положение, при което двете последни букви ( Ц и А. Ако се случи второто, задачата е да се намери редица от ходове, с която А. Например можем да разместим останалите две букви А ( в първия и третия ред) или пък двете Л - та. По-долу предла-гаме едно решение с 32 хода. Читате-лят може сам да потърси други решения дори с по-малък брой хрдове. В записа на решението там, където мо-гат да се преместят две пулчета с ед-накви букви, със стрелка сме посочили посоката на движение на пулчето, кое-то е на ход. [22]
Очевидно описаният процес за тър-сене на най-добрия алгоритъм в по-следна сметка ще даде резултат, но на практика той може да се осыцестви само от електронно-сметачна машина, така че ползата от подобен алгоритъм е само теоретична. Въпреки че по него подреждането се извършва с минимален брой стъпки, сложността му се увеличава от огромния брой случаи. [23]
К и К2, ще забележим, че те реализират четни пермутации, а понеже в алгоритъма те се използуват след спрягане, то и техните спрегнати ще реализират четни пермутации. То-ва показва, че ако за подреждането на пулчетата след етап 1 е необходимо да се изпълни четна пермутация, фор-мулите RI и К2 са достатъчни, но ако трябва да се изпълни нечетна пермутация, накрая задължително ще прибегнем до формулата С. Следовател-но, за да елиминираме С, трябва така да преработим етап 1, че за следва-щия етап да останат само четни пермутации. След това пресмя-таме четността на получената пермутация: ако тя е четна, продължаваме по стария начин ( етап 2) само с фор-мулите К и К2, понеже тогава няма да се наложи да използуваме С ако пък пермутацията е нечетна, изпълня-ваме В. Тъй като подредените пулчета са извън зоната на цикъл 5, той не разваля нищо от постигнатото до момента. Какво се получава след негово-то изпълнение. Понеже В е цикъл с дължина 6, той е нечетна пермутация, следователно резултатът е произведение на две нечетки пермутации, което вече е четна пермутация и затова можем да продължим отново с форму-лите К и К2, конто осигуряват подреждането. [24]
Тогава тя е около върха В и с една от шеспе формули на фиг. Така свеждаме случая към предишния и завършва-ме подреждането за не повече oi 12 4 7 23 хода. [25]
Последната играчка от типа на миникуба, която ще опишем, е звездата ( фиг. Тя представлява два впле-тени един в друг тетраедъра и по отношение на подреждането и се свежда към тетраедъра - всъщност звездата се получава от тетраедъра, като прилепим към всяка от стените му по ед-на малка правилна пирамидка. [26]
Но ние току-що по-казахме, че такава формула не съществува. Това показва, че формулите К и К2 са достатъчни за довършване на подреждането в този етап. [27]
Нека споменем, че във II гл. G ( A B) - там преброихме конфигурациите, при конто е възможно подреждането. Ако идеята, из-ползувана там, се даде в алгебрична форма, ще видим, че групата на играта 10 триъгълника може да се разглежда като подгрупа на друга импримитивна трупа, чиито класове на импримитив-ност съдържат по 6 елемента. [28]
Както виждаме, нетри-виалните игри се дават от случая 3, в който се получава алтернативната или симетричната трупа върху множеството X. Ако групата е алтерна-тивна, играта се подрежда само ако пермутацията а, която трябва да осъ-ществим за подреждането, е четна. Построяването на а може да се извър-ши, като проследим доказателството на теоремата. Ако пък групата е си-метрична, подреждането е винаги въз-можно. При това, ако пермутацията а, която трябва да реализираме, е четна, постъпваме както в предния случай, а ако е нечетна, използуваме онзи цикъл А който е нечетна пермутация. Тогава по лема 3 на стр. [29]
Читателях трябва да пристъпи към тази глава чак след като е разучил главоблъсканиците в предишната глава и се е опитал самостоятелно да ги реши. При това под решение се разби-ра не случайното подреждане на даде-на главоблъсканица, а намирането на система от указания, конто осигуря-ваг подреждането и независимо от на-чалното положение на главоблъскани-цата. [30]