Przeskocz do treści

Delta mi!

Loading

Kolorowe czapeczki – kontynuacja

Andrzej Dąbrowski

o artykule ...

  • Publikacja w Delcie: luty 2006
  • Publikacja elektroniczna: 30-01-2016
  • Autor: Andrzej Dąbrowski
    Afiliacja: Instytut Matematyczny, Uniwersytet Wrocławski
  • Wersja do druku [application/pdf]: (172 KB)

Niedługo po ukazaniu się mojego artykułu Kolorowe czapeczki do redakcji przyszedł list od wieloletniego Czytelnika Delty, Jana Błaszczyńskiego, z propozycją rozwiązania postawionego tam problemu. Proste rozwiązanie Jana Błaszczyńskiego, w przeciwieństwie do przedstawionego w moim artykule, jest deterministyczne ii |; i na dodatek pozwala rozstrzygnąć problem dla dowolnej liczby kolorów czapeczek i dowolnej liczby krasnoludków.

Dwa dni później przyszedł list od innego Czytelnika artykułu, studenta pierwszego roku matematyki stosowanej na Politechnice Gdańskiej, Marcina Krzywkowskiego, proponujący inne rozwiązanie, też proste i deterministyczne. Propozycja Marcina Krzywkowskiego omija dodatkowe założenie zawarte w rozwiązaniu Jana Błaszczyńskiego, ale ogranicza się do dwóch rodzajów czapeczek.

Oryginalne zadanie było takie:

Zadanie. Królewna Śnieżka wezwała siedmiu krasnoludków i oświadczyła, że w związku z wielkim świętem w najbliższą niedzielę postanowiła nagrodzić ich pracowitość.
- Przygotowałam dla was białe i kolorowe czapeczki. Nie powiem wam, ani ile białych, ani ile kolorowych czapeczek przygotowałam. Każdemu z was nałożę jedną z czapeczek na głowę, ale by było bardziej uroczyście, przedtem zgaszę światło. Po zapaleniu światła zobaczycie czapeczki u swoich kolegów, ale swojej nie będziecie mogli zobaczyć. Każdy z was dostanie 2 kartki ze swoim imieniem i napisem: Mam białą czapeczkę albo Mam kolorową czapeczkę. Jeśli któryś z was zechce, powinien wybrać jedną z nich i wrzucić do koszyka na środku sali. Ale pamiętajcie! Nie wolno wam się porozumiewać! Wspaniała nagroda - tu Królewna uśmiechnęła się tajemniczo - będzie wam wręczona, jeśli okaże się, że nikt się nie pomylił, a przynajmniej jedna osoba zgadła, jaką ma czapeczkę na głowie.

Rozwiązania Czytelników Delty

Warunki zadania pozwalają ustalić wcześniej strategię postępowania. W obu rozwiązaniach krasnoludki umawiają się działać "na tempo". W rozwiązaniu Jana Błaszczyńskiego tempo wyznacza kolejność, w jakiej krasnoludki będą wrzucać kartki do koszyka. Marcin Krzywkowski proponuje, aby krasnoludki podejmowały działanie co ustalony odcinek czasu, na przykład co 5 sekund.

Jan Błaszczyński zaproponował rozwiązanie przy dodatkowym założeniu, że na głowach krasnoludków są wszystkie rodzaje czapeczek. Warunkiem koniecznym do rozwiązania jest ubranie krasnoludków we wszystkie rodzaje czapeczek - skoro Śnieżka przygotowała białe i czerwone czapeczki, to z każdego rodzaju istnieje co najmniej jedna - pisze autor. Warunek ten przenosi on na przypadek dowolnej liczby rodzajów czapeczek - ma być reprezentowany każdy spośród |q typów czapeczek.

Rozwiązanie to najprościej przedstawić w postaci grafu.

obrazek

 iv | Tu krasnoludek wpisuje typ, którego brakuje.

 iv | Tu krasnoludek wpisuje typ, którego brakuje.

Gdy krasnoludek nr 1 widzi czapeczki q − 1 typów, wie, że jego czapeczka ma typ, którego brakuje i daje odpowiedź poprawną. Gdy krasnoludek nr 1 nie wrzuca kartki, to oznacza, że nie widzi q −1 typów czapeczek. Gdyby tych typów było mniej niż q −1, to wraz z jego czapeczką mogłoby być mniej niż q typów, co jest sprzeczne z założeniem, że wszystkie typy czapeczek są reprezentowane. Tak więc na głowach krasnoludków innych niż nr 1 są reprezentowane wszystkie typy. Sytuacja początkowa się powtarza, ale z mniejszą o 1 liczbą krasnoludków. W k -tym kroku albo krasnoludek zobaczy |q− 1 typów czapeczek, albo wśród |n− k pozostałych krasnoludków są reprezentowane wszystkie typy czapeczek. Najpóźniej (n + 1− q) -ty krasnoludek zobaczy u swoich kolegów o wyższych numerach q − 1 różnych typów, co kończy zgadywanie.

Podobne w pomyśle rozwiązanie dla dwóch kolorów czapeczek i dowolnej liczby n > 1 krasnoludków proponuje Marcin Krzywkowski.

Krok 0 (5 sekund od początku)

Do koszyka podchodzą wyłącznie ci, którzy widzą czapeczki jednego koloru. Są możliwe 3 przypadki:

  • Podszedł jeden krasnoludek - wtedy wrzuca kartkę z kolorem innym niż widzi.
  • Podszedł więcej niż jeden krasnoludek - wtedy każdy z nich wrzuca kartkę z kolorem takim, jak widzi.
  • Nie podszedł żaden krasnoludek - wtedy każdy krasnoludek widzi co najmniej jedną czapeczkę każdego koloru.

Krok 1 (10 sekund od początku)

Do koszyka podchodzą wyłącznie ci, którzy widzą dokładnie jedną czapeczkę koloru A i więcej niż jedną czapeczkę koloru B. Każdy z nich wnioskuje, że ma na głowie czapeczkę koloru A i taką kartkę wrzuca do koszyka.

Jeżeli do koszyka nie podszedł żaden krasnoludek, to każdy z nich widzi co najmniej po dwie czapeczki każdego koloru.

Krok 2 (15 sekund od początku)

Do koszyka podchodzą wyłącznie ci, którzy widzą dokładnie dwie czapeczki koloru A i więcej niż dwie czapeczki koloru B. Każdy z nich wnioskuje, że ma na głowie czapeczkę koloru A i taką kartkę wrzuca do koszyka.

Jeżeli do koszyka nie podszedł żaden krasnoludek, to każdy z nich widzi co najmniej po trzy czapeczki każdego koloru. Wykonujemy krok 3.

Ogólnie, jeżeli w k −1 kroku do koszyka nie podszedł żaden krasnoludek, to każdy z nich widzi co najmniej po k czapeczek każdego koloru. I wtedy wykonuje się następujący krok.

Krok k ( 5 k 1 sekund od początku)

Do koszyka podchodzą wyłącznie ci, którzy widzą dokładnie k czapeczek koloru A i więcej niż k czapeczek koloru B. Każdy z nich wnioskuje, że ma na głowie czapeczkę koloru A i taką kartkę wrzuca do koszyka.

Postępowanie to musi się skończyć sukcesem wcześniej niż w kroku o numerze (n − 1)/2.

Dlaczego oryginalne rozwiązanie jest tak skomplikowane?

Oba rozwiązania przysłane przez Czytelników łamią założenie o tym, że podczas zgadywania nie wolno się porozumiewać. Przedstawione rozwiązania pozwalają kolejnym krasnoludkom przekazać swoją wiedzę poprzez fakt wstrzymania się od wrzucania kartek i wykonywanie tych gestów w kolejnych "krokach". Takie działanie jest z założenia niedozwolone.

To jednak ja nieświadomie sprowokowałem możliwość innej interpretacji założeń. W pierwotnej wersji artykułu każdy krasnoludek miał do wyboru trzy kartki: Mam białą czapeczkę, Mam kolorową czapeczkę i Rezygnuję z odpowiedzi. Ponadto na dany sygnał każdy z krasnoludków w tym samym czasie musiałby wrzucić do koszyka jedną z trzech kartek.

Złośliwy chochlik namówił mnie, żeby skrócić opis i zamiast polecenia wrzucenia kartki Rezygnuję z odpowiedzi zaproponowałem rezygnację z wrzucania. Przy okazji wypadł z tekstu artykułu nakaz jednoczesnego wrzucenia kartek.

Dzięki temu poznaliśmy jednak dwa ciekawe rozwiązania nieco innego zadania.

Propozycja

Nie jest znane rozwiązanie dla 3 typów czapeczek i |n krasnoludków. Rozwiązanie Wesołka z artykułu |xiii daje prawdopodobieństwo sukcesu p = 1/3. Oczekujemy propozycji rozwiązań o jak największym prawdopodobieństwie sukcesu dla 3 typów czapeczek i n krasnoludków. Na początek dla n = 3. Najciekawsze rozwiązania przedstawimy w Delcie.