Talizmanowo
W encyklopedii matematycznej MathWorld znajduje się hasło „sześciokąt talizmanowy” zilustrowane następującym przykładem:
Ogólna matematyczna definicja takiego „zębatego” sześciokąta, stanowiącego fragment siatki heksagonalnej, podana jest w encyklopedii. Przykładowy składa się z 19 pól, w których rozmieszczono liczby od 1 do 19 tak, że – na tym polega jego „talizmanowość” – różnica między liczbami w sąsiednich polach nigdzie nie jest mniejsza od określonej liczby, w tym przypadku od 4.
Talizmanowe sześciokąty wymyślił i nazwał Joseph Madachy, spec od matematyki rekreacyjnej. Przykład pochodzi z jego książki wydanej w roku 1979. Od tego czasu nikt się takimi figurami liczbowymi bliżej nie interesował, więc postanowiłem dołożyć do tematu małą cegiełkę, zamieszczając w czerwcowym Świecie Nauki zadanie, polegające na wypełnieniu 19-polowego sześciokąta liczbami od 1 do 19 tak, aby różnica między liczbami w sąsiednich polach prawie nigdzie nie była mniejsza niż 5. Dopisałem „prawie”, bo początkowo sądziłem, że przykład w MathWorldzie jest ekstremalny i nie sposób go przebić, czyli wszystkich różnic nie mniejszych niż 5 nie idzie uzyskać. Tymczasem ku mojemu zdziwieniu okazało się to możliwe. Czy Państwu też uda się przebić MathWorlda? Nie wiem, na ile całkowicie różnych sposobów da się to zrobić, ale na pewno na więcej niż jeden.
Komentarze
Wszystkich rozwiązań jest 36748, przy czym rozwiązania izomorficzne liczone są wielokrotnie.
Próby ograniczenia rozwiązań do unikalnych z punktu widzenia izomorficznego (umieszczenie największej z liczb rogowych w konkretnym rogu oraz większego z brzegowych sąsiadów na konkretnym brzegu) ograniczyło tę liczbę do 3065… ale chyba gdzieś coś pokręciłem, bo 3065 * 12 = 36780 – czyli o 32 za dużo…
Bez eliminacji obrotów i symetrii rozwiązań jest 36780. Mamy 6 obrotów i 6 symetrii, więc istotnie różnych rozwiązań jest 36780/12=3065. Teraz spróbujemy znaleźć coś dla różnicy 6.
Dla odległości 5 program liczył ok. dobę a dla odl. =6 tylko kilka minut i okazuje się, że nie ma żadnego rozwiązania.
Problemy z formatowaniem, czyli jak przekuć problem w sukces.
2413308
153421929
2761735418
71628320339
26514371023
362512132
11223112
Powyżej widzimy sześciokąt talizmanowy o boku 4 (zamiast 3 jak w oryginalnym zadaniu)
Liczby od 1 do 37 rozmieszczono tak, aby różnica między liczbami w sąsiednich polach nigdzie nie była mniejsza niż 9.
Problem polega na tym, że liczby w poszczególnych wierszach „posklejały się”.
Zadanie nasuwa się samo, więc go nie definiuję.
Do końca lata jest sporo czasu – ponad sto tysięcy minut (!!!) – życzę wielu miłych chwil przy tym zadaniu.
To ja dodam, że pomyliłem się podając liczbę 36748 jako liczbę poprawnych układów (jest ich rzeczywiście 36780).
@Spytko z Melsztyna:
Program działał aż dobę??? Mój dla odległości 5 działa ok. 14 sekund.
@Spytko z Melsztyna:
Co do rozwiązań istotnie różnych – rzeczywiście wszystkie rozwiązania możemy posklejać w równoważne. Jest ich oczywiście 36780 / 12 = 3065.
Możemy jednak zauważyć, że część z tych rozwiązań możemy połączyć jeszcze jedną symetrią. Mianowicie każde rozwiązanie ma rozwiązanie „symetryczne”, w którym każdą liczbę x można zastąpić liczbą 20 – x.
Oczywiście jeśli środkowy element ma wartość 10, to oba rozwiązania są identyczne i nic nie sklejamy, ale dla pozostałych układów możemy je połączyć w pary: jedna ze środkowym elementem mniejszym od 10, a druga z >10.
I teraz tak:
– liczba układów ze środkowym elementem mniejszym od 10: 1362
– liczba układów ze środkowym elementem = 10: 341
– liczba układów ze środkowym elementem > 10: 1362
1362 + 341 + 1362 = 3065
@apartado:
Wyzwanie przyjęte 🙂
@miodziu
Skoro wyzwanie przyjęte, to poniżej to samo, ale minimalna odległość to 10.
„Wyzwanie” raczej w cudzysłowie nieprawdaż?
1526414
30116273
8203251728
2434102131213
11233361929
35722369
18371225
@apartado
24,13,30,8
15,34,2,19,29
27,6,17,35,4,18
7,16,28,3,20,33,9
26,5,14,37,10,23
36,25,1,21,32
11,22,31,12
kilka minut z ołówkiem 😉
@apartado
15,26,4,14
30,1,16,27,3
8,20,32,5,17,28
24,34,10,21,31,2,13
11,23,33,6,19,29
35,7,22,36,9
18,37,12,25
taki sam stopień trudności
@ Spytko z Melsztyna
Dzięki za współudział w czerpaniu radości z używania szarych komórek.
Przy tak zwanej okazji:
To zadanie wydaje mi się dobrym materiałem na „coś więcej” w dziedzinie łamigłówkowości.
Szczególnie podoba mi się to, że ułożenie takiego zadania, nie jest rzeczą banalną – 37 elementów robi już spore wrażenie na badaczach wszelkiego rodzaju kombinacji, permutacji.
Pomyślę o tym zadaniu więcej, kiedy pogoda pozwoli powylegiwać się pośród piasków niedostępnych wydm.
@apartado
Na pomysł zadania na odszyfrowywanie ciągów po wymazaniu przecinków wpadłem już dość dawno w kontekście odgadywania wylosowanych numerów lotto 🙂
Twoje zadanie jest łatwe bo możemy łatwo rozdzielać ciągi wszędzie tam gdzie pojawia się pary będące liczbami większymi od 37, np. 67, 91, 43. A więc ok. 2/3 przecinków mamy za darmo. Tu nie trzeba nawet korzystać z informacji o odległości między sąsiednimi liczbami. Dużo trudniej powinno być dla n=5 i 6. mamy wtedy zakresy liczb odpowiednio 1..61 i 1..91 i tu już ten sposób (prawie) nie działa a więc robi się sporo ciekawiej 🙂
Pomysł wart dopracowania.
@miodziu
Właśnie zastanawiam się nad sprytnym sposobem wygenerowania tych 36780 układów 🙂
W moim programie zastosowałem przeszukiwanie drzewa z odcinaniem gałęzi ale jak widać struktura plastra umożliwia jakąś drogę na skróty.
Najlepszy pomysł jaki mam na daną chwilę to wziąć wszystkie 4-elementowe podzbiory zachowujące warunek odległości od pozostałych trzech elementów. Następnie z tej listy wybierać podzbiory 3 zbiorów nie mających części wspólnych. każdą taką trójkę umieścić w 3 narożnikach i szukać trójramiennego „śmigła” dla wszystkich 64 rotacji czwórek.
Ciekaw jestem Twojego pomysłu na to zadanie 🙂
@miodziu
Errata: W tych czwórkach każdy element ma być odległy o 5 od odpowiednich dwóch z pozostałych elementów a nie od wszystkich trzech.
@Spytko z Melszyna:
Idea: pola wypełniamy po kolei, np. od góry do dołu od lewej do prawej.
W każde kolejne pole wpisujemy pierwszą pasującą liczbę i przechodzimy do następnego pola.
Jeśli w pewnym polu nie mamy już żadnej pasującej liczby, to wracamy do poprzedniego pola i wpisujemy w nie kolejną pasującą liczbę.
Implementacja rekreacyjna. W wolnej chwili prześlę kod programu.
@Spytko z Melszyna:
Oto moje programy:
http://ideone.com/D901XC
http://ideone.com/BDTFdc
Pierwszy utożsamia obroty/symetrie, drugi nie utożsamia. Różnią się tylko jednym przełącznikiem typu bool.
@miodziu
Dzięki za odpowiedź. Twój sposób jest identyczny z moim. Różnica jest tylko w rekurencji (ja jej nie mam) ale nie sądzę by to było przyczyną tak ogromnej różnicy w czasie. Kolejność pól ( w sensie ilości sąsiadów o mniejszych numerach) też mam podobną. Może to ten przedpotopowy Basic ma kolizję z dużo nowszym sprzętem, który z kolei nie należy do obecnie najszybszych ? Ale nie chce mi się już przepisywać programu na Visual Basic dla samego rozstrzygnięcia tego dylematu 🙂
@Spytko z Melszyna
Ja rozumiem, ze Basic to staroć (sam ostatnio miałem z nim do czynienia kilkanaście lat temu), ale żeby różnica szybkości była aż tak duża (wychodzi mi rzędu kilku tysięcy razy).
Może jednak robisz coś nie tak? Wklej proszę Twój kod w Basicu na ideone.com a chętnie mu się przyjrzę (tak z czystej ciekawości) i znajdę coś do poprawy 🙂
@miodziu
Jestem z powrotem 🙂
Nie mogę się dopatrzyć skąd bierze się taka różnica w czasie wykonania między naszymi programami. Idea jest taka sama. Ale może źle patrzę ?!
Jeśli będziesz miał chwilę czasu to poniżej załączam link do mojego kodu.
http://ideone.com/qObWTA