19 żetonów
Nie planowałem zamieszczać zadania Elastic bands z ubiegłorocznych łamigłówkowych mistrzostw świata, a przynajmniej nie teraz. Wspomniałem tylko, że było inspiracją do napisania o „przeplatance” brainstring. Skoro jednak w komentarzach pojawiła się prośba o jego przedstawienie, to czemu nie.
Przypominam reguły (przykład z rozwiązaniem jest w poprzednim wpisie).
Oznaczone kolejnymi liczbami 19 żetonów (bo XIX WPC) połączonych jest trwale elastycznymi gumkami:
Poniżej znajduje się ten sam splot, ale żetony rozmieszczone są inaczej, a więc inny jest także układ łączących je gumek:
Proszę ponumerować żetony.
Na mistrzostwach gumki były sprzężone z paroma innymi łamigłówkami. Inaczej mówiąc, kilka liczb z rozwiązań innych zadań można było wpisać jako podpowiedzi do wskazanych żetonów – albo odwrotnie, jeśli ktoś wcześniej uporał się z gumkami.
Podpowiedzi w Elastic bands nie są jednak konieczne, choć zadanie jest bez nich dość trudne, a raczej żmudne. Wymaga systematycznego rozgryzania krok po kroku, skupienia, spostrzegawczości i cierpliwości. W związku z tym zapewne nie każdemu się spodoba. Ja za takimi nie przepadam, ale jeśli się przełamię i zacznę, to „dłubanina” wciąga. Najważniejsze znaleźć właściwy punkt zaczepienia i wykazać dużo samozaparcia. Czy ktoś wykaże, to się okaże.
Komentarze z prawidłowymi rozwiązaniami uwalniane są wieczorem w przeddzień kolejnego wpisu. Wpisy pojawiają się co 3-4 dni.
Komentarze
Od kółka położonego najwyżej: 13,10,2,1,17,16,14,5,19,4,7,12,3,6,8,15,18,9,11.
13,10,2,1,17,16,14,5,19,4,7,12,3,6,8,15,18,9,11
Nie jest tak trudne, „jak go malują”. Jeżeli znajdzie się na początku położenie 5-ki, to zaraz potem mamy 12-kę, itd,itd i idzie przyjemnie, jak po sznurku.
Jak już faktycznie znajdzie punkt zaczepienia to zadanie idzie jak burza. (całość <5 min, choć pewnie miałem szczęście z tym początkiem)
Wypisuję od najwyższego zgodnie z ruchem zegara:
13 10 2 1 17 16 14 5 19 4 7 12 3 6 8 15 18 9 11
Punkt zaczepienia to (dla mnie) 3 żetony 4-gumkowe – wzajemnie połączone; każdy ma dodatkowo 2 sąsiadów, z których 13 i 7 łączą się przechodząc tylko przez jeden dodatkowy żeton.
Z tego od razu oznaczamy 12 i 5. Z 12 mamy 11, która łączy się z 8 przez jeden żeton. A dalej już tylko wpisujemy…
Jako ostatnie wpisałem bodaj 18.
Począwszy od żetonu znajdującego się najwyżej, zgodnie z ruchem wskazówek zegara: 13 10 2 1 17 16 14 5 19 4 7 12 3 6 8 15 18 9 11
Miejsca 1, 2, … , 19 zajmują liczby:
13, 10, 2, 1, 17, 16, 14, 5, 19, 4, 7, 12, 3, 6, 8, 15, 18, 9, 11.
Pozdrawiam,
jazz
13, 10, 2, 1, 17, 16, 14, 5, 19, 4, 7, 12, 3, 6, 8, 15, 18, 9, 11
Pozdrawiam 🙂
Dzisiaj rano rozsupłałem tę przeplatankę, ale nie zapisałem rozwiązania.
Te rysunki pokazują, jaki był mój punkt zaczepienia:
http://pokazywarka.pl/422ypv/
Pozdrawiam
Witam
Idąc od „szczytu” zgodnie z wskazówkami zegara:
13,10,2,1,17,16,14,5,19,4,7,12,3,6,8,15,18,9,11
Ciężko było zacząć ale potem już z górki.
Pozdrawiam
Piotr
Te zadania to przykład problemów izomorfiznu grafów, ważnego chociażby w analizowaniu substancji chemicznych. Informatycy głowią się nad rozwiązaniem czy problem ten można rozwiązać w czasie wielomianowym.
Pozdrawiam
Piotr
Nie takie trudne a calkiem przyjemne:
13-10-2-1-17-16-14-5-19-4-7-12-3-6-8-15-18-9-11
a
Zadanie to rozwiązywałem dwiema metodami. Pierwszym razem poszukiwałem jakichkolwiek charakterystycznych cech obu grafów i po dość żmudnych dociekaniach udało mi się je rozwiązać. Zaś drugim razem zdecydowałem się na inne podejście. Po zauważeniu, że prawy graf jest grafem planarnym, zdecydowałem się użyć programu GeoGebra, utworzyłem oba grafy i po kilku graficznych przekształceniach zdecydwanie szybciej znalazłem poszukiwany izomorfizm, o jakim pisze Piotr. Szybkie znalezienie rozwiązania było możliwe dzięki planarności grafów. W ogólniejszym przypadku jest to dość trudny problem. Ciekawy jestem jak radzą sobie z takimi zadaniami zawodnicy na zawodach.
Pozdrawiam,
jazz
W związku z fragmentem komentarza Jazza:
„Ciekawy jestem jak radzą sobie z takimi zadaniami zawodnicy na zawodach.”
pozwolę sobie podpowiedzieć zasadę jednego ze sposobów stosowanego na zawodach – moim zdaniem najbardziej skutecznego:
próbujemy rozbić graf na rozłączne podgrafy o niewielu (3-4) wierzchołkach w taki sposób, aby jeden z tych podgrafów jakoś różnił się od pozostałych. Najlepiej oczywiście, aby wszystkie podgrafy, poza jednym „odmieńcem”, były izopodgrafami, wtedy łatwo wskazać go na diagramie-rozwiązaniu i dalej już leci…
mp
Nie było takie trudne, ani żmudne – wystarczyło znaleźć 12 (która znajduje się w tym samym miejscu co na pierwszym obrazku) i potem leciało już hurtem bez zastanowienia. Od północy będą to: 13, 10, 2, 1, 17, 16, 14, 5, 19, 4, 7, 12, 3, 6, 8, 15, 18, 9, 11. Nie wiem ile czasu mają na to na turniejach, mnie zajęło dosłownie parę minut. Mój sposób: węzły mogą mieć trzech (większość) lub czterech (takich jest trójka) sąsiadów – zapisałem zatem przy każdym węźle jego (najkrótszą) odległość od węzła z czterema sąsiadami. Potem wystarczy spostrzec, że istnieje tylko jedna „dwójka” sąsiadująca z dwiema „jedynkami” i „trójką” – i jest to 12.