Gra Żaba na wykresie mniszka lekarskiego
W lokalnym stawie słychać hałas. Grupa żab chce zorganizować przyjęcie urodzinowe!
W stawie znajdują się łącznie 22 lilie, z których każda zawiera jedną żabę. Oznaczono je numerami od 0 do 21. Aby ułatwić sobie życie, każda żaba zbudowała jeden most do każdego ze swoich sąsiadów. Żaba 0 jest najpopularniejszą żabą i ma żaby od 1 do 7 jako swoich sąsiadów, podczas gdy żaby od 8 do 21 mają tylko poprzednią żabę jako sąsiada.
Dziewiąta żaba chce świętować swoje urodziny. Czy możesz poprowadzić wszystkie inne żaby do jej lilii?
Możesz poinstruować wszystkie n żab na niepustym polu lilii A, aby przeskoczyły do innego niepustego pola lilii B wtedy i tylko wtedy, gdy istnieje ścieżka między A i B, która składa się dokładnie z n unikalnych mostów.
Ilustruje to poniższy obrazek.
Innymi słowy, zasady gry w żabę są formalnie podane jako:
Gra w żabę
Gra toczy się na wykresie, którego wierzchołki reprezentują „pady lilii” (lilie wodne).
Na początku gry umieść po jednej żabie na każdej liliowej podkładce.
Celem gry jest przeniesienie wszystkich żab na jedną poduszkę lilii.
Możesz przenieść dokładnie wszystkie n żab znajdujących się na podkładce lilii A na inny obszar lilii B wtedy i tylko wtedy, gdy oba pola lilii nie są puste (zawierają co najmniej jedną żabę) i istnieje ścieżka od A do B składająca się z dokładnie n unikalnych krawędzi .
Następnie układanka na obrazku jest formalnie podana jako:
Celem łamigłówki jest rozwiązanie gry w żabę na 9 wierzchołku podanego wykresu (patrz obrazek powyżej). Wykres składa się z wierzchołka korzenia oznaczonego jako zerowy wierzchołek, z którym łączymy 6 wierzchołków liści oznaczonych jako {1, 2, 3, 4, 5, 6} i jeden wykres ścieżki składający się z 15 wierzchołków, których wierzchołki są oznaczone jako {7, 8 , 9, ..., 21}.
Możesz wydrukować wykres i użyć tokenów do reprezentowania żab. Jeśli nie, użycie długopisu i kartki papieru nie powinno stanowić problemu (i tak ostatecznie to rozwiązałem).
PS Na rozgrzewkę, czy widzisz, że grę w żabę można rozwiązać na dowolnym wierzchołku wykresu ścieżki ?
To dlatego, że:
Umieść wykres ścieżkowy P n z n wierzchołkami na osi liczbowej. Jeśli zaczniesz od środkowego wierzchołka i naprzemiennie skaczesz w lewo i w prawo (lub odwrotnie, w zależności od parzystości n), zobaczysz, że ścieżkę można łatwo rozwiązać w wierzchołkach liścia (wierzchołki stopnia 1).
Teraz, aby rozwiązać wykres ścieżki P n w dowolnym wierzchołku v, po prostu podziel go na dwa podgrafy ścieżki, które dzielą wierzchołek v jako liść (i nie mają wspólnych wierzchołków) i rozwiąż każdy podgraf przy użyciu strategii wierzchołków liścia.
Ta łamigłówka została zainspirowana moim uogólnieniem zagadki Numberphile , od linii do wykresów. Wykres podany w tej układance jest szczególny, ponieważ jest najmniejszym kontrprzykładem do jednego z moich starych przypuszczeń na temat „wykresów mniszka lekarskiego” .
Aby stworzyć obraz układanki (podanego wykresu), użyłem edytora wykresów csacademy .
PS Mathpickle ma więcej takich łamigłówek! Widzieć:
https://mathpickle.com/project/lazy-toad-puzzles-counting-symmetry/
https://mathpickle.com/project/lazy-toads-on-a-star/
Odpowiedzi
Unikalne rozwiązanie?
Grupa A:
Przenieś 5 żab na 0 z płatków 1 do 5.
Przenieś 6 żab z 0 do 12 = 7 żab na 12.
Przenieś 7 żab z 12 na 19 = 8 żab na 19.
Przenieś 1 żabę z 20 do 21 = 2 żaby na 21.
Przenieś 2 żaby od 21 do 19 = 10 żab na 19.
Przenieś 10 żab od 19 do 9 = 11 żab na 9.
Grupa B:
Przenieś 1 żabę z 13 do 14 = 2 żaby na 14.
Przenieś 1 żabę z 15 na 16 = 2 żaby na 16.
Przenieś 2 żaby z 16 do 14 = 4 żaby na 14.
Przesuń 4 żaby z 14 do 10 = 5 żab dalej 10.
Przesuń 5 żab z 10 do 6 = 6 żab na 6.
Przesuń 6 żab z 6 do 11 = 7 żab na 11.
Przesuń 7 żab z 11 do 18 = 8 żab na 18.
Przesuń 1 żabę z 17 do 18 = 9 żaby na 18.
Przenieś 9 żab z 18 na 9 = 20 żab na 9.
I w końcu:
Przesuń 1 żabę od 8 do 7 = 2 żaby na 7.
Przesuń 2 żaby od 7 do 9 = IMPREZA NA 9 !!
Mogą istnieć inne rozwiązania, ale:
Krok 1:
Zbierz wszystkie płatki na 0, przez 1 → 0, 2 → 0, 3 → 0, 4 → 0, 5 → 0, 6 → 0
Krok 2:
Zrób jedyne co możesz z 7 żabami na 0: przeskocz je do 13; następnie przeskocz tam 8 żab do 21. Masz teraz 9 żab na 21: 0, 1, 2, 3, 4, 5, 6, 13, 21.
Krok 3:
Jedyny skok, jaki te 9 żab może wykonać bezpośrednio, to 12, ale utkniesz. W rzeczywistości chcemy dostać je bezpośrednio do 9. Dlatego potrzebujemy jeszcze 3 żab! Najlepiej jest pobrać je z sąsiednich łodyg lilii, 18, 19 i 20, przez 19 → 20, (19) (20) → 18, (18) (19) (20) → 21. Mamy teraz 12 żab na 21 i możemy przeskoczyć je wszystkie do 9.
Krok 4:
Teoretycznie jesteśmy skończeni, ponieważ PO pokazuje, jak doprowadzić wszystkie żaby na ścieżkę do jednego z jego punktów końcowych, więc możemy 7-8 do 9 i 10-17 do 9, ale żeby być wyraźnym: 8 → 7, 78 → 9; oraz 13 → 14, (13) (14) → 12, (12) (13) (14) → 15, (12) (13) (14) (15) → 11, (11) (12) (13) (14) (15) → 16, (11) (12) (13) (14) (15) (16) → 10, (10) (11) (12) (13) (14) (15) (16 ) → 17 oraz (10) (11) (12) (13) (14) (15) (16) (17) → 9.
Oryginalna nieprawidłowa odpowiedź - O rany, jestem głupi.
Oto jedno rozwiązanie, mogą być inne:
Pierwszą rzeczą, na którą należy zwrócić uwagę, jest to, że możesz użyć 0 tylko raz, więc musisz uważać, aby najpierw scentralizować niektóre płatki (1-6), a następnie przenieść je wszystkie poza 0. Ale ile chcesz scentralizować? Oczywistą pierwszą rzeczą do zrobienia jest wszystko: przesuń wszystkie 1-6 płatków do 0, a następnie przeskocz 7 żab do 13. Ale to szybko się kończy: przeskakujesz 8 żab do 21, a następnie 9 żab do 12 i utkniesz .
Ale nie musisz brać wszystkich płatków naraz, ponieważ możesz przeskoczyć kilka żab do płatka, a następnie wskoczyć z powrotem do 9. Więc spróbujmy wziąć wszystkie płatki oprócz jednego do 0, dając serie: 1 → 0, 2 → 0, 3 → 0, 4 → 0, 5 → 0, 012345 → 12, 012345 (12) → 19. Potrzebujemy dwóch dodatkowych żab, aby wrócić do 19, które możemy złapać przez 20 → 21 i (20) (21) → 19, a cały bałagan 012345 (12) (19) (20) (21) wraca do 9 .
Następne kroki:
W tym momencie masz masę żab na 9 i pojedyncze żaby na 6, 7, 8, 10, 11 i 13-18. Najpierw wyczyśćmy stronę płatka. Potrzebujemy trzech żab na 6, aby wskoczyć z powrotem do 9, co możemy uzyskać za pomocą 8 → 7, 78 → 6 i 678 → 9. Teraz 10 i 11 dochodzą do 9 z 10 → 11, (10) (11) → 9. W końcu mamy sześć żab w rzędzie między 13 a 18, które można zsumować w 15 na podstawie podanego wyniku wykresu ścieżki (wyraźnie: 14 → 13, (13) (14) → 15, 17 → 16, (16) (17) → 18, (16) (17) (18) → 15), a następnie ta masa przeskakuje do 9, kończąc zagadkę.