Wygraj 2 000 000 $
Nie lubię reklam w trybie rozkazującym, nawet gdy zachęcają do czegoś chwalebnego, więc tytuł tego wpisu proszę potraktować jako parodię. Dwa miliony są jednak na poważnie i – jak się Państwo zapewne domyślają – można je zainkasować rozwiązując łamigłówkę, ale zacznę od jednego miliona.
W marcowej „Wiedzy i Życiu”, która właśnie trafiła do kiosków, opisałem łamigłówkę sprzed kilku lat, za pierwsze rozwiązanie której przysługiwał okrągły milion funtów brytyjskich. Była to układanka o nazwie Eternity, czyli Wieczność, przypominająca puzel, ale bez obrazka. Składała się z 209 wielobocznych części o jednakowej powierzchni, ale różnym kształcie, którymi należało wypełnić dwunastokąt foremny. Ze względu na gigantyczną liczbę kombinacji przy układaniu, stanowiła raczej propozycję dla wytrawnych programistów, choć nawet dla nich rozwiązywanie z pomocą komputera było pracą iście benedyktyńską, którą wielu wyceniło na więcej niż milion GBP, a inni potraktowali z przymrużeniem oka. Mimo to Eternity sprzedawała się podobno całkiem nieźle, zapewne po części jako kuriozum. Dostępna była w wielu krajach, kuchennymi drzwiami trafiła także do Polski. Nie zabrakło oczywiście chętnych do całkiem poważnych zmagań o fortunę. Przewidywano, że rozwiązywanie potrwa cztery lata. Tymczasem dwóm matematykom z Cambridge wystarczył niespełna rok, by każdy z nich został półmilionerem. O tym, jak sobie z tym poradzili, można przeczytać w „Wiedzy i Życiu”. Tuż za nimi uplasował się pewien niemiecki programista – do zajęcia pierwszego miejsca zabrakło mu dwóch tygodni, więc, niestety, obszedł się smakiem. Oto jego rozwiązanie (proszę kliknąć na obrazek).
Szacuje się, że Eternity miało mnóstwo rozwiązań, ale równocześnie od 10^50 (według jednych) do 10^400 (według innych) razy więcej nie-rozwiązań (układy nie wypełniające całego dwunastokąta, po utworzeniu których nie dawało się już nigdzie upchnąć żadnego z pozostałych do wyłożenia elementów). W sumie różnych rozwiązań znaleziono tylko sześć. Dalszych z braku bodźca nikomu nie chciało się szukać i sprawę odłożono do lamusa.
Twórca łamigłówki i sprawca całego zamieszania, Christopher Monckton, brytyjski dziennikarz z tytułem wicehrabiego, interesu raczej nie zrobił. Szczegóły nie są znane, ale fakt, że aby wypłacić nagrodę musiał sprzedać swoją rezydencję, jest dość wymowny. Mimo to już w momencie uroczystej wypłaty, w roku 2000, odgrażał się, że wkrótce opracuje i wyda drugą wersję łamigłówki Eternity z nagrodą, że ho, ho… Zapowiedzi ponawiał co roku, ale z czasem zaczęto je traktować jak obiecanki-cacanki, zwłaszcza że wicehrabiego zainteresowały też inne sprawy: zaangażował się mocno w debatę na temat globalnego ocieplenia oraz wydał książeczkę z sudoku.
Przygotowując artykuł do „Wiedzy i Życia” także miałem bardzo nikłą nadzieję, że ciąg dalszy nastąpi. I oto niespełna dwa tygodnie temu leciutko mnie zatkało, gdy trafiłem na tę oto stronę.
A zatem za pięć miesięcy świat ogarnie szał rozwiązywania Eternity II, czyli wyścig po 2 miliony dolarów – tak przynajmniej wieszczą autor i wydawca. Byłbym jednak skłonny traktować tę zapowiedź jak pobożne życzenie i raczej zapytałbym wicehrabiego Moncktona, ile rezydencji zostało mu jeszcze do sprzedania. Wprawdzie twierdzi on, że z układanką ma szansę uporać się każdy, bez względu na wiek i wykształcenie, ale wypadałoby dodać, że szanse mogą być różne. Wydawca zadbał, aby łamigłówka kusiła także wyglądem, nawet naszych milusińskich, bowiem składa się z 256 kwadratowych płytek z kolorowymi „obrazkami”. Należy nimi wypełnić diagram 16×16, a wzory na stykających się płytkach powinny do siebie pasować – i właśnie w tym cały szkopuł. Przypomina to trochę „Poplątańca” z wpisu o Rubiku sprzed paru tygodni, tylko kombinacji jest więcej – 256! (silnia). A jeszcze trzeba uwzględnić, że każdy kwadrat można ulokować na cztery sposoby. W sumie wyjdzie – bagatela – około 10^660 kombinacji (jeśli się nie kropnąłem w obliczeniach). Oczywiście, gdy zabaweczka będzie dostępna w całej okazałości, ta ponadastronomiczna liczba może zostać znacznie zmniejszona. Na razie szczegóły okryte są mgłą tajemnicy. Gdyby teraz ujawniono zbyt wiele z matematycznej struktury układanki, wówczas niewykluczone, że pierwsze poprawne rozwiązania wpłynęłyby nazajutrz po rynkowym debiucie. Inna sprawa, że i tak na ich ujawnienie czekalibyśmy do zakończenia konkursu, czyli do 31 grudnia 2008 roku, dnia – miejmy nadzieję – zapłaty.
Komentarze
To bardzo ciekawe! 🙂 Z moich wyliczeń wynika, że liczba kombinacji 256!*4^256 jest 662-cyfrowa. Już zacieram rączki i wyobrażam sobie jak dwa miliony dolarów wpadają do kieszonki jakiegoś biednego naszego rodaczka. 🙂
Potwierdzam obliczenia PS. 10^661, a nie 10^660, tylko co to za różnica przy takiej kosmicznej liczbie (liczba atomów we Wszechświecie – ściślej, tej jego części, do której nasz wzrok sięga, także uzbrojony- wynosi zaledwie 10^81). Przelecenie nawet najszybszym komputerem tylu kombinacji będzie trwać rzeczywiście Wiecznośc. Dla kogo taka łamigłówka? Chyba dla szaleńców.
Uwzgledniłbym w tych obliczeniach symetrię rozwiązania. W końcu możemy swobodnie powiedzieć, że rozwiązania np. obrócone o 90 stopni są „identyczne”. Wtedy wychodzi „tylko” 7,1 * 10^659. Ale faktycznie nie wiemy nic o pojedynczych klockach, więc podejrzewam że możliwości będzie duuużo mniej. Aha – czy wiemy że klocki są jednostronne?
Dobre pytanie, bo w pierwszej Eternity części można było odwracać. Niestety, jeśli chodzi o Eternity II nigdzie nie znalazłem informacji na ten temat.
Logicznych rozwiązań jest jednak sporo mniej, a mianowicie (przy opcji, że klocki są jednostronne):
Szukanie pierwszego klocka w polu A1 (256 klocków razy 4 pozycje) 1024 możliwości i pierwszy klocek ułożony. Jedno pole mamy na pewno w którymś z 1024 ułożeń dobre. Następnie dla każdego z 1024 ułożeń przypasowujemy klocek w miejsce A2, w najgorszym wypadku myślę, że 1 klocek na 10 będzie miał sensowne jedno dopasowanie. Mamy więc już 1024 * ~26 (255/10). Dla kolejnych pól A3, A4… analogicznie czyli. 1024 * 26 * 26 * 26 * 26 * 26 * (25 * 10) * (24 * 10) * … * (2 * 10) * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1. Pewnie większość ułożeń zacznie być sprzeczne już pod koniec układanki. Wykluczyłbym z tego powodu kolejnych 10% ułożeń. Jaki więc mamy wynik ilości koniecznych ułożeń by znaleźć rozwiązanie?
Jeśli się nie pomyliłem to 6,8481838039342720507839426676654*10^65, odejmując owe 10% i przybliżając do 10^65 mamy 6*10^65 sensownych w czasie rozwiązywania układów.
Oszacujmy czas potrzebny do wykonania tej zabawy.
Znalezienie pasującego klocka powinno potrwać średnio około 5 sekund * 256 klocków. 1280 sekund zajmie nam ułożenie jednej planszy, czyli około 22 minut, dodałbym do tego czas potrzebny na organizację i trzesące się ręce, że ktoś nas wyprzedzi. zakładam więc 0,5h na układ. Ułożenie wszystkich układów zajmie więc nam 3*10^65 godzin. Czyli „tylko” ~3,42*10^61 lat.
Powoli zaczynam nie obejmować tego co piszę więc kończę pisać i proszę o weryfikacje.
Może podzielimy się w rozwiązywaniu tego czegoś. Każdy z 7000000000 mieszkańców Ziemi miałby na przeanalizowanie swoich wytycznych 4,89^51 lat. Jeśli ktośby przypadkiem znalazł rozwiązanie każdy dostałby 2,86 * 10 ^-4 dolara. :/
dla fanow sudoku informuje ze w sobote sa eliminacje konkurencyjnej imprezy:
http://www.sfinks.org.pl/index.php
Mimo, że II-jka wygląda na trudniejszą w sensie, że mamy więcej możliwości to z drugiej strony dużo banalniejszy będzie kod programu, który będzie rozwiązań szukał.
Pewną trudnością jest fakt, że panowie matematycy, którzy I-ynkę wygrali opracowują zasady.
Moim zdanie sztuka będzie dobraniu liczyb różnych wzorków. Nie może być ich za dużo (dla 50 banalny algorytm potrzebuje na moim kompie 3 sekund na znalezienie rozwiązania, ale nie trafiłem nigdy na więcej niż jedno), z drugiej nie może być za mało, bo wtedy byle dziecko pod sklepem przypadkiem ułoży 😉
Tak, że strzelam, że mogą wprowadzić dwustronność i liczbę różnych wzorków na poziomie 20-30-tu
Chyba trochę źle na to patrzysz.
II-jka dlatego jest „banalna”, żeby łatwo można było stwierdzić że jest nie rozwiązywalna – koleś 2gi raz już nie ma zamiaru się „przejechać”.
No ciekawe, ciekawe, patrze z perspetywy informatyka z wykształceniem matematycznym. Na razie analizuje, ale zobacze jak sie będzie rozwijać. Patrząc w sposób prosty, czyli polecieć po wszystkich układach, jest rzeczywiście nierozwiązywalne, ale z drugiej strony, jest pół roku na opracowanie algorytmu, optymalizację, no i komputery też nie te same co wtedy 😉
Kris, czytales moze „Rzecz o istocie informatyki” Davida Harela? Nie wiem jakie masz wyksztalcenie, ale rozwiazanie Eternity II jest problemem NP-zupelnym i jesli dla 256 elementow znajdziesz jakies wydajne rozwiazanie to mysle, ze nie powinienes sie nim specjalnie dzielic nawet dla 2 mln $, bo pewnie taki algorytm bylby wart ciutke wiecej 😉 Analizuj, analizuj, w sumie pol roku moze Ci wystarczyc – moze nawet rozpracujesz, czy P=NP – pochwal sie moze wtedy 😉 Moze faktycznie te nie te same co wtedy komputery tez pomoga 🙂
Książki nie czytałem, ale chętnie sięgnę. Wykształcenie mam wyższe, Wydział MIM na UW, więc o problemach klasy NP trochę wiem 😉 ale mam wrażnie, że nie jest to jednak zadanie klasy problemu komiwojażera.
Wszystko zależy od warunków jakie nałożą twórcy, fakt, że siedzą przy tym matematycy i będą się starać to utrudnić (patrz: sprowadzić to do NP).
Zamodeluj sobie z sytuację gdzie będziesz miał 50 różnych wzorów na brzegach klocków i sprawdź, że najprostszy algorytm poradzi sobie z nim w kilka sekund i wcale nie musi przeglądać wszystkich możliwych układów klocków.
A co do końcówki, to aż taki naiwny nie jestem, nie drwij sobie 🙂
OK, sorry, moze troche przesadzilem, ale jak to pisalem to wlasnie wrocilem z imprezki 😉 W kazdym razie problem malpiej ukladanki jest problemem nie tylko z klasy NP, ale jest NPC, a wiec jest dokladnie tej samej klasy co problem komiwojazera – z tego co mnie uczyli (ale bylo to jakis czas temu 😉 kazdy problem NPC daje sie sprowadzic czy tam zredukowac do innego problemu NPC. Z tym co masz racje, to ze algorytm wielomianowy nie istnieje (oczywiscie prawdopodobnie 😉 ) w ogolnym przypadku – tutaj zadaniem tych, ktorzy wprowadzaja lamiglowke na rynek, jest takie jej zaprojektowanie, zeby wyeliminowac jak najwiecej roznych heurystycznych mozliwosci rozwiazania.
No chyba Marek P. zaczął się targować 😉
Z tego co widzę to chyba nie utrudnili, ale niby trochę ułatwiają (choć chyba jest to bardziej podgrzewanie atmosfery). Jest początkowy puzel i znalezienie rozwiązań dwóch mniejszych daje jakieś ułatwienie, choć jeśli dobrze skumałem to chyba tylko odsłaniają kolejny puzel.
Z punktu widzenia teoretycznego (co wspomini Karwer) nie wnosi to nic, nadal algorytm szukania jest klasy NP, ale pozostaje furtka, że kto zmaczuje więcej ten wygra, a tu może liczyć się już sprytny algorytm i trochę komputerów.
pozdro
Demo 4×4 jest oczywiście banalne, bo to ma być podpucha. Szukanie rozwiązania bez pomocy kompa zajelo mi 7 minut. Komputerowi zajęło to kilka sekund i znalazł 640 możliwych rozwiązań.
Widać już tu złośliwość układaczy, losując układ 4×4 z 4 kolorami czyli klocki są ułożone losowo (ale z założeniem że jest po 12 kolorów i rozwiązanie istnieje) trwa to dużo szybciej i rozwiązań jest zwykle tylko kilka 🙂
przesadzacie cos z tymi szacunkami. Przeciez kiedy ukladacie np. puzzle, to nie probujecie absolutnie kazdej krawedzi z kazda, tylko szukacie „pasujacych”. W tym momencie liczba kombinacji znaczaco sie zmniejsza.
Uwazam poza tym ze ulozenie krawedzi juz definiuje reszte rozwiazania, a takich mozliwosci jest tylko 64!, a poniewaz rogi nie moga byc „byle gdzie”, to tak naprawde tylko 60!*4!.