Wspominek MM
Zdecydowałem się na Mastermindowy wspominek z dwóch powodów. Po pierwsze: nie mam akurat nic bardziej odkrywczego pod ręką; a ściślej – to, co mam, niezbyt do Łamibloga pasuje (układanki MacMahona, którymi bez rekwizytu, czyli niemanualnie trudno się rozrywać). Po drugie: stuknęło okrągłe 40 lat od pierwszych mistrzostw świata w tej grze-łamigłówce. Poniżej jedno z prostszych zadań rozwiązywanych na tych mistrzostwach. Prostszych m. in. dlatego, że kolory w kodzie nie powtarzają się.
Zadanie polega na odgadnięciu kodu (znaki zapytania) utworzonego z pięciu różnych kolorów. Wszystkich kolorów – dla uproszczenia zapisu oznaczonych cyframi – jest dziesięć. Klucz do rozwiązania stanowi siedem podanych prób odgadnięcia i ocena zgodności każdej próby z kodem. Ocenę tworzą białe i czerwone kołeczki. Biały oznacza, że w próbie jest właściwa cyfra (taka jak w kodzie), ale umieszczona na niewłaściwym kolejnym miejscu; czerwony to pełna zgodność, czyli dobra cyfra na tym samym miejscu co w kodzie.
W kilku próbach ten sam kolor powtarza się, ale jego zgodność z kodem oceniana jest zawsze tylko jednym kołeczkiem, bo w kodzie występuje on tylko raz, przy czym pierwszeństwo ma oznaczenie właściwego koloru na właściwym miejscu.
Zadanie dodatkowe dla wytrwałych: czy którąś z prób można usunąć bez utraty jednoznaczności rozwiązania?
PS. Wnuczek przeczytał tytuł i powiedział, że dziadek pisze o cukierkach M&M’s. Nie zmieniłem tytułu, bo pisownia Master Mind także jest poprawna, choć nieco „archaiczna”.
Komentarze
04936
0,4,9,3,6.
Trzecią próbę można usunąć bez utraty jednoznaczności rozwiązania.
Rozwiązaniem jest
09516
Można usunąć podpowiedzi 2,3,6. 3 i 6 można usunąć równocześnie.
76060 02
24112 10
67253 02
01497 12
25349 02
To wystarczy do jednoznacznego rozwiązania.
1. Z pierwszego wiersza wynika, że w rozwiązaniu będzie co najmniej jedna z 6 i 7, a z ostatniego, że co najmniej jedna z 2, 3, 5. A jeśli weźmiemy czwarty wiersz, to dojdziemy do wniosku, że w obu przypadkach nie możemy wziąć więcej, niż jednej cyfry.
2. Patrzymy znowu na pierwszy i ostatni wiersz i biorąc pod uwagę pkt. 1, mamy trzy pewniaki: 0, 4, 9 (wszystkie na złych miejscach).
3. Drugi wiersz: 4 jest na dobrym miejscu, wykluczamy z rozwiązania 2.
4. Piąty wiersz: są cyfry z pkt. 2, więc wykluczamy z rozwiązania 7, a z pkt. 1 mamy kolejnego pewniaka: 6.
5. Szósty wiersz: znowu cyfry 0, 4, 9, więc wykluczamy 5. Z trójki z pkt. 2 została tylko 3 i mamy komplet cyfr: 0, 3, 4, 6, 9.
6. Szósty wiersz: 4 jest na dobrym miejscu (pkt. 3), więc 0 na złym. Dodając pierwszy wiersz, wychodzi, że 0 musi być na pierwszym miejscu.
7. Wiersze piąty i ostatni: 9 nie będzie na dwóch ostatnich miejscach, więc będzie na trzecim.
8. Z pierwszego wiersza wynika, że 6 będzie na ostatnim miejscu.
Rozwiązanie: 04936
Jak widać wyżej, nie uwzględniałem w ogóle trzeciego wiersza.
Nie byłem wytrwały, tylko sobie zapisałem i samo wyszło 😉
Jak czas pozwoli, spróbuję wyrzeźbić algorytm do przeszukiwania podzbiorów wierszy. Może coś innego wyskoczy.
Czas pozwolił i tak oto wygląda minimalny zestaw dający jednoznaczne rozwiązanie:
https://snag.gy/4gMLwQ.jpg
Jedyne rozwiązanie to: 0,4,9,3,6
Otrzymamy je również po wyrzuceniu drugiego, trzeciego lub szóstego wiersza.
Ale okazuje się, że jest jeszcze lepiej. Możemy wyrzucić wiersze 3 i 6 jednocześnie i też otrzymamy powyższe, jedyne rozwiązanie 🙂
P.S.
Wyobrażam sobie radość Dziadka jeśli Wnuczek polubi matematykę !!!
Udało mi się znaleźć rozwiązanie w głowie, tzn. tylko i wyłącznie patrząc na przykład, bez kartki, bez ołówka 🙂
04936
Zadanie dla wytrwałych: można usunąć drugą lub trzecią próbę – wtedy dalej pozostanie jedno rozwiązanie. Potwierdza to poniższy program komputerowy: https://ideone.com/KxfcCk
Och… w programie w pierwszym wierszu podałem złe dane: 76070 zamiast 76060 🙁