Пентомино

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

Фиг. 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-те решения на формата на ван де Ветеринг. Предполагам, че бройът класове нѣма да е много по-голѣм, но че те ще съдържат повече елементи, отколкото в изучаванийът от Хансен случай.

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