Класификация на решенията за една форма от тетрахексове

Поправка от 19 юли 2019. След откриване на една трансформация, която свръзва решения 24 и 8, предишните групи II и IV се сливат в настоящата група I. Нѣколко групи сѫ преименувани.

Вече писах за класификацията на решенията за правоѫгълникът 6 × 10 от пентомина, разработена от Хансен. С помощта на компютърна програма той показва, че 2339-те решения могѫт да бѫдѫт разделени в 911 класа, най-големийът от които има 50 елемента, а най-малките само по един. В рамките на всеки клас решенията могѫт да бѫдѫт трансформирани едно в друго с помощта на три операции: (1) разместване на положението само на две фигурки; (2) разменяне на местата на два участъка от решението (които имат еднаква форма); (3) симетрична операция върху подредбата на един участък.

Реших да проведѫ аналогичен анализ на решенията на по-проста форма, образувана със седемте тетрахекса, които сѫ показани на фиг. 1.

Фиг. 1. Седемте тетрахекса и имената им на български.

Подбрах форма, която има относително много решения, за да има какво да се класифицира. Показана е на фиг. 2 и може да се нарече Артишок. Има общо 30 решения, без да броим симетричните (които се получават чрез отразяване спрѣмо оста на симетрия).

 

Фиг. 2. Артишокът има 30 несиметрични решения.

При анализът се оказа, че има само едно прилагане на трансформация (2) по Хансен, която е размѣна на еднакви по форма участъци. Всички останѫли трансформации съответстват на (3) по Хансен, а именно симетрична операция върху подредбата на участък. Често участъците сѫ с размер само две фигурки, но тъй като сѫ симетрични не може да се говори за трансформация от тип (1). 

Решенията се разпадат на осем групи, най-голѣмата от които съдържа единадесет решения, а трите най-малки -- само по едно.  Нека отбележим, че при това положение най-голѣмата група поражда повече от една трета от всички решения. 

Фиг. 3. Решения 27 и 26 се превръщат в 23 и 25, и обратното, чрез завъртане не участък състоящ се от четири фигурки, т.е. повече от половината от общийът брой. Трансформацията между 7-10 и 8-9 се състои в завъртане на блок от пет тетрахекса, отбелѣзан в червено. Решение 24 има два частично застѫпващи се участъка, които осигуряват връзката между шестте решения в лѣво и четирите в дѣсно. Гредата остава неподвижна.

Допълнение от 12 юли 2019. В рамките на група II сѫществува още една трансформация, която свръзва решения 23 и 27. Става въпрос за размѣна на два участъка с еднакви очертания, както е показано на фиг. 3Б. В конкретнийът случай тази трансформация е с резултат, еквивалентен на завъртането на двата участъка заедно.

Фиг. 3Б. Двата участъка с еднаква форма сѫ оцветени в сиво и жълто. Разменянето им е еквивалентно на завъртане на целийът оцветен участък от четири фигурки.

На фиг. 4 сѫ показани решенията от група II. И тук единствено гредата остава неподвижна. 

Фиг. 4. Група II за Артишокът -- седем решения. Гредата е единствената неподвижна фигурка в тази група. Решения 19 и 20 могѫт да бѫдѫт доведени до 21, което, от своя страна, се обръща в 28 след четири трансформации.

Следващите четири групи сѫ по-малки, а последните три, съдържащи само по едно решение, сѫ представени заедно. Струва си да се отбележи, че единствено в група IV гредата не е разположена по периферията на артишокът.

Фиг. 4. Група III съдържа пет решения.

Фиг. 6. Групи IV  и V съдържат симетричен участък "капка", изграден по два различни начина. Група IV е уникална заради разположението на гредата, в средата на артишокът.

Фиг. 7. Трите решения, които образуват самостоятелни групи. 5 и 22 съдържат симетрични участъци, но със симетричен вѫтрешен строеж, поради което отразяването им не води до нови решения. Решение 15 е уникално сред всичките 30 решения с това, че не съдържа нито един симетричен участък, изграден от повече от една фигурка.

В сбит вид информацията за групите може да се представи в следната табличка:

Групи	Решения	Брой трансформации	Бележка
Ι	7, 8, 9, 10, 16, 17, 19, 20, 21, 28, 29	10	Единствена с размѣна на еднакви по контур участъци (вж. фиг. 3Б).
ΙI	11, 12, 23, 24, 25, 26, 27	6
ΙII	2, 3, 4, 6, 18	4
IV	0, 1	1	Единствена с разположение на гредата вѫтре в артишокът.
V	13, 14	1
VI	5	-
VII	22	-
VIII	15	-	Единствена без нито един симетричен участък, съставен от повече от една фигурка.

Допълнение от 19 юли 2019. Групите от решения могѫт да се представѭт като графове, в които премахваме самите изображения и оставяме само номерата. Всѣка трансформация е ребро на графът. Между нѣкои върхове сѫществуват повече от едно ребра, което е отбелѣзано с числото 2 на фиг. 8.

Фиг. 8. Всички групи представени като граф.

Макар и това да се дължи в не малка степен на пространствената подредба на отделните групи, безспорно ми се струва, че фиг. 8 притежава естетическа стойност, напомняйки за карта на звездното небе, с отбелѣзани съзвездия. Би било интересно да се разработи критерий, по който да се определят ѫглите между ребрата, независимо дали имат общ връх или не. Ребрата между двойките 11 - 12, 26 - 27 и 23 - 25 трѣбва да сѫ успоредни, защото става въпрос за една и сѫща трансформация. Наличието на ребра между еднакви върхове предполага, че ребрата не трѣбва да сѫ прави, а например дѫги от окрѫжност: тогава ѫглите между двете връзки 23-27 и останѫлите ще могѫт да сѫ различни. Принципно различен подход би бил да се дадѫт координати на всѣко решение и ребрата да се начертаѭт както дойде.

Пентомино

Изминахѫ двадесет години откакто открих в училищната библиотека първото томче на Математически развлечения, българскийът превод на избрани статии на Мартин Гарднер по развлекателна математика. 

Фиг. 1. Корицата на книгата, която със сигурност е повлияла най-силно на влечението ми към математиката.

Тогава наистина живеехме в различно време, достѫпът до информация и до знание беше по-труден, по-бавен, понѣкога дори невъзможен. Но пък като ни паднеше нещо в рѫцете, не го пускахме лесно. Така и аз, вместо да прелистѭ книгата и да ѭ върнѫ на рафтът в библиотеката, ѭ записвах и презаписвах, за да прочетѫ всѣка глава и да ѝ се насладѭ. Разбира се, не всички глави предзвикахѫ еднакъв интерес у мене. Но посветените на полиомината определено ме запалихѫ, защото много добре си спомням, че ползвах тетрадка с големи квадратчета, за да ги изчертавам и изрѣзвам. Още тогава научих за книгата на Соломон Голомб, посветена на полиомината. Но, от тогавашната перспектива, дори да ѭ видѭ нѣкога изглеждаше невъзможно. Да не говорим, че и не знаех никакъв английски.

А онзи ден книгата пристигнѫ у дома, от далечен Тексас, и си ѭ разглеждам.

Така се получава, че вече съм чел доста неща по темата в Интернет и от книгата на Голомб не научих нови неща. Но пък имах възможност да се замислѭ за нѣкои философски страни на пентомината, и на полиформите (обобщение на понятието за всѣкакви форми и измерения).

Впечатление ми направи по-специално следнийът абзац от книгата:

There is a lesson in plausible reasoning to be learned from the pentominoes. Given certain basic data, one labours long and hard to fit them into a pattern. Having succeeded, one then believes the pattern to be the only one that "fits the facts", indeed, that the data are merely manifestations of the beautiful, comprehensive whole constructed from them. The pentominoes illustrate that many different patterns may be constructed from the same data, all equally valid, and that the nature of the final pattern is determined more by the desired shape than by the information at hand. It is also possible that, for certain data, no pattern of the type the constructor is conditioned to seek may exist.

Solomon W. Golomb, Polyominoes. 2nd edition, 1994.

Въпросът ми се струва много добър: какъв е смисълът на пъзел с множество решения? Какво приложение, в широкийът смисъл на думата, може да имат 65-те решения на шахматната дъска с квадратна дупка посредата?

Първата идея, която ми идва, е че количеството решения е своеобразна мѣрка за сложността на формата. Колкото по-сложна е една форма, толкова по-малко възможност за вариране на положенията на фигурките ще дава тя и, следователно, решенията ще сѫ по-малко, но и по-лесни за намиране, защото контурите на формата, която пълним, ще ни налагат употребяваме тази или онази фигурка. Оказва се, че сложността на формата е обратно пропорционална на сложността на намиране на решение.

И двете сложности, обаче, остават относителни спрѣмо наборът от фигурки, с който работим. Може да се зададе общийът въпрос: за определен набор фигурки, която е формата, с най-много решения? Кои сѫ формите с едно единствено решение?

Човек би могъл да си помисли, че отговорът на първийът въпрос е правоѫгълникът 6 × 10, защото формата му е проста и максимално близка до квадрат. Но проблемът с формите с висока степен на симетрия е, че много от решенията им сѫ еквивалентни. Бройът решения за всеки правоѫгълник е всѫщност четири пѫти по-малък, именно заради двете оси на симетрия. Така 6 × 10 има "едва" 2339 решения. Но шахматната дъска с махнѫт ѫгъл 2 × 2 има 5027, може би заради единствената си ос на симетрия (диагонална) и заради близостта си с квадратът.

Фиг. 2. Осакатена по този начин, шахматната дъска има 5027 решения.

Ад ван дe Ветеринг (Add van de Wetering) е открил форма, за която сѫществуват 16 720 решения. Тя не притежава никаква симетрия и дори не е по-близко до квадрат от шахматната дъска с отрѣзан ѫгъл.

Фиг. 3. Формата на ван де Ветеринг с 16 720 решения.

Дори и бегъл поглед върху конкретните решения за тези плодовити форми води към друг интересен въпрос, касаещ понятието "принципно различно решение". Да видим за какво става въпрос.

Отстраняването на симетрични решения касае единствено цѣлата форма. Но понѣкога решенията съдържат симетрични участъци, които водят до механично пораждане на нови решения, както е показано на фиг. 4.

Фиг. 4. Сивите участъци в тези две решения сѫ симетрични спрѣмо диагонална ос,минаващата през горнийът им десен и долнийът лѣв ѫгъл. Можем ли да твърдим, че това сѫ принципно различни решения?

В сѫщото време, нѣкои решения съдържат участъци с еднаква форма и размери, които сѫ взаимнозаменяеми. Така жълтийът и сивийът участък на фиг. 1. сѫ не само симетрични, но и с еднаква форма и поради това пораждат група от общо 8 решения, чието принципно различие е спорно.

Плодовитите форми използват и друг механизъм за натрупване на решения, основаващ се на плодовити участъци, както е видно на фиг. 5. Струва си да се забележи, че сивийът участък, без да е симетричен, може да бѫде запълнен от едни и сѫщи фигурки по различни начини. Нещо повече, във второто и третото решение N-пентоминото се намира в едно и сѫщо положение, т.е. плодовийът участък има на свой ред плодовит подучастък!

Фиг. 5. Група решения с плодовити участъци (в сиво).

През 1991 Уилфред Хансен (Wilfred J. Hansen) вече е изследвал задълбочено връзките между решенията за правоѫгълника 6 × 10 и е открил, че 2339-те решения могѫт да се разпределѭт в 911 класа, съдържащи се от 1 до 50 решения. Той обаче не разглежда като еквивалетни решения, при които един участък, съдържащ повече от две фигурки, може да бѫде пренареден. Хансен взема предвид само пренареждания на участъци с две фигурки. Намирам този подход за половинчат: пренареждането или не трѣбва да се счита за еквивалентна операция или да се счита за такава независимо от бройът фигурки, които съдържа. Хансен обяснява, че във вторийът случай бройът класове се променя само с три. Интересно би било аналогичен анализ да се проведе за 16 720-те решения на формата на ван де Ветеринг. Предполагам, че бройът класове нѣма да е много по-голѣм, но че те ще съдържат повече елементи, отколкото в изучаванийът от Хансен случай.

Макар и да не достигнѫхме до фундаментален отговор на въпросът за смисълът на многообразието от решения за дадена форма, поне навлѣзохме в сѫщината на явлението.

Паркетиране на равнината и пъзли

От нѣколко седмици насам се връщам към едни от "Математическите развлечения", с които се срещнѫх за първи пѫт в пети клас благодарение на книгата на Мартин Гарднър. Благодарѭ на хората, които сѫ ѭ превели на български и над библиотекарьт, който ѭ е осигурил в училище "Димчо Дебелянов", кѫдето учех тогава!

Тогава изрѣзвах пентомина и хексомина от тетрадки с карирани листи и ги редѣх на масичката в холът у дѣдо и баба. Днес е възможно все още да сѫ останѫли нѣкои от фигурките, между листите на стари тетрадки или в други съкровищници от онези дни.

Да припомнѭ набързо за какво става въпрос.

Когато вземем n на брой квадратчета с еднакви размери, можем да ги подредим така, че рѫбовете им да се докосват. Ако вземем само едно квадратче, получава се една фигурка, наречена мономино. Ако вземем две, пак се получава само една фигурка -- домино (от тук идва и самото окончание). С три квадратчета се получават две тримина. Така стигаме до дванадесетте пентомина, които сѫ изключително интересен комплект.

Пълнийът комплект от пентомина.

Прекрасното при този комплект е, че 12 × 5 = 60 и от фигурките могѫт да се подредѭт различни правоѫгълници: 3 × 20, 4 × 15, 5 × 12, 6 × 10. Наблизо до кѫщата, кѫдето живеехме във Варна, има блокове, чиито фасади сѫ украсени с пана от пентомина. Явно архитектът сѫщо се е радвал на тези фигурки.

Тази снимка взех от интернет. Цѣлостното излѫчване напомня за България. Когато се приберѫ във Варна това лѣто, ще снимам блоковете, които съм виждал в детството си.

Пентомината могѫт дори да бѫдѫт подредени във формата на паралелепипед с приятно съотношение на дължините на рѫбовете: 3 × 4 × 5. Това се случва, когато заместим квадратчетата с кубчета. Сѫществуват много игри, които ползват пентомина, обикновено съставени именно от кубчета. В послените три години купих два такива комплекта, но най-скѫпийът ми си остава този, който направи баща ми, когато още бѣх ученик. Тогава той беше дърводелец. Нѣкак съм успѣл да го убедѭ да отдели толкова много време и внимание, защото беше направил не само пентомина, а сѫщо и пълнийът комплект от хексомина (35 на брой) и от простраствени пентакубове (фигурки от пет кубчета, но разположени не само в равнината, както е при полиомината). Цѣлата колекция напълваше една кутия за обувки, при рѫб на кубчето около два сантиметра. Сега тези фигурки сѫ нѣкѫде във Варна, на неизвестно за мене мѣсто.

Паралелепипед, сглобен от комплектът Cayro.

Сега погледът ми е много повече привлечен от фигурките, образувани от по-сложни елементи.

Преди малко повече от месец се амбицирах да изрежѫ всичките фигурки образувани от квадрат, правоѫгълен триѫгълник с катети единица и правоѫгълен триѫгълник с катети едно и две. Пълнийът комплект може да се види на сайтът на F. Esser тук. Изработването на самийът комплект не беше трудно, заради силното присѫствие на прави ѫгли. За съжаление, сглобяването на форми от този комплект се оказа доста трудно на рѫка.

Рѫчноизработенийът ми комплект. Самата форма ѭ копирах от интернет.

След това дойде ред на пъзел, измислен от Кристофър Монктън (Christopher Monckton), ексцентричен английски благородник. Неговийът сайт вече не сѫществува, но самийът пъзел може все още да се види на сайта на Вихер, тук. Използва се мрежа от квадрати и равностранни триѫгълници, известна като "плосконос квадрат". Самите квадрати сѫ разрѣзани на два равнобедрени правоѫгълни триѫгълника. Всѣка от двадесетте фигурки се състои от четири триѫгълника (два равностранни и два правоѫгълни, или три от единийът вид и само един от другийът).

Решетката, която се използва за комплектът на Монктън. На английски това паркетиране на равнината се нарича snub square. В Уикипедия има малко информация за него.

На сайтът на Вихер има нѣколко примера за форми, образувани с този комплект. В течение на нѣколко седмици се блъсках със SVG и JavaScript, но в крайна сметка успѣх да напишѫ код, който намира решения за произволна форма. В моите чертежи квадратите сѫ разбити на четири малки равнобедрени триѫгълника. Това е само за удобство при програмирането.

Общата площ на фигурките на Монктън е 40 правоѫгълни и 40 равностранни триѫгълника. Възможни сѫ форми с много добра симетрия.

Две големи яйца. Всѣко едно съдържа точно 20 правоѫгълни и 20 равностранни триѫгълника.

Две припокриващи се големи яйца и едно малко. Общата област на големите е сѫщо малко яйце. Малкото яйце съдържа по 8 от двата вида триѫгълници. За съжаление, не е възможно да се образуват пет отделни малки яйца.

От този пъзел по естествен начин достигнѫх до така наречените петоѫгълници от Кайро (защото там имало много тротоари с такива плочки; на мен ми се струва, че и във Варна има, това лѣто ще ги издирвам). Когато центровете на квадратите и равностранните триѫгълници в мрежата "плосконос квадрат" бѫдѫт съединени, се получава мрежа от еднакви петоѫгълници, които, четири по четири, се съединяват в шестоѫгълници.

Самите пропорции на петоѫгълници от Кайро могѫт да варират, но нѣкои отношения остават константи. Два от ѫглите винѫги сѫ прави, четири от страните винѫги сѫ еднакво дълги. Ѫгълът срещу вариращата страна се движи от 90° до 270°, но в тези два крайни случая фигурата вече не е петоѫгълник.

На сѫщийът принцип, както при полиомината, могѫт да се образуват и поликайрота. В интернет има доста сайтове, на които сѫ представени различни комплекти (от монокайро до хептокайро и нагоре). Интерес за мен представляват тетракайротата, които сѫ седемнадесет на брой. Като цѣло, забелязвамъ, че оптималнийът размер на един комплект от подобни фигури е между десет и двадесет. Ако сѫ по-малко, не е интересно, ако сѫ повече, стават твърде трудни за боравене.

Всички тетракайрота. Картинката е взета от сайта на Ливио Дзука (Livio Zucca).

Както и при елементите от пъзелът на Монктън, в първийът момент ме изумява трудността да бѫдѫт запомнени различните конфигурации. Нѣкои сѫ много лесни за възприемане (първата и последната), други могѫт да бѫдѫт възприети като осакатени шестоѫгълници (последната на първийът и първата на вторийът ред). Умът, привикнѫл към ориентация в правоѫгълни мрежи, се оказва силно затруднен тук. Понятията горе/долу и лѣво/дѣсно, с помощта на които се ориентираме, сѫ неприложими. За да може човек да се ориентира в тази мрежа и да разбере и запомни формите на тетракайротата, нужна е нѣкаква концептуализация на пространството.

Съседите на един петоѫгълник.

Има две насоки за осмисляне: изхождайки от единичните петоѫгълници или от шестоѫгълниците, които те образуват четири по четири.

В случай, че искаме да се ориентираме посредством петоѫгълниците, нужни сѫ ни много повече от четирите думи, достатъчни за ориентрация в квадратна мрежа (горе/долу, лѣво/дѣсно): петоѫгълникът A се намира в уникално отношение спрѣмо жълтийът петоѫгълник. За него трѣбва дума, която нѣма антоним, или поне нѣма симетричен антоним, предполагащ огледалност. Всички останѫли петоѫгълници се разпределят в двойки: B - C, D - E, P - Q. Значи трѣбват три двойки симетрични/огледални думи. В крайна сметка, нужни сѫ общо седем думи. За моментът, да използваме съставни думи. Спрѣмо жълтийът петоѫгълник, другите се намират както следва:
A - направо;
B - направо-дѣсно;
C - направо-лѣво;
D - обратно-дѣсно;
E - обратно-лѣво;
P - надѣсно;
Q - налѣво.
Следването на една и сѫща посока в квадратна мрежа ни прекарва по прави линии (надолу-надолу-надолу...). Тук този обход ни кара да се въртим в крѫг: тръгвайки от жълтийът петоѫгълник и следвайки посока винѫги направо, ще прескачаме безкрайно между него и A. С посока винѫги направо-дѣсно пък ще се въртим в четворката жълт-B-P-D.

Какво ще се получи, ако се ориентираме по шестоѫгълниците? Нужно е, от една страна, да ситуираме петоѫгълниците в шестоѫгълниците, от друга, да ситуираме шестоѫгълниците един спрѣмо друг.

Ориентация, изхождаща от шестоѫгълниците. Системата е напълно симетрична, но сѫ нужни десет думи.

Защо човекът ползва само симетрични системи за ориентация? Заради анатомията му, безспорно. Ходим по земята, затова за нас има горе и долу; имаме две симетрично разположени рѫце, затова за нас има дѣсно и лѣво; имаме очи само от едната страна на тѣлото, затова за нас има напред и назад. За посоките на светът ползваме четири думи -- север, юг, изток и запад. Но в естонскийът и финскийът имат осем думи. Ще дам пример с естонски, защото думите там сѫ по-кратки, започвайки от север и въртейки се по посока на часовниковата стрелка: põhi, kirre, ida, kagu, lõuna, edel, lääs, loe.

Пчелите има тѣло със сѫщийът вид симетрия, като нашето, но строѭт килийки, които сѫ шестоѫгълни и разположени по съответнийът начин. Ако можехѫ да говорѭт, бихѫ ли имали шест думи за посоките в шестоѫгълна мрежа? Или, казано по по-човешки начин, как бихѫ се ориентирали жителите на град с улици във формата на шестоѫгълна мрежа (мечтата на Валтер Кристалер)? "Вървете по тази улица и, когато стигнете до църквата, завийте на..."? Решение, и то за проблемът е пространството, а не просто в равнината, навѣрно се съдържа в терминологията на кристалографите.

Макар и тук да е нарѣзана на квадратни парчета, пчелната пита се състои от шестоѫгълници.

NALDO е името на мрежата от средства за обществен транспорт в юго-западна Германия. Картата е разделена на шестоѫгълници, като всеки един има нещо като централен град. Това навѣрно е свързано с моделът на Кристалер.

Всички тези въпроси сѫ интересни, но да се върнем към комплектът от седемнадесет тетракайрота. Понеже един шестоѫгълник е съставен от четири петоѫгълника, както и всѣко тетракайро, човек би могъл да се надѣва комплектът да може да покрива форми, съставени от седемнадесет шестоѫгълника. За съжаление, това е невъзможно. Невъзможни сѫ каквито и да е симетрични форми, в които участват всичките тетракайрота. Ако обаче оставим настрана едно от тетракайротата, сѫществуват хиляди начини да бѫде покрит ромб с рѫб от четири шестоѫгълника.

Едно от решенията за ромбът с рѫб от четири шестоѫгълника. Едно от тетракайротата не е използвано.

Ливио Дзука е доказал, че симетрични форми не могѫт да се образуват и с 55-те пентакайрота. Много тѫжно.