Kameleony
Postanowiłem sięgać od czasu do czasu do osobistego archiwum, a ściślej do tego, co popełniłem lat temu naście dla zagranicznych pism. Wspominam te lata z nostalgią, bo były tłuste dla ciekawych łamigłówek. Dziś konkurencja jest większa (gierki internetowe i komputerowe), a komercja i masówka bardziej dominująca. Próby zainteresowania sudokowiczów ambitniejszymi zadaniami wypadają mizernie, ale jednak coś się dzieje, choć zwykle w wymiarze niszowym. Na fali popularności sudoku pojawiło się na świecie sporo pisemek dla główkołamaczy z wyższej półki, które jednak na ogół cienko przędą lub po prostu padają. W lipcu 2006 roku BBC zaczęło wydawać znakomicie zapowiadający się MindGames Magazine, który dotrwał niestety tylko do stycznia 2007 (9 numerów). Francuscy zapaleńcy próbują natomiast wskrzesić kultowy periodyk Jeux et Strategie. Trzymam kciuki.
Nakład prestiżowego amerykańskiego magazynu Games jest dziś rzędu 60 tysięcy, a jeszcze pod koniec lat 80. przekraczał pół miliona. W jednym z numerów ukazało się wówczas, jako odrębny konkurs, poniższe zadanie autora Łamiblogu, dotyczące wyimaginowanej gry o nazwie…
Szachy kameleonowe
Na planszy złożonej z 20 sześciokątnych pól jest siedem pionków. Ruch polega na przesunięciu dowolnego z nich na sąsiednie pole. Pionki mogą przybierać jeden z trzech kolorów – czarny, biały lub czerwony, ale zmiana koloru następuje tylko w szczególnych okolicznościach:
jeśli po ruchu dwa pionki w różnych kolorach znajdą się na sąsiednich polach, a wszystkie pozostałe sąsiednie pola będą puste, wówczas kolor obu pionków zmienia się na taki sam, czyli trzeci.
Na przykład, jeśli w sytuacji przedstawionej na diagramie biały zostałby przesunięty z pola 16 na 11, to oba pionki, które znalazłyby się obok siebie – biały oraz czarny na polu 6 – natychmiast by się zaczerwieniły.
Zadanie polega na tym, aby zaczynając od pozycji na rysunku, doprowadzić w minimalnej liczbie ruchów do układu, w którym kolor wszystkich siedmiu pionków będzie jednakowy.
Choć nagrody były symboliczne, na kameleonowy konkurs wpłynęło blisko 700 rozwiązań i była to wówczas liczba przeciętna. Dziś w podobnych zabawach setka rozwiązań uznawana jest za bardzo przyzwoity wynik.
Przytoczyłem zadanie sprzed 18 lat bez zmian, choć właściwie powinienem w nim to i owo skorygować. Przede wszystkim wypadałoby zmienić nazwę szachy kameleonowe, bo łamigłówka z szachami ani trochę się nie kojarzy, a kameleony są raczej antykameleonami. Poza tym istnieje odmiana szachów bajkowych zwana kameleonowymi, ale to już całkiem inna bajka, do której zapewne kiedyś powrócę.
Rysunek nad zadaniem pochodzi z konkursu zamieszczonego na łamach Jeux et Strategie, w którym nazwiska autorów parodii Mony Lisy należało dopasować do ich dzieł. Czy komuś z Państwa uda się podać bez podpowiedzi, kto popełnił powyższy „plagiat”?
Komentarze
Wstępnie znaleziony przeze mnie wariant jest następujący:
(w nawiasach „pionki-kameleonki” i ich nowy kolor)
1. 8-3 (3, 4 czarne)
2. 4-9 (9, 15 białe)
3. 3-8
4. 13-7
5. 7-2 (2, 6 białe)
6. 8-13 (13, 18 białe)
Główna trudność tego typu zadań to fakt, że nigdy nie można być pewnym rozwiązania. To, iż osiągnęliśmy cel potrzebując niewielkiej liczby ruchów nie oznacza przecież, że nie można tego zrobić jeszcze szybciej. W praktyce (poza żmudną analizą absolutnie wszystkich wariantów) jest bardzo trudno (lub wręcz niemożliwością) udowodnienie poprawności swojej koncepcji.
Tutaj też niestety nie mam pewności, że to co przedstawiłem jest optymalne. W związku z tym będę próbować dalej, ale dopiero jutro.
Pozdrawiam
AB
Uwolniłem rozwiązanie Andrzeja69 ponieważ jest ono… do pobicia (mp)
> jeśli po ruchu dwa pionki w różnych kolorach znajdą się
> na sąsiednich polach
Czy warunkiem koniecznym jest, by któryś z tych dwóch pionków wykonał ten ruch? Chodzi mi o sytuację, gdy są trzy pionki obok siebie i jeden z nich odskoczy, zostawiając dwa pozostałe w różnych kolorach na sąsiednich polach – czy one wtedy zmieniają kolor?
Witam Pani Olu po dłuższym niewitaniu.
Oczywiście, po ruchu, który Pani opisała, też nastąpi zmiana kolorów „osamotnionej” pary.
Pozdrawiam
mp
Muszę przyznać, że odpowiedź na pytanie Oli wiele zmienia (no cóż, trzeba mi było czytać dokładnie… 😉 ).
W tej sytuacji szybka, mała modyfikacja przesłanego wcześniej wariantu polegająca na usunięciu ruchów tam i z powrotem między polami 8 i 3:
1. 13-7
2. 7-2 (2, 6 białe; 4, 8 czarne)
3. 8-13 (13, 18 białe)
4. 4-9 (9, 15 białe)
Kolejność ostatnich dwóch ruchów można odwrócić i to wydaje się trochę podejrzane.
Jutro spróbuję, czy nie uda się ujednolicić kolorów trzema ruchami.
Pozdrawiam
AB
Najpierw ustalmy jakie może być rozwiązanie .
Jeżeli pionkom nadamy wartości np. czarny – 1 , czerwony – 2 , biały – 3 to można zauważyć , że po każdej transformacji wartość liczbowa wszystkich pionków pozostanie taka sama albo zmieni się o 3 .
Dla pozycji wyjściowej wartość liczbowa tego układu wynosi 15 .
A zatem po każdej tranformacji wartość układu będzie podzielna przez 3 .
Jedyny układ 7 takich samych pionków o wartości podzielnej przez 3 to same białe pionki (21) .
A zatem układ według podanych zasad można przemienić wyłącznie w 7 białych pionków .
Minimalna ilość ruchów potrzebna do takiej konwersji to 4 .
1)czerwona+biała=2 czarne
2,3,4)czarna+czerwona=2 białe
Niestety nie jest możliwe aby zrobić to w 4 ruchach ponieważ po ruchu 8-3 i 4-9 nie jesteśmy w stanie dokonać następnych konwersji.
A zatem może da się to zrobić pięcioma ruchami ?
Tak – to jest możliwe.
13-7 , 16-17 , 18-19 , 7-2 , 8-13
Pozdrowienia
AC
Moje rozwiązanie:
1) 13 -> 19 (4 i 8 czarnieją)
2) 15 -> 9
3) 8 -> 14
4) 14 -> 19 (4, 9, 18, 19 bieleją)
5) 12 -> 7 (6, 7 bieleją)
Pozdrawiam, Ola 🙂
> Czy komuś z Państwa uda się podać bez podpowiedzi, kto
> popełnił powyższy ?plagiat??
Bez podpowiedzi nie 🙂 Ale z podpowiedzią i owszem: Gary Larson.
1) Z 13 na 7
2) Z 7 na 2. Wtedy 6 i 2 zmienią się na białe a 4 i 8 na czarne.
3) Z 8 na 13 zmiana na białe
4) Z 15 na 9 zmiana na białe
Kameleonowa rozgrywka:
1. 13-7
2. 7-2
3. 8-13
4. 4-9 lub 15-9
I mamy białego kameleona.
Pozdrawiam
Do Oli
W pierwszym ruchu oczywiście jest 13->12 .
Bardzo sympatyczne rozwiązanie , które trochę zadaje kłam mojemu rozumowaniu , jakoby do czterech konwersji potrzebne były cztery ruchy .
Ale myślę , że optymalne jest i tak rozwiązanie w pięciu ruchach (chociaż wcale nie jest potrzebna konwersja nieruchomych pionów przez odejście innym pionem) . Ciekawe czy ktoś poda jakieś inne rozwiązanie ?
Pozdrawiam
AC
Alku, wbrew pozorom Twoje rozumowanie kłamu nie zadaje… Dlatego uwolniłem rozwiązania Oli i Twoje.
mp
Do Alka:
Muszę Ci pogratulować bardzo sprytnego dowodu na konieczność „wybielenia” pionków, ale niestety nie mogę się zgodzić z drugą częścią Twojej wypowiedzi.
Możliwość zmiany kolorów przez odejście zmienia bardzo dużo. Zauważ, że np. Twoje rozwiązanie nie jest do końca poprawne: W czwartym ruchu (7-2) kolory zmienią nie tylko pionki na polach 2 i 6 (na biały), ale jednocześnie pionki 4 i 8 na czarny. To akurat nie stanowi dużego problemu: zmieniając kolejność dwóch ostatnich ruchów cel osiągniesz.
Natomiast największa różnica polega na tym, że można w jednym ruchu zmienić kolory czterech pionków (a teoretycznie nawet sześciu) na raz! Także masz rację pisząc, że należy dokonać czterech transformacji, ale wcale nie musi to oznaczać czterech ruchów.
Powodzenia w dalszej optymalizacji.
Pozdrawiam
AB
We wcześniejszym komentarzu zapowiedziałem, że spróbuję zunifikować pionki w trzech ruchach.
Zamiast tego postaram się udowodnić, że minimalna liczba posunięć to jednak cztery.
Na wstępie przypomnę to, co napisał wcześniej Alek: Pionki należy wybielić i potrzebne są na to cztery transformacje: czerwony+biały na dwa czarne i trzykrotnie czerwony+czarny na dwa białe.
Zamiana istniejącego czarnego pionka wraz z jednym z czerwonych na dwa białe może nastąpić w tym samym ruchu, co jakaś inna transformacja, ale pozostałe trzy nie mogą się ze sobą łączyć.
Dlaczego?
Konwersja czerwony+biały na dwa czarne musi, z oczywistych względów, poprzedzać przemianę każdego z nowych czarnych.
Oba nowe czarne nie mogą zmienić barwy w tym samym ruchu, gdyż w momencie odejścia pierwszym z nich, drugi nie ma kontaktu z żadnym innym pionkiem (w przeciwnym przypadku wcześniejsza konwersja nie miałaby miejsca). Oczywiście można podejść najpierw czerwonym pionkiem do jednego z dwóch czarnych, a dopiero następnie odejść drugim (wówczas możliwa jest jednoczesna przemiana), ale nie zmienia to faktu, że na oba nowe czarne pionki potrzebne są dwa niezależne ruchy. Jeśli doliczymy do tego pierwotną transformację to już mamy trzy.
Załóżmy teraz, że te trzy ruchy wystarczą. Oznacza to, że czwarta metamorfoza musi nastąpić przy okazji jednej z tych trzech, ale, co ważniejsze, oznacza to też brak jakichkolwiek „martwych przebiegów”.
A więc zamiana pary czerwony z białym na dwa czarne musi nastąpić w pierwszym ruchu. Można to osiągnąć na trzy sposoby: 8-3 (3, 4 czarne), 13-12 (4, 8 czarne) i 13-17 (4, 8 czarne). Nie chcę się tutaj rozwodzić opisując każdy z tych przypadków, bo już na pierwszy rzut oka widać, że w żadnym z nich nie da się w dwóch ruchach przemienić nawet samych nowych czarnych pionków (nie wspominając już o tym istniejącym od początku).
Wniosek taki, że w trzech ruchach kolorów nie ujednolicimy.
Wynika z tego zatem, że chyba moje drugie, skorygowane, czteroruchowe rozwiązanie jest poprawne. Ciekaw jestem, czy są jakieś inne równorzędne (nie licząc oczywiście przestawienia kolejności dwóch ostatnich posunięć).
Pozdrawiam
AB
Panie Marku – ciekawy jestem ile z tych 700 rozwiązań na konkurs było poprawnych .
Moja wstępna interpretacja zasad zakładała , że zmienia się para pionków , z których jeden wykonał ruch i dopiero rozwiązanie Oli pokazało mi , że się myliłem . I dlatego moje stwierdzenie , że do 4 konwersji potrzeba 4 ruchów było błędne (w jednym ruchu można zrobić więcej niż jedną przemianę).
Zresztą rozwiązania Jawy , Andrzeja i Andrzeja69 (szacunek Panowie) też mają podwójną konwersję , a że jeden ruch jest bezprzemianowy to przypadkiem wyszło na moje .
Niestety moja satysfakcja jest niepełna , ponieważ uwalniając moje rozwiązanie nie skomentował Pan , że jest również do pobicia (rozumiem , że byłaby to za duża podpowiedź) i tym samym nie optymalizowałem rozwiązania do niższej liczby ruchów .
A zadanie scharakteryzowałbym tak jak to uczynił ktoś z porucznikiem Colombo (wspaniała rola Petera Falk) – „taki miły , malutki piesek , który biega dookoła i merdając ogonem zakopuje miny” .
Pozdrowienia
AC
> > Ola pisze: 2008-01-11 o godz. 09:25
> > Moje rozwiązanie:
> > 1) 13 -> 19 (4 i 8 czarnieją)
> > 2) 15 -> 9
> > 3) 8 -> 14
> > 4) 14 -> 19 (4, 9, 18, 19 bieleją)
> > 5) 12 -> 7 (6, 7 bieleją)
> Alek pisze: 2008-01-11 o godz. 17:39
> Do Oli
> W pierwszym ruchu oczywiście jest 13->12 .
Oczywiście 😉 Pomyliłam się przy przepisywaniu.
Pozdrawiam, Ola
Alku, cytuję tekst sprzed lat (przy okazji będzie wprawka z angielskiego):
Nearly half of the 700 entrants found a four-move solution. The winnings moves were: 13-7, 7-2, 8-13, and 15-9. The last move could also have been 4-9, and the last two moves were interchangeable, making four variations in all.
Otóż właśnie, cztery „wariacje” są jakby słabą stroną łamigłówki, ale z drugiej strony w zadaniach szachowych warianty są normą, tylko pierwszy ruch rozwiązania powinien być jeden jedyny – a wszak to szachy, choć kameleonowe
.
m
Dziękuję bardzo Panie Marku za redakcyjny komentarz do rozwiązań. Zawsze zazdrościłem Amerykanom ich perfekcyjnej znajomości angielskiego :).
Pozostaję z nieśmiałą nadzieją, że Pana archiwa zawierają jeszcze niejeden taki rodzynek, i że będzie nam dane zakosztować przyjemności spróbowania następnych (myślę oczywiście o zadaniach, a nie o komentarzach).
Pozdrowienia
ac
Dziękuję Alku za miłe słowa. Archiwa są niewielkie, ale coś się jeszcze z nich wyłuska.
Na razie głowię się nad zagadką, której rozwiązania pewnie nigdy nie poznam: kto zgłosił Łamiblog do konkursu Bloger roku 2007?
Ze względu na wrodzoną skromność i niechęć do rywalizacji nigdy bym się na to sam nie zdecydował (o braku szans nie wspominając), a próżność nie pozwoliła mi nie przyklepać zgłoszenia.
Taki „dziwoblog” jak Łamiblog zapewne odpadnie w przedbiegach, ale to miłe, że komuś się podobają moje pisanki, więc serdeczne dzięki nieznajomy zgłaszaczu.
PS tymczasem mam kandydata w konkursie na najlepszego komentatora blogu, jeśli kiedyś ktoś wymyśli taki konkurs.