Cтраница 3
Не трябва да се очаква, че пулчетата винаги ще могат да се подредят. Под решение на за-дачата ще разбираме намиране на метод за разпознаване, дали пулчета-та могат да се подредят, или не, и алго-ритъм, който в първия случай да осъ-ществява подреждането. [31]
Ако сменим ключовата дума в играта търпение с някаква друга, в която има две повтарящи се букви, конто обаче са на други места, или пък ако сменим местата на клетката, която остава свободна в края на играта, ще получим нови главоблъсканици, чиито решения са близки до подреждането на търпение. [32]
Използуваме формули-те Ki A - 2B - lABA и обратната и К2 А-1 В-1 А - ВА2, чиито графики са показани на фиг. Начинът по който подреждаме останалите лунички с тези формули, е описан на стр. Там беше спомена-то, че в края на подреждането е въз-можно луничките 7 и 8 да бъдат раз-менени и за този случай там се пред-лагаше формулата С А - ( ВА-2 В-1 А) 5А, която запазва всичко друго, като размества само тях. Cera обаче тази формула не върши работа, защо-то освен че размества луничките 7 и 8, тя развал я ориентацията на левия централен шестоъгълник. От факта, че групата на играта се съдържа в А - следва, че не съществува формула, която да размества само две лунички и значи е безсмислено да я тьрсим. Ще покажем, че в края на етап 4 е невъз-можно луничките 7 и 8 да се окажат разменени. [33]
Номерацията на клетките на играта е дадена на фиг. За улесне-ние при подреждането на пулчетата с номера 2, 3, 4, 7, 8 и 9 от втория цикъл сме поставили по една точка във върха, който е в центъра на цикъла. [34]
Както виждаме, нетри-виалните игри се дават от случая 3, в който се получава алтернативната или симетричната трупа върху множеството X. Ако групата е алтерна-тивна, играта се подрежда само ако пермутацията а, която трябва да осъ-ществим за подреждането, е четна. Построяването на а може да се извър-ши, като проследим доказателството на теоремата. Ако пък групата е си-метрична, подреждането е винаги въз-можно. При това, ако пермутацията а, която трябва да реализираме, е четна, постъпваме както в предния случай, а ако е нечетна, използуваме онзи цикъл А който е нечетна пермутация. Тогава по лема 3 на стр. [35]
Понякога пък вместо числа се използуват букви, конто обра-зуват смислена фраза. Тогава обаче, ако главоблъсканицата съдържа поне две повтарящи се букви, както и да поставим плочките в кутийката, само с допустими размествания винаги можем да подредим фразата. Такава е например думата главоблъсканица. За да намалим броя на повтарящите се букви, до последното А можем да поставим точка ( фиг. При тази главоблъсканица, както и при играта / 5 лесно подреждаме думата или до же-ланото крайне положение, или до по-ложението на фиг, 4, при което оста-ва още да се разместят последното А. За разлика от задачата на Лойд обаче наличието на повтарящи се букви прави възможно и в този случай подреждането на плочките. За колко хода може да се направи то. Едно решение от 32 хода е посочено в следващата глава. Можете ли да намерите алгоритъм, по който да се справяте с предложената главоблъсканица. [36]
Основна задача на таз и книга е чрез игрите да стимулира заниманията с математика. Типична пермутационна игра е кубът на Рубик, а за прототип на всички такива игри се смята играта / 5 на Сам Лойд. Пермутационните игри притежават под-вижни елементи, конто могат да се разместват по определени правила. Това по-зволява да разглеждаме играчката като система, която се намира в различии състояния, а едно или няколко от тях се обявяват за крайни или заключителни. Задачата е при произволно начално състояние чрез последователно прилагане на допустимите от правилата действия играчката да се приведе в някое от заключи-телните състояния. Тъй като и при най-простите пермутационни игри броят на различните състояния обикновено е огромен, шансовете да се достигне до заклю-чително състояние само с хаотични ходове практически са равни на нула. Така възниква проблемът за търсене на някаква насочена последователност от ходове за подреждане, на някаква система от указания, спазването на конто да прави възможно подреждането на играчката от произволно нейно изходно състояние. Такива системи от указания се наричат алгоритми, а търсенето на алгоритми и тяхното обосноваване е чисто математическа дейност. [37]
К и К2, ще забележим, че те реализират четни пермутации, а понеже в алгоритъма те се използуват след спрягане, то и техните спрегнати ще реализират четни пермутации. То-ва показва, че ако за подреждането на пулчетата след етап 1 е необходимо да се изпълни четна пермутация, фор-мулите RI и К2 са достатъчни, но ако трябва да се изпълни нечетна пермутация, накрая задължително ще прибегнем до формулата С. Следовател-но, за да елиминираме С, трябва така да преработим етап 1, че за следва-щия етап да останат само четни пермутации. След това пресмя-таме четността на получената пермутация: ако тя е четна, продължаваме по стария начин ( етап 2) само с фор-мулите К и К2, понеже тогава няма да се наложи да използуваме С ако пък пермутацията е нечетна, изпълня-ваме В. Тъй като подредените пулчета са извън зоната на цикъл 5, той не разваля нищо от постигнатото до момента. Какво се получава след негово-то изпълнение. Понеже В е цикъл с дължина 6, той е нечетна пермутация, следователно резултатът е произведение на две нечетки пермутации, което вече е четна пермутация и затова можем да продължим отново с форму-лите К и К2, конто осигуряват подреждането. [38]
Няма да даваме точно определение на понятието алгоритъм за подреж-дане на пермутационна игра. Ще припомним само, че алгоритъмът тряб-йа да съдържа система от ефективно изпълними указания, строгото следва-не на конто винаги да ни довежда до подреждане на играта. При това ука-занията не трябва да изискват в про-цеса на изпълнението някаква досет-ливост или творчество. Накратко ка-зано, указанията трябва да са така формулирани, че да се изпълняват автоматично, без допълнителни разсъ-ждения. Например дори описание-то на лесната част на нашия алгоритъм ще се окаже доста дълго. Ние обаче ще дадем пълното описание по две причини: първо, за да се запо-знаем с поне един пример за истински алгоритъм и, второ, за да можем по неговото описание да дадем и оценка за броя на елементарните преобразувания, необходими за подреждането на главоблъсканицата. [39]
Това е една наистина вълшебна играчка от серията на Рубик ( фиг. Глобусът, както ще го на-ричаме накратко, представлява сфера с картата на Земята. Около екватора, нулевия и 90-ия меридиан са отделени три взаимноперпендикулярни пояса, всеки от конто е разделен на 12 квад-ратчета, като поясите се пресичат по диаметрално противоположни квад-ратчета. Квадратчетата са поставени в специални жлебове, което позволява всеки пояс да се върти. След всяко за-въртване, кратно на 360 / 12 30, мо-же да се завърти всеки друг пояс. За подреждането помагат много и осемте неподвижни сферични триъгьлника, конто съдържат част от картата. [40]