Sześć siedem dwa

https://xpil.eu/xj0 📋

"O żeż", pomyśli teraz co drugi Czytelnik, "numerek w tytule, pewnie znów będzie smęcić o matematyce, idę stąd"

A no będzie, owszem, ale nie za dużo i o niezbyt skomplikowanej matematyce. Przynajmniej na pierwszy rzut oka 😉

Niedawno odkryłem jeszcze jeden powód, dla którego należy szanować liczbę sześć (słownie: 6), która od dawien dawna jest moją ulubioną wśród liczb, o czym zresztą już kiedyś pisalem, ale nie chce mi się teraz szukać.

Otóż szóstka jako pierwsza wyłamuje się ze schematu superpermutacji.

Yyyyy, que pasa?

Superpermutacja N znaków to najkrótszy ciąg znaków, który zawiera w sobie każdą N-elementową permutację tych znaków. Poniżej przykłady (dla ułatwienia skorzystamy z cyfr):

Nota bene, wie ktoś może dlaczeg mówimy "cyfr i liter" a nie "litr i cyfer"?

Dla N=2 mamy:

121

Permutacje zbioru dwuelementowego są dwie: 12, 21. Można je "skleić" dwójką i w wyniku dostaniemy 121. Albo 212, jak kto woli.

Dla N=3:

123121321

Powyższy tekst zawiera komplet sześciu permutacji cyfr 1, 2 i 3: 123, 132, 213, 231, 312, 321. I znów, są one umiejętnie "posklejane".

Dla N = 4:

123412314231243121342132413214321

Dla N = 5:

123451234152341253412354123145231425314235142315423124531243

W powyższych czterech przypadkach ilość znaków w każdej z superpermutacji daje się wyliczyć wzorem:

L(N) = 2!+3!+...+N!

Dla N=6 sytuacja ulega zmianie!

Okazuje się bowiem, że zamiast spodziewanych 673 znaków, dla N=6 da się skonstruować superpermutację o dlugości 672 znaki.

Czemu tak?

W szczegóły się nie będę zagnieżdżał, bo szczerze powiedziawszy sam nie do końca czuję temat. Powiem tylko tyle, że dla N > 6 wzór na długość najkrótszej permutacji wynosi:

n! + (n-1)! + (n-2)! + (n-3)! + n - 3

Natomiast sama metoda konstruowania superpermutacji opiera się na zmodyfikowanym w 2013 roku algorytmie wyszukiwania ścieżek hamiltonowskich w grafach Cayleya grup symetrycznych.

I wszystko jasne.

https://xpil.eu/xj0 📋