Dodaj do ulubionych

Siedmiu Dezerterów

18.05.05, 02:45
Zagadka ze znanej kategorii 'uwolnienia skazańców’ i wyjątkowo ciężki orzech
do zgryzienia. Oto ona:

W celi siedzi siedmiu dezerterów skazanych na śmierć przez rozstrzelanie.
Oznajmiono im, że dostaną ostatnią szansę uratowania swego życia. Przed
egzekucją bowiem każdemu kolejnemu skazańcowi zostanie nałożony na głowę
czarny lub biały kapelusz wybrany w sposób losowy (poprzez rzut monetą) i to w
taki sposób, żeby żaden ze skazańców nie widział koloru swego kapelusza, ale
za to widział kapelusze współwięźniów. Następnie każdy ze skazańców będzie
miał możliwość odgadnąć kolor swego kapelusza lub odpowiedzieć ‘nie wiem’, ale
odbędzie się to w taki sposób, że jego odpowiedź nie będzie słyszana przez
pozostałą szóstkę.

Wszyscy więźniowie będą uwolnieni jeśli choć jeden z nich spróbuje odgadnąć
kolor swego kapelusza i żaden z odgadujących nie pomyli się co do koloru swego
kapelusza. Ale uwaga! Więźniom po nałożeniu kapeluszy nie wolno przekazywać
sobie w żaden sposób żadnych informacji, gdyż natychmiast wszyscy zostaną
rozstrzelani.

Dziś jest noc przed dniem egzekucji, wszyscy więźniowe siedzą w jednej celi.
Postanowili opracować najlepszy plan, który dawałby im największą szansę na
uratowanie życia. Co obmyślili? Jaka strategia zapewni im największe
prawdopodobieństwo przeżycia?

Życzę wszystkim owocnych zmagań nad tą łamigłówką. Jeśli macie już jakąś
pierwszą myśl to zapuście ją, a postaram się na bieżąco komentować odpowiedzi.

CdM
Obserwuj wątek
    • Gość: kama Re: Siedmiu Dezerterów IP: *.neoplus.adsl.tpnet.pl 18.05.05, 10:45
      cardemon napisał: ...
      Wszyscy więźniowie będą uwolnieni jeśli choć jeden z nich spróbuje odgadnąć
      kolor swego kapelusza ...
      "Spróbuje odgadnąc"? Chyba odgadnie - próbować może każdy.
      Czy więxniowie wiedzą, który z nich zgłasza się do odpowiedzi?Jesli tak, to
      mogą kolejnościa zgłoszeń przekazać innym informacje, np ten pierwszy mówi "Nie
      wiem" który widzi obok siebie dwia jednakowe kolory(jest taki conajmniej
      jeden).Jego sąsiedzi wiedzą wtedy , jaki mają kolor, widzac sąsiada po drugiej
      stronie tego, który sie zgłosił. Pzostali wszyscy mówia "nie wiem".Warunki
      zadania zostały spełnione - nikt sie nie pomylił.
      Jezeli więźniowie nie wiedzą, który z nichjuż odpowiedział, pozostaje im tylko
      powiedzieć "nie wiem" z wyjątkiem ostatniego, który powie jeden z kolorów - ma
      50% prawdopodobieństwa,że zgadnie.

      • cardemon Re: Siedmiu Dezerterów 18.05.05, 12:58
        Gość portalu: kama napisał(a):

        > cardemon napisał: ...
        > Wszyscy więźniowie będą uwolnieni jeśli choć jeden z nich spróbuje odgadnąć
        > kolor swego kapelusza ...
        > "Spróbuje odgadnąc"? Chyba odgadnie - próbować może każdy.

        Otóż nie. "Choć jeden spróbuje odgadnąć" oznacza, że choć jeden wypowiedział się
        co do koloru swego kapelusza, czyli chodzi o wyeliminowanie przypadku, że cała
        siódemka pasuje (mówi "nie wiem").

        > Czy więxniowie wiedzą, który z nich zgłasza się do odpowiedzi?Jesli tak, to
        > mogą kolejnościa zgłoszeń przekazać innym informacje, np ten pierwszy mówi "Nie
        >
        > wiem" który widzi obok siebie dwia jednakowe kolory(jest taki conajmniej
        > jeden).Jego sąsiedzi wiedzą wtedy , jaki mają kolor, widzac sąsiada po drugiej
        >
        > stronie tego, który sie zgłosił. Pzostali wszyscy mówia "nie wiem".Warunki
        > zadania zostały spełnione - nikt sie nie pomylił.

        W warunkach zadania jest mowa o tym, że więźniowie nie mogą się porozumiewać
        podczas całego kapeluszowego procederu. Umówmy się, że oddanie głosu przez
        każdego ze skazańców jest niejawne i wszyscy oddają głos dokładnie w tym samym
        czasie.

        Tak czy siak mamy pierwszą propozycję (brawo!) - 50% prawdopodobieństwo
        uratowania życia. Kto daje więcej?

        Pozdrawiam,
        CdM
        • kornel-1 Re: Siedmiu Dezerterów 18.05.05, 16:50
          Strategia: Jeśli widzisz 5 lub 6 kapeluszy w tym samym kolorze zgłoś kolor
          przeciwny, w innym wypadku milcz ("nie wiem").
          Ale to tylko zawodne intuicyjne rozwiązanie. A prawdopodobieństwa nie potrafię
          policzyć w tej chwili.
          Kornel
    • Gość: pafcio Re: Siedmiu Dezerterów IP: *.aster.pl / *.aster.pl 18.05.05, 16:49
      ten kto widzi 3 białe i 3 czarne mówi nie wiem
      ten kto widzi 4 czarne i 2 białe mówi biały
      ten kto widzi 4 białe i 2 czarne mówi czarny
      ten kto widzi 4 czarne i 2 białe mówi biały
      ten kto widzi 5 czarnych i 1 biały mówi nie wiem
      ten kto widzi 5 białych i 1 czarny mówi nie wiem
      ten kto widzi 6 białych mówi czarny
      ten kto widzi 6 czarnych mówi biały

      wydaje mi się, że przeżyją z prawdopodobieństwem 65,625%

      pozdrawiam
      parcio
    • Gość: Kama Re: Siedmiu Dezerterów IP: *.neoplus.adsl.tpnet.pl 18.05.05, 21:45
      Więźniowie wiedzą,ze najbardziej orawdopodobny rozkłads kolorów jest 4b : 3c
      lub odwrotnie 3b : 4c (prawdopodobieństwo jest 35/64). Umawiaja sie więc: kto
      zobavzy 3b i 3c powie "nie wiem", a kto 4b i 2c powie c lub odwrotnie 2b i 4c
      to b.Jednak takich którzy zobaczą 4b+2c możed być nie trech, a pięciu(przy
      rozkładzzie początkowym 5b+2ć) i kazdy mówiac c spowoduje nieszczęście.Byłoby
      dobrze, gdyby tytlko jeden podał kolor, a pozostali "nie wiem" - wtedy
      prawdopodobieństwo byłoby spore, ale przy braku jakielkolwiek komunikacji
      zlozyć należy odpowiedzialnośc na jednego, wytypowanego w przeddzień.Jeśli
      zobaczy przewagę jednego koloru - poda drugi, jesli zobaczy równowagę -
      zaryzykuje.
    • andy._ Re: Siedmiu Dezerterów 18.05.05, 21:48
      Potwierdzam wynik pafcia i mogę jeszcze dodać, że tej klasie rozwiązań (dla
      danego układu skazaniec mówi nie wiem albo głosuje na kolor mniejszościowy)
      jest to rozwiązanie najlepsze i jedyne. Teraz można próbować bardziej
      wyrafinowanych strategii typu podział siódemki na grupki, z których każda
      stosuje inną podstrategię, ale wygląda, że to raczej pogorszy wynik ...

      Pozdr.
      A._
        • Gość: Kujonik Re: Siedmiu Dezerterów IP: *.neoplus.adsl.tpnet.pl 18.05.05, 23:53
          Idea kamy wydaje sie najbardziej efektywna. Więźniowie typują swego
          reprezentanta, którego instruują: Jeżeli widzisz wiecej czarnych - powiedz
          biały, jesli więcej białych - powiedz czarny. Jesli jednakowo -powiedz dowolną
          barwę.
          Prawdopodobieństwo,że przezyjemy jest wtedy 49/64=76,56%
          Większa liczba podających kolor zmniejsza to prawdopodobieństwo.Tu milczenie
          jest złotem.
          • Gość: lukkasz Re: Siedmiu Dezerterów IP: *.acn.waw.pl 19.05.05, 01:43
            kolory są od siebie niezależne. wyobraźmy sobie, że kolory losowane są kolejno,
            a zgaduje ostatnia osoba. przecież wiedza o tym, co wypadło dotychczas nie
            powie jej nic o tym, jaki kolor ona wylosuje. tak więc wyłonienie reprezentanta
            daje prawdopodobieństwo 1/2 prawidłowej odpowiedzi.
            lukkasz
    • cardemon Krótki komentarz - Re: Siedmiu Dezerterów 19.05.05, 02:10
      Mamy na razie kilka opisanych strategii. Szeregując je według prawdopodobieństwa
      uratowania się skazańców otrzymujemy:

      65,625% - Pafcio (druga myśl Kamy, ta bez typowania reprezentanta, jest bardzo
      podobna)

      54,6875% - Kornel z poprawką Andy'ego

      50% - Kama (wytypowanie jednego zgadującego, obliczenia Kujonika są niepoprawne)

      32,812% - Kornel


      Na razie nikt nie przedstawił optymalnej strategii, więc łamigłówka nadal nie
      jest rozwiązana.
      Dla Uli natomiast mam radę. Spróbuj rozwiązać powyższą zagadkę na trzech więźniach.

      CdM
    • Gość: grzesiek Re: Siedmiu Dezerterów IP: *.cbk.waw.pl / *.cbk.waw.pl 19.05.05, 11:12
      Prawdopodobieństwa rozkladów nie mają tu nic do rzeczy. To jaki mam
      kapelusz na glowie nie zależy od tego co mają inni. Wynika to wprost
      z procedury losowania kapeluszy - każdy kapelusz jest wylosowany niezależnie
      przy pomocy rzutu monetą (zakladam że jest fifty fifty).

      Gdyby wszyscy odpowiedzieli "nie wiem" to będa skazani, a zatem ktoś powinien
      zgadywać. Z drugiej strony każde zgadywanie niesie ryzyko wpadki, a zatem aby
      je zminimalizować to zgadywać powinien tylko jeden skazaniec. Z powodu już
      opisanego powyżej jest wszystko jedno który z nich będzie zgadywal, a zatem
      najlepiej żeby z góry się umówili który zgaduje. Reszta mówi "nie wiem".
      To daje 50% szansy na uratowanie.

      Gdybym jednak byl tym skazńcem wybranym do losowania, to nie wybieralbym losowo,
      ale stawial bym na ten kolor, którego widzę więcej. Argumentacja jest taka:
      skoro widzę np. 4 czarne i 2 biale, to być może moneta jest jakaś krzywa i
      faworyzuje czarne. Wówczas lepiej postawić na czarne.
    • uller Re: Siedmiu Dezerterów - 75% 19.05.05, 15:47
      Typujemy trzech więzniów. Czterech pozostalych odpowiada zawsze nie wiem.
      Tych trzech wyciaga wnioski tylko na podstawie widzianych kapeluszy na głowach
      dwóch pozostałych wytypowanych więźniów. Jeżeli któryś z nich widzi:
      1 biały i 1 czarny mówi Nie wiem
      2 biale mówi czarny
      2 czarne mówi bialy
      • uller Re: Siedmiu Dezerterów - 78,125% 19.05.05, 16:52
        Uzasadnienie podam jutro gdyz dzisiaj się nie wyrobie. Kluczem jest podzial na
        dwie grupy. Cztero i trzy osobową. I ta trzy osobowa podejmuje pierwszą decyzję
        na podstawie tego co widzi w cztero osobowej grupie.
        • Gość: PM Wniosek z narady IP: *.neoplus.adsl.tpnet.pl 19.05.05, 17:50
          7 rzutów monetą może dać 128 różnych układów orłów i reszek, w tym:
          1 układ - same reszki;
          7 układów -1 orzeł;
          21 ukł. - 2 orły;
          35 ukł. - 3 orły;
          35 ukł. - 4 orły;
          21 ukł. - 5 orłów;
          7 ukl. - 6 orłów;
          `1 ukl. - 7 orłów.
          Każdy z tych układów jest możliwy z prawdopodobieństwem 1/128 i w czasie nocnej
          narady więżniowie mogą się łudzić,że coś wymyślą, ale przy braku kontaktu z
          innymi następnego dnia kazdy może tylko stwierdzić,że z tego co widzi,
          zrealizował sie jeden z dwu ww układów, ale nić z tego nie wynika o kolorze
          jego nakrycia. Dlaczego dwa układy? Widząć np.6 czarnych wie tylko, ze moneta
          6 razy upałdła jednakowo a wynik siódmego rzutu jest mu nieznany i może go
          odgadnąć z prawdopodobieństwem 1/2.Drugi kolega mysli podobnie i wie,ze
          prawdopodobieństwo odgadnięcia też jest 1/2, ale że obaj zgadną - już to
          prawdopodobieństwo jest 1/4.Następni zgadując zmniejszaja to jeszcze bardziej.
          Więżniom pozostaje wylosować reprezentanta i modlić się, by miał szczęscie.
          Pozostali taktownie przyznaja się do niewiedzy.50% mają gwarantowane.
            • kornel-1 Re: Wniosek z narady 19.05.05, 20:29
              Przede wszystkim muszę powiedzieć, że doszedłem do ułamka Pafcia 84/128 :-)

              Moje drugie podejście to:
              -kto widzi 6 jednakowych zgłasza kolor ten sam 2/128
              -kto widzi 5 jednakowych zgłasza kolor przeciwny 42/128
              -kto widzi 4 jednakowe milczy ("nie wiem")
              -kto widzi 3 jednakowe mówi cokolwiek (powiedzmy czarny - co by pod nastrój
              pasował) 35/128

              Szansa, że sknociłem obliczenia jest gigantyczna ale "wyszło" mi 79/128 = 61.72%
              Kornel
        • kornel-1 Re: Siedmiu Dezerterów - 78,125% 19.05.05, 22:29
          75% widzę i się z tym zgadzam 32/128+48/128= 0.75
          ale skąd te 3.125%?

          uller napisał:
          > Uzasadnienie podam jutro gdyz dzisiaj się nie wyrobie. Kluczem jest podzial na
          > dwie grupy. Cztero i trzy osobową. I ta trzy osobowa podejmuje pierwszą
          decyzję
          > na podstawie tego co widzi w cztero osobowej grupie.

          Hm. Ja te 75% mam w oparciu o analizę w obrębie wcześniej wybranych trzech osób
          (czwórka mówi nie wiem a trójka nie musi znać rozkładu w czwórce). W ostatnim
          zdaniu piszesz, że trójka opiera się na tym co widzi w 4-osobowej grupie. Więc
          jak jest?
          Kornel
        • mesquaki Re: Siedmiu Dezerterów - 78,125% 19.05.05, 23:27
          Już chciałam wnieść pomysł racjonalizatorski na rozszerzenie ullerowej
          strategii, ale widzę że nie doczytałam i Uller sam ją rozszerzył. A tak się
          namęczyłam :(.
          Idea ta polega na tym, że dzielimy skazańców na grupę 3- i 4-osobową. Grupa 4-
          osobowa zgaduje na podstawie kapeluszy pozostałych członków grupy wg zasady:
          widzę 0 Białych kapeluszy: mówię Czarny,
          widzę 1 lub 2 B : nie wiem
          widzę 3 C: Biały
          W ten sposób wyniki rozkładają się w stosunku 8:6:2 (prawidłowe
          odgadnięcie:nikt_nic_nie_wie:pomyłka), a pomyłki tu chcemy zminimalizować, jako
          że są nieprzyjemne w skutkach. Nad niewiedzą popracuje grupa 3-osobowa.
          Pozostała, 3-osobowa grupa skazańców interweniuje tylko w wypadku, gdy w 4-
          osobowej nikt nic nie wie, (czyli gdy kolory kapeluszy w 4-osobowej są jak
          1:3), w przeciwnym wypadku milczy. Ich zasady są takie same, jak w pierwszym
          poście Ullera. Sumarycznie jest więc 1/2 + 3/4 * 6/16 =.78125
          m
            • cardemon Re: Siedmiu Dezerterów - 78,125% 20.05.05, 03:31
              Mes, nie mogę się zgodzić z Twoim rozumowaniem. Oczywiście przy rozkładzie 2-2
              odpowiedzi będą "nie wiem", ale przy układzie BBBB każdy jeden z tej czwórki
              odpowie "czarny" (Mes:>miało być na odwrót, oczywiście: widzę 3B: Czarny<), a
              przy czterech układach 3-1 typu BCCC, ten widzący trzy czarne odpowie "czarny"
              (Mes:>widzę 0 Białych kapeluszy: mówię Czarny<). Zatem nie będzie rozkładu 8:6:2
              (prawda:pas:pomyłka) tylko 5:6:5.

              Pozdrawiam, CdM
              • mesquaki Re: Siedmiu Dezerterów - 78,125% 20.05.05, 04:18
                cardemon napisał:

                > Mes, nie mogę się zgodzić z Twoim rozumowaniem. Oczywiście przy rozkładzie 2-2
                > odpowiedzi będą "nie wiem", ale przy układzie BBBB każdy jeden z tej czwórki
                > odpowie "czarny" (Mes:>miało być na odwrót, oczywiście: widzę 3B: Czarny
                > 0;), a
                > przy czterech układach 3-1 typu BCCC, ten widzący trzy czarne odpowie "czarny"
                > (Mes:>widzę 0 Białych kapeluszy: mówię Czarny<). Zatem nie będzie rozkł
                > adu 8:6:2
                > (prawda:pas:pomyłka) tylko 5:6:5.
                Eh, przepraszam, wciąż źle. Powinno być "widzę 0 Białych kapeluszy: mówię
                Biały". Generalnie, skazańcy, którzy widzą skrajne ilości kapeluszy (tu: 0 i 3)
                deklarują kolor przeciwny, pozostali milczą.
                Tak namieszałam, że spróbuję to jeszcze raz opisać, choć nie wiem, czy to coś
                da :).
            • mesquaki Re: Siedmiu Dezerterów - 78,125% 19.05.05, 23:46
              Gość portalu: pafcio napisał(a):

              > > Pozostała, 3-osobowa grupa skazańców interweniuje tylko w wypadku, gdy w
              > 4-
              > > osobowej nikt nic nie wie, (czyli gdy kolory kapeluszy w 4-osobowej są ja
              > k
              > > 1:3)
              >

              > miałas na myśli 2:2, czyli dwa białe i dwa czarne, prawda?
              > pozdrawiam
              > pafcio

              Tak, dzięki, właśnie zamierzałam się poprawić.
              Wyrażnie mi dziś nie idzie czytanie i pisanie :).
          • kornel-1 Re: Siedmiu Dezerterów - 78,125% 20.05.05, 01:37
            mesquaki napisała:

            > Pozostała, 3-osobowa grupa skazańców interweniuje tylko w wypadku, gdy w 4-
            > osobowej nikt nic nie wie, (czyli gdy kolory kapeluszy w 4-osobowej są jak
            > 1:3), w przeciwnym wypadku milczy.

            Hm. Jeśli dobrze zrozumiałem, Cardemon chciał by:

            > Umówmy się, że oddanie głosu przez
            >każdego ze skazańców jest niejawne i
            >wszyscy oddają głos dokładnie w tym samym czasie.

            Czy rozwiązanie 78% spełnia ten wymóg?

            Kornel
              • kopperek Re: Siedmiu Dezerterów - 78,125% 20.05.05, 02:32
                cardemon napisał:

                > kornel-1 napisał:
                >
                > > Czy rozwiązanie 78% spełnia ten wymóg?
                > >
                > > Kornel
                >
                > Niestety rozwiązanie Mesquaki tego wymogu nie spełnia. :(
                > CdM

                ??? Jakto nie spełnia? Przecież jeśli podział w 4-osobowej grupie jest 2:2 (nie
                3:1, jak napisała przez pomyłkę Mes), to ci z grupy trzyosobowej od razu wiedzą,
                że wszyscy z 4-osobowej będą milczeć. Więc w czym problem?
        • uller Re: Siedmiu Dezerterów - 78,125% 20.05.05, 08:10
          Miałem podac dzisiaj rozwiązanie ale zrobil juz to za mnie mesquaki.
          Ale ja pozwole sobię tez na zamieszczenie swojego wcześniej przygotowanego
          objaśnienia.
          Dzielimy dzezerterów na dwie grupy 3 i 4 osobowe. W grupie cztero osobowej
          decyzja podejmowana jest tylko na podstawie widzianych kapeluszy reszty członków
          tej (4 osobowej) grupy i tak kiedy widzą:
          3 czarne - mówia biały
          2 czarne 1 biały mówia nie wiem
          2 białe 1 czarny mówią nie wiem
          3 białe - mówia czarny
          Więżniowie z trzy osobowej grupy tylko wtedy kiedy widza ze w cztero osobowej
          jest rozkład 2białe i 2 czarne wyciaga wnioski na podstawie widzianych kapeluszy
          na głowach dwóch pozostałych więźniów z grupy 3 osobowej. Jeżeli któryś z nich
          widzi:
          1 biały i 1 czarny mówi Nie wiem
          2 biale mówi czarny
          2 czarne mówi bialy
          Kiedy w grupie cztero osobowej jest układ 3-1 (lub 1-3) lub 4-0 (lub 0-4)
          więżniowie z grupy trzy osobowej zawsze mówią nie wiem.
          Kiedy widza układ 3-1 juz się ciesza, a kiedy widzą 4-0 już wiedza że zgineli
          P = 8/16+6/16*6/8 =0,78125.
          Pozdrawiam
          Uller.
          Do zobaczenia jutro we Wrocławiu ;)
    • lapacz_w_zycie Re: Siedmiu Dezerterów 19.05.05, 20:06
      Moja propozycja:
      więźniowie nadają sobie numery
      od 1 do 7. Następnego dnia więzień numer 3
      mówi, że ma czarny kapelusz. Wszyscy inni mówią: 'nie wiem'
      Prawdopodobistwo sukcesu 50%, ale przynajmniej
      algorytm oryginalny.
      A poważnie:
      jestem głęboko przekonany,
      że nic więcej niż 50% nie da się wycisnąć.
      Dowód przez machanie rękami:
      (*) kolor kapelusza na głowie każdego
      z więźniów jest niezależny od koloru
      kapeluszy pozostałych zatem nikt nie może
      wnioskować o kolorze własnego na podstawie
      tego co widzi u innych.
      (**) zgodnie z warunkami zadania po zobaczeniu
      koloru kapeluszy pozostałych nie ma żadnego
      przepływu informacji pomiędzy więźniami,
      zatem każdy wie o kolorze swojego kapelusza
      dokładnie tyle co dzień wcześniej.

      A może jakiś błąd w warunkach zadania?

      lwz
      • Gość: darekw Re: Siedmiu Dezerterów IP: *.neoplus.adsl.tpnet.pl 19.05.05, 22:18
        Panie i panowie... Cały czas drepczemy w miejscu :)
        To, ze 6ciu mówi "nie wiem" a 7dmy zgaduje, z prawdopodobieństwem 50% jest
        oczywiste. Ale po co wtedy zagadka ???
        Musimy sie lepiej postarać (ale na mnie raczej nie liczcie) ... hehe :D

        PS. Przypomina mi się stara zagadka "Auto czy koza?" - gdzie tez zawsze
        wychodziło 50%
      • Gość: pafcio Re: Siedmiu Dezerterów IP: *.aster.pl / *.aster.pl 19.05.05, 22:27
        skoro jesteś niedowiarek;) to proponuję Ci napisanie krótkiego programiku,
        który spełni warunki zadania i zgodnie z wyżej podanymi algorytmami będzie
        sprawdzał, czy więźniowie przeżyją czy nie. jak już to zrobisz to podaj nam
        wynik po dużej ilości prób.

        a teraz na poważnie. nie każdy rozkład kapeluszy ma takie samo
        prawdopodobieństwo. więc wnioskowanie na podstawie tego co się widzi ma sens. a
        co do Twego dowodu, to pierwsza częśc (*) jest prawdziwa, ale już to co jest
        po "zatem" jest przykładem wyciągania złych wniosków.

        pozdrawiam
        pafcio
      • lapacz_w_zycie Re: Siedmiu Dezerterów 19.05.05, 22:39
        > jestem głęboko przekonany,
        > że nic więcej niż 50% nie da się wycisnąć.
        > Dowód przez machanie rękami:

        po raz kolejny przyszło mi boleśnie
        poznać wątpliwą wartość głębokich
        przekonań i dowodów przez machanie rękami.
        Świetna zagadka, myślę nad czymś lepszym niż 84.

        lwz
        • Gość: Kama Re: Siedmiu Dezerterów IP: *.neoplus.adsl.tpnet.pl 19.05.05, 23:30
          Wszelkie propozycje, zeby wszyscy widzacy konkretny układ podawali kolor jest
          beż sensu.Przy rozkładzie 6b+1c pięć osób widzi 5b+1c i wrzeszcząc "mam c"
          naraża wszystkich na śmierć, bo drugiego c już nie ma.Widzący 5b+1c jest tylko
          pewny,że rozkład kapeluszy jest 6b+1c albo 5b+2c, ale jego kapelusz ma
          jednakowe szanse być b jak i c, bo nadal nie wie,co wskazała jego moneta.
          Zagadka jest o tyle ciekawa, że sugeruje jakies tajemnicze możliwości, a
          dopowadza do wniosku - niech zgaduje jeden.
    • cardemon Krótki komentarz nr 2 20.05.05, 02:47
      Oto bieżące rozwiązania niniejszej zagadki (% zaokrąglone do 0.1):

      Uller - strategia "wybranej trójki" - 75% szans na ocalenie (duże brawa, ale
      nadal nie jest to optymalne rozwiązanie)
      Pafcio - strategia "na rozkłady 6-1 i 4-3" - 65.6%
      Kornel - drugie podejście - 61.7% (dobrze policzone, Kornel)
      Kornel z poprawką Andy'ego i Kama - strategia "na rozkład 4-3" - 54.7%

      No i oczywiście rozwiązania z arbitralnie wybranym jednym zgadującym, które
      zawsze dają 50% prawdopodobieństwo uratowania się skazańców.

      Na koniec kilka moich przemyśleń odnośnie samej zagadki. Przede wszystkim muszę
      powiedzieć, że jest ona wyjątkowo perfidna i z piekła rodem. :)
      Jest w niej nawet coś transcendentalnego, coś co "sugeruje jakies tajemnicze
      możliwości" (słowa Kamy). Paradoksalnie też zaprzecza zdrowemu rozsądkowi, jaki
      wyraża PM ("50% mają gwarantowane") i Łapacz_w_życie ("jestem głęboko
      przekonany, że nic więcej niż 50% nie da się wycisnąć"). Otóż da się wycisnąć
      więcej niż 50%, a nawet więcej niż 75%...

      Na pewno w końcowym podsumowaniu napiszę wszystko, co wiem o tej zagadce, ale na
      razie jeszcze na to za wcześnie. Póki co nie chcę też niczego sugerować, ani
      podpowiadać, raczej życzę wszystkim owocnych zmagań z tym wyjątkowo trudnym
      zadaniem.

      CdM
    • mesquaki Re: Siedmiu Dezerterów - 0.78125 jeszcze raz 20.05.05, 05:33
      Podejście drugie, po polowaniu na błędy.
      Dzielimy skazańców na grupy 3- i 4-osobową.
      Grupa 4-osobowa zgaduje na podstawie kapeluszy pozostałych członków swojej
      grupy wg zasady:

      widzę 0 Białych kapeluszy: mówię Biały,
      widzę 1 B : nie wiem
      widzę 2 B: nie wiem
      widzę 3 B: Czarny

      Czyli skazańcy widzący wszystkie 3 pozostałe kapelusze w jednym kolorze,
      deklarują kolor przeciwny, ci, którzy widzą mieszane kolory, milczą.
      Deklaracje w tej grupie będą takie:
      CCCC (1 kombinacja) , wszyscy deklarują B, pomyłka
      BCCC (4) B:deklaruje B, C: nie wiedzą, sukces
      BBCC (6) B: nie wiedzą, C: nie wiedzą
      BBBC (4) B: nie wiedzą, C: deklaruje C, sukces
      BBBB (1) wszyscy deklarują C, pomyłka
      W ten sposób wyniki rozkładają się w stosunku 8:6:2 (prawidłowe
      odgadnięcie:nikt_nic_nie_wie:pomyłka), a pomyłki tu chcemy zminimalizować, jako
      że są nieprzyjemne w skutkach. Nad niewiedzą popracuje grupa 3-osobowa.
      Pozostała, 3-osobowa grupa skazańców, interweniuje tylko w wypadku, gdy w 4-
      osobowej nikt nic nie wie, (czyli gdy w grupie 4-osobowej są 2 B i 2 C
      kapelusze), w przeciwnym wypadku milczy. Ich zasady są takie same, jak w
      pierwszym poście Ullera. Sumarycznie jest więc 8/16 + 3/4 * 6/16 =.78125
      To powyższe zasymulowałam i zdaje się działać jak trzeba.

      Do Kornela:
      Każdy z grupy 3-osobowej widzi, czy grupa 4 –osobowa ma 2B i 2 C kapelusze, czy
      też inną ich kombinację. Może więc podjąć decyzję indywidualnie i
      natychmiastowo, czy głosować według kolorów kapeluszy w swojej grupie, czy
      milczeć. Wszyscy głosują równocześnie. Warunki zadania są tutaj spełnione.


      Wydaje mi się też, że taki sam wynik można uzyskać, jeśli podzieli się
      skazańców na 5 i 2 osobową grupę.
      Ci z piątki głosują analogicznie jak czwórkowcy (skazańcy widzący wszystkie 4
      pozostałe kapelusze w jednym kolorze, deklarują kolor przeciwny, ci, którzy
      widzą mieszane kolory, milczą).

      CCCCC (1 kombinacja) , wszyscy deklarują B, pomyłka
      BCCCC (5) B:deklaruje B, C: nie wiedzą, sukces
      BBCCC (10) B: nie wiedzą, C: nie wiedzą
      BBBCC (10) B: nie wiedzą, C: nie wiedzą
      BBBBC (5) B: nie wiedzą, C: deklaruje C, sukces
      CCCCC (1) wszyscy deklarują C, pomyłka

      I tu następuje zmyłka: więzień z grupy 5-osobowej, który stwierdzi wokół siebie
      2C i 2 B kapelusze, zamiast milczeć, głosuje razem z więźniami z 2-ki według
      zasad 3-grupowych.
      Tak naprawdę będzie 3 takich więźniów: 3B z piątki 3B2C lub 3C z piątki 2B3C,
      ale to nie ma znaczenia, jako że wszyscy mają taki sam kolor kapelusza, taką
      samą informację i głosują jednakowo.
      Grupa 2-osobowa jest w stanie zidentyfikować kolor kapelusza tego więźnia, (B
      jeśli 3B2C, C jeśli 2B3C).
      Jeśli rozkład w 5-tce jest inny niż 2B3C/3B2C, skazańcy z 2-ki deklarują
      niewiedzę.
      Wychodzi mi z tego 10/32 + 3/4 * 20/32=.78125
      Aczkolwiek głowy za to nie dam. Ani niczego innego.
      I tak naprawdę, nie ma potrzeby się w takie wikłania zagłębiać :)
      Tak czy owak, miło się nad czemś znów pogłowić.
      pozdrawiam
      m
      • Gość: PM Re: Siedmiu Dezerterów - 0.78125 jeszcze raz IP: *.neoplus.adsl.tpnet.pl 20.05.05, 13:00
        Wyobaźcie sobie taka sytuację:5 osób obserwuje wynik pięciu rzutów monetą.
        Rzucono już cztery razy i wszyscy znaja wyniki kolejnyxh rzutów.Z jakim
        prawdopodobieństwem kazdy z obserwatorów odgadnie wynik piątego rzutu?
        Oczywiscie, niezależnie od tego, co zobaczył,wynik jest zależny tylko od
        piątego rzutu i prawd. zgadnięcia jest 1/2 dla kazdego z nich.Jesli dwaj
        mieliby obowiązek zgadywać - prawd. byłoby już 1/4, jesli trzech - 1/8
        itd.Najwsiększe więc prawdopodobieństwo jest , kiedy zgadyje tylko jeden. Przy
        dowolnej liczbie rzutów wynik ostatniego rzutu jest tak samo prawdopodobny.
        Układ barw kapeluszy odpowiada dokładnie układowi orłów i reszek i kazdy widząć
        kolegów może czuc sie tak, jakby czekał na ostatni rzut monetą i miał odgadnąc
        wynik. Należy zwrócic uwagę,że wprowadzanie nawet dwóch zgadujących zwiększa
        prawdopodobieństwo błędu.(Przy jednoczesnych zdarzeniach prawdopodobieństwa
        mnożymy, a kazde z nich jest mniejsze niż 1, więc iloczyn jest mniejszy niz
        kazde z osobna)
        Autor zadania , mówiąc,ze zna wynik wyższy niż 50%, na pewno sie myli.
        • Gość: Uważny Re: Siedmiu Dezerterów - 0.78125 jeszcze raz IP: *.neoplus.adsl.tpnet.pl 20.05.05, 13:27
          Pomysł zagadki świetny i podanie warunków sugeruje,że można znalęźć metodę
          skutecznego ratowania skazanych.Isotne wniosek z powyższych rozważań jest
          następująćy. Jesli poszczególny więżień ma sznsę zgadnąć z prawdop. a, zas inny
          z prawdop. b, to nie powinni głosować jednocześnie, bo wtedy prawdop. jest ab<a
          i ab<b - powinien głosować tylko jeden.Rozważania Kamy i ostatnie PM wyrażnie
          wykazują,że bariera 1/2 jest nie do przekroczenia (przy podanych twardych
          warunkach, kiedy nikt nie wie, co widzzi inny).
        • kopperek Re: Siedmiu Dezerterów - 0.78125 jeszcze raz 20.05.05, 13:28
          A jednak nie. Najłatwiej pozbyć się tego wrażenia rozważając pierwotny algorytm
          ullera dla trzech osób (zamieszczony teżw powyższym poście Mesquaki). Jest osiem
          możliwych układów kolorów. I o ile wartość oczekiwana ILOŚCI błędnych odpowiedzi
          i ILOŚCI prawidłowych odpowiedzi JEST taka sama i wynosi 0.75, to rzecz w tym,
          że przypadki złych odpowiedzi są skanalizowane w dwóch przypadkach (wszystkie
          białe, wszystkie czarne) - wtedy kłamią wszyscy trzej - i o to chodzi! Natomiast
          odpowiedzi prawidłowe padają w sześciu pozostałych przypadkach i wtedy
          odpowiedzi udziela tylko jeden z nich. Gdyby gra polegała na tym, że każda dobra
          odpowiedź daje punkt, a każda zła powoduje utratę punktu, to faktycznie wartość
          oczekiwana wygranej wyniosłaby zero - ale warunki zadania są inne.

          pzdr.
        • lapacz_w_zycie Re: Siedmiu Dezerterów - 0.78125 jeszcze raz 20.05.05, 14:22
          >Autor zadania , mówiąc,ze zna wynik wyższy niż 50%, na pewno sie myli.
          Też byłem tego całkowicie pewien.
          Właśnie dlatego to zadanie jest takie dobre.
          Aż zazdroszczę Ci że iluminacja - moment zrozumienia
          jest jeszcze przed Tobą. Bądź gotów na tę chwilę.
          Zadanie pierwszoligowe, klasy dylematu Monty Hall.
          Dzięki CMD.

          lwz
        • Gość: pafcio Re: Siedmiu Dezerterów - 0.78125 jeszcze raz IP: *.aster.pl / *.aster.pl 20.05.05, 16:36
          błąd w rozumowaniu Twoim jest w momencie porównania wyniku piątego rzutu z tym,
          że mamy już zrobione 5 rzutów i nie zgadujemy 5 wyniku (żadnego konkretnego, bo
          to jak wcześniej było wspomniane daje 50%), ale zależnei od strategii wynik
          jest zgadywany przy 1, 2, 3, 4 albo 5 rzucie na podstawie rozkładu.

          jeżeli będę w kasynie i zobaczę że 2 razy wypadło czerwone pod rząd to nie
          zaryzykuję czarnego tylko dlatego, ze jest większe prawdopodobieńśtwo bo nie
          jest.
          ale jeśli jest nas trzech i mamy na głowie kapelusz w jednym z kolorów losowo
          wybranych z prawdopodobieństwem 50% to Ci co widzą 2 kapelusze tego samego
          koloru mają dużą szansę zgadnąć swój kolor - a różnica jest taka, że nie
          wiadomo którzy to są (nie dwóch konkretnych, ale w zależności od sytuacji dwóch
          z nich trzech - lub trzech jeżlei akurat przy rozkłądzie 3,0 się mylą. więc
          bedąc tym który widzi 2 kapelusze w tym samym kolorze zagrałbym, ale już jakby
          na mnie trafiło że widzę 1 plus 1 to nie.

          nie wiem jak to lepiej wytłumaczyć

          pozdrawiam
          pafcio
    • Gość: kama Re: Siedmiu Dezerterów IP: *.neoplus.adsl.tpnet.pl 20.05.05, 18:52
      Pafcio! Fantazjujesz! Przykład z kasynem dwa czerwone i nie wiadomo co w
      trzecim jest dokładnie taki sam,jak dwa białe kapeluszę u sąsiadów.
      Zaden z nich nie wie dokładnie, co widzą pozostali, a na temat swego kopelusza
      również nie wie nic.Wszystkojedno czy widzi bb, bc, czy też cc, czy cb(jesli
      patrzy od lewej doprawej) w dalszym ciągu jest taki sam głupi jak gdyby mic
      nie widział.Dokładnie jek trzeci wynik w kasynie. Nie kombinuj, bo sprawa jest
      jasna - nić z obserwacji nie wynika na temat swego nakrycia głowy.Jesli jesteś
      telepatą - to już co innego!


      • kopperek Re: Siedmiu Dezerterów 20.05.05, 19:09
        Gość portalu: kama napisał(a):

        > Pafcio! Fantazjujesz! Przykład z kasynem dwa czerwone i nie wiadomo co w
        > trzecim jest dokładnie taki sam,jak dwa białe kapeluszę u sąsiadów.
        > Zaden z nich nie wie dokładnie, co widzą pozostali, a na temat swego kopelusza
        >
        > również nie wie nic.Wszystkojedno czy widzi bb, bc, czy też cc, czy cb(jesli
        > patrzy od lewej doprawej) w dalszym ciągu jest taki sam głupi jak gdyby mic
        > nie widział.Dokładnie jek trzeci wynik w kasynie. Nie kombinuj, bo sprawa jest
        > jasna - nić z obserwacji nie wynika na temat swego nakrycia głowy.Jesli jesteś
        > telepatą - to już co innego!
        >

        Heh, zagadka budzi emocje:). Kama, poświęć dosłownie chwilę czasu i rozpisz
        sobie algorytm ullera dla grupy trzech osób. Dwie minuty i wszystko będzie jasne
        - w sześciu przypadkach na osiem odzywa się tylko jeden z nich i mówi prawdę, w
        dwóch pozostałych przypadkach zgadują wszyscy i wszyscy popełniają błąd.
      • Gość: pafcio Re: Siedmiu Dezerterów IP: *.aster.pl / *.aster.pl 20.05.05, 19:34
        > Pafcio! Fantazjujesz! Przykład z kasynem dwa czerwone i nie wiadomo co w
        > trzecim jest dokładnie taki sam,jak dwa białe kapeluszę u sąsiadów.
        tak, ale pod warunkiem, ze to Ty grasz jako jedyny zawodnik i widzisz te 2
        białe kapelusze, czyli z Twojej pozycji. w zagadce jest mowa nie o Tobie, ale o
        Tobie i innych myślących w miarę zawodnikach, którzy postępując zgodnie z
        algorytmem osiągają wspomniane rezultaty.
      • mesquaki Re: Siedmiu Dezerterów 20.05.05, 21:10
        Co prawda Kopperek z Pafciem wszystko już napisali, no i lepiej jest raz samemu
        przeanalizować niż 10 razy przeczytać, ale spróbujmy:
        Jest 8 możliwych układów kolorów kapeluszy w trójkach. Każdy z nich jest
        jednakowo prawdopodobny. Skazańcy (KAŻDY z trójki) głosują według reguły :
        widzę dwa takie same kolory: głosuję na przeciwny, widzę dwa różne: milczę.
        Wygląda to tak:
        (1 kolumna - kolory kapeluszy na głowach 3 więźniów;
        2 kolumna - deklaracje tych 3 więźniów;
        3 kolumna - wynik całościowy dla trójki)

        1_BBB__CCC__rozstrzelanie
        2_BBC__??C__wolność
        3_BCB__?C?__wolność
        4_BCC__B??__wolność
        5_CBB__C??__wolność
        6_CBC__?B?__wolność
        7_CCB__??B__wolność
        8_CCC__BBB__rozstrzelanie

        W tych 8 możliwych przypadkach, każdy ze skazańców 4 razy milczał, a z
        pozostałych 4 strzałów połowę zgadł, a połowę nie. Tak się jednak szczęśliwie
        składa, że każdy z nich pomyli się w tych samych dwóch przypadkach: gdy wszyscy
        mają kapelusze tego samego koloru. Na pozostałe 6 z 8 rozkładów przypadają
        tylko prawidłowe odpowiedzi i "nie wiem". Tak więc na 75% cała ta przykra
        sprawa powinna zakończyć się sukcesem, prawda?
        m
        • Gość: nowy Re: Siedmiu Dezerterów IP: *.neoplus.adsl.tpnet.pl 20.05.05, 22:18
          Twoje rozumowanie jest poprawne w tym sensie,ze bardziej jest prawdopodobny
          układ 2+1 niż 3 , ale po przeprowadzeniu rozdania jest już komkretny jeden
          układ i przestaje nas interesować jakie było jego prawdopodobieństwo, czy
          powstał przez rzut monetą, czy przez widzimisie strażnika. Facet widzi przed
          soba dwa białe kapelusze i wtedy wie,że zaszła jedna z dwu możliwości:
          wylosowano albo trzy białe albo 2 białe i czarny. Z tego nie wynika o jego
          kapeluszu. Wie tylko,ze nie wylosowano trzech jednakowych, jesli widzi rózne, a
          jesli widzi dwa jednakowe, wie ,ze nie wylosowano trzech przeciwnego koloru.To
          jego cała wiedza.
          Przedstawiony pomysł mówi tylko,ze gdyby powtarzano losowo próby wielokrotnie
          przy róznych rozdaniach, to czesciej wystapiłby układ 2+1 niż inne
          • Gość: darekw Re: Siedmiu Dezerterów IP: *.neoplus.adsl.tpnet.pl 20.05.05, 22:31
            Zagadka iscie diabelska ... niesamowita!!! Uważnie śledzę dyskysje.
            Przelamuje stereotypy myslenia. To faktycznie zwielokrotniony "Monty Hall"
            Tak samo wydaje się \, że nie mozna przekroczyć 50%
            Kluczowy jest podział na grupy i różne rozklady prawdopodobieństawa.
            (tak jak w brydżu - jak rozkładają się brakujace atuty)
            Niestety trzeba się orientować w matmie i racuvnku "prawdopodobieństw
            warunkowych" - nie wiem czy to tak sie nazywa :) ale tak mi pasuje.

            Kamień milowy wśród zagadek.
          • kopperek Re: Siedmiu Dezerterów 20.05.05, 22:49
            Gość portalu: nowy napisał(a):

            > Twoje rozumowanie jest poprawne w tym sensie,ze bardziej jest prawdopodobny
            > układ 2+1 niż 3 , ale po przeprowadzeniu rozdania jest już komkretny jeden
            > układ i przestaje nas interesować jakie było jego prawdopodobieństwo, czy
            > powstał przez rzut monetą, czy przez widzimisie strażnika. Facet widzi przed
            > soba dwa białe kapelusze i wtedy wie,że zaszła jedna z dwu możliwości:
            > wylosowano albo trzy białe albo 2 białe i czarny. Z tego nie wynika o jego
            > kapeluszu. Wie tylko,ze nie wylosowano trzech jednakowych, jesli widzi rózne, a
            >
            > jesli widzi dwa jednakowe, wie ,ze nie wylosowano trzech przeciwnego koloru.To
            > jego cała wiedza.

            Oczywiście. I z tego wynika, że jeśli ten konkretny facet będzie zgadywał -
            podając kolor inny niż te dwa jego towarzyszy, bo tak ustalili - to
            prawdopodobieństwo trafienia wynosi dokładnie 50%. Mimo tego prawdopodobieństwo
            sukcesu całej grupy wynosi 75%:)), bo facet będzie zgadywał tylko w połowie
            przypadków! W pozostałych - zgadywać będą towarzysze (zawsze jeden z nich), i
            tak się miło składa, że wtedy na pewno trafią. Natomiast NIE trafią dokładnie w
            tych samych przypadkach, co nasz bohater. Czyli w dwóch konfiguracjach na osiem.
            O tej zaagadce można opowiadać godzinami:D.

            > Przedstawiony pomysł mówi tylko,ze gdyby powtarzano losowo próby wielokrotnie
            > przy róznych rozdaniach, to czesciej wystapiłby układ 2+1 niż inne

            Czyli PRZED losowaniem prawdopodobieństwo takiego układu można oszacować -
            wynosi 75%. Jeśli w tych wypadkach algorytm daje sukces, to przed losowaniem
            szanse sukcesu wynoszą 75%.
            • Gość: nowy+ Re: Siedmiu Dezerterów IP: *.neoplus.adsl.tpnet.pl 21.05.05, 00:00
              Mylicie dwie różne rzeczy.Prawdopodobieństwo rozkładu 2+1 jest rzeczywiście
              75%, ale na to się składa BBC,BCB,CBB, CCB,CBC,BCC .Prawdopodobieństwo
              komkretnego układu np.BBC jest 1/8, a tylko z jednym, konkretnym mamy do
              czynienia po rozdziale kapeluszy i konkretnie jeden sie na ten temat wypowie.

              To że wprowadzono tu rzuty moneta nie ma zadnego znaczenia, jesli seria rzutów
              była tylko jeden raz.Przy wielu seriach najczęsciej wystapi 3+1, ale przy
              jednej kazdy wynik jest jednakowo mozliwy.
              • kopperek Re: Siedmiu Dezerterów 21.05.05, 00:59
                Gość portalu: nowy+ napisał(a):

                > Mylicie dwie różne rzeczy.Prawdopodobieństwo rozkładu 2+1 jest rzeczywiście
                > 75%, ale na to się składa BBC,BCB,CBB, CCB,CBC,BCC .Prawdopodobieństwo
                > komkretnego układu np.BBC jest 1/8, a tylko z jednym, konkretnym mamy do
                > czynienia po rozdziale kapeluszy i konkretnie jeden sie na ten temat wypowie.
                >
                > To że wprowadzono tu rzuty moneta nie ma zadnego znaczenia, jesli seria rzutów
                > była tylko jeden raz.Przy wielu seriach najczęsciej wystapi 3+1, ale przy
                > jednej kazdy wynik jest jednakowo mozliwy.

                Kręcimy się w kółko. Mam wrażenie, że ciągle rozpatrujesz problem "jestem jednym
                z więźniów i mam zgadywać" - to jest prawdopodobieństwo warunkowe, oparte na
                pewnych założeniach. Tak sformułowane prawd. wynosi faktycznie 50%. Tyle że to
                zbytnie uproszczenie problemu.
                Proponuję - wróć do postu Mesquaki. Najlepiej rozrysuj sobie tabelkę sam. Osiem
                możliwych konfiguracji, każda jednakowo prawdopodobna; dla sześciu z nich
                pewność sukcesu, dla dwóch porażka. O czym my właściwie dyskutujemy? Wszystko co
                napisaliśmy poniżej tamtego postu to bicie piany.

                pzdr.
                • Gość: nowy + Re: Siedmiu Dezerterów IP: *.neoplus.adsl.tpnet.pl 21.05.05, 01:36
                  Oczywiście,ze czuje sie jako jeden ze zgadujących, bo od tego zalezy moje życie
                  i innych. I takpowinien mysleć kazdy z więźniów Tu nie ma prawdopodobieństywa
                  warunkowego. Zgadywanie jest po fakcie - widze taki a taki układ, który juz
                  jest, a nie będzie. Rzeczywiście -jest to bicie piany, bo częśc z
                  rozwiązyjących wierzy w czary.
                  • kopperek Re: Siedmiu Dezerterów 21.05.05, 15:22
                    Gość portalu: nowy + napisał(a):

                    > Oczywiście,ze czuje sie jako jeden ze zgadujących, bo od tego zalezy moje życie
                    >
                    > i innych. I takpowinien mysleć kazdy z więźniów Tu nie ma prawdopodobieństywa
                    > warunkowego.

                    Jest. Analizujesz tylko sytuację, gdy w ogóle podejmujesz próbę odgadnięcia, a
                    algorytm nakazuje Ci powiedzieć "nie wiem", gdy widzisz różne kapelusze.
                    Ignorujesz ten aspekt.

                    Zgadywanie jest po fakcie - widze taki a taki układ, który juz
                    > jest, a nie będzie.

                    Tak. I albo zgadujesz, i masz wtedy 50% szans na sukces - choć właśnie mówienie
                    o prawdopodobieńśtwie w momencie gdy jest już po losowaniu może budzić
                    wątpliwości - albo nic nie robisz i wtedy zgadują inni. I tak zdeiniowane prawd.
                    warunkowe - jaka jest szansa, że ten zgadujący trafi, jeśli ja widzę dwa różne
                    kapelusze - wynosi dokładnie 100%.
    • cardemon Krótki komentarz nr 3 21.05.05, 01:54
      Wiadomość dobra: Brawa dla Ullera i Mes, którzy znaleźli rozwiązanie dające
      78.1% szans na uratowanie się więźniów.
      Wiadomość zła: Nie jest to optymalna strategia.

      Teraz moje uwagi na gorąco.
      Po pierwsze wycofuję się z wszelkich zastrzeżeń co do rozwiązania Mes. Wszystko
      się w jej strategii zgadza, a na dodatek pięknie rozpisała (mesquaki
      20.05.2005 21:10) wariant zagadki dla 3 więźniów.
      Po drugie wyrażam słowa uznania dla Kopperka, którego analizy trafiają w samo
      sedno problemu.
      Po trzecie składam podziękowania Kopperkowi i Pafciowi, którzy cierpliwie
      tłumaczą, choć może to brzmi dla niektórych forumowiczów paradoksalnie, że
      skazańcy mają większą szansę niż 50% na uratowanie życia.
      Po czwarte choć nadal nie udzielam żadnych podpowiedzi, to pozwolę sobie
      napomknąć, że optymalne rozwiązanie jest jak struktura krystaliczna, idealna w
      swej symetrii i tak doskonała, że usunięcie jednego atomu niszczy całą konstrukcję.

      No cóż, "o tej zagadce można opowiadać godzinami" (Kopperek). :)

      CdM
      • Gość: GrzesiekII Re: Krótki komentarz nr 3 IP: *.neoplus.adsl.tpnet.pl 21.05.05, 03:45
        Przestań już komentować, bo nic nowego tu nie będzie. Jeżeli masz uzasadnienie
        wiekszego prawdopodobieństwa niż 50% -podaj je, proszę.Jestem przekonany,ze
        jest to niemożliwe - całe zamieszanie jest przez te monete, którą, niesstety,
        rzucamy tylkojedna serię kolejno 7 razy i jeżeli kazdy rzut jest przypisany
        konkretnemu więźniowi, to niema co rozprawiać,że jeden rozkład jest bardziej
        prawdopodobny miż inny.Wyobraźmy sobie,że więźniowie po ciemku zakładają
        kapelusze i zgadywanie nastepuje po zapaleniu światła. Efekt końcowy jest taki
        sam,jak przy rzucie monetą,a cała wstępna spekulacja odpada.
      • mesquaki Re: Krótki komentarz nr 3 21.05.05, 18:46
        cardemon napisał:

        > optymalne rozwiązanie jest jak struktura krystaliczna, idealna w
        > swej symetrii i tak doskonała, że usunięcie jednego atomu niszczy całą
        > konstrukcję.

        Jezu....
        Ani chybi potrzebujemy kogoś z rentgenem w oczach :).

        Tak właściwie, to całkiem istotna podpowiedź.
        Do tego podejrzewam, że Cardemonowe rozwiązanie może się dość mocno różnić
        koncepcyjnie od naszego.
        m
        • kopperek Re: Krótki komentarz nr 3 21.05.05, 21:28
          mesquaki napisała:

          > Do tego podejrzewam, że Cardemonowe rozwiązanie może się dość mocno różnić
          > koncepcyjnie od naszego.
          > m

          Tak czy inaczej mam nadzieję, że Cardemon da nam jeszcze czas przynajmniej do
          końca weekendu:). Chociaż zaczynam już wątpić, czy coś mądrzejszego wymyślę.
      • kopperek Re: Krótki komentarz nr 3 23.05.05, 00:45
        > Po czwarte choć nadal nie udzielam żadnych podpowiedzi, to pozwolę sobie
        > napomknąć, że optymalne rozwiązanie jest jak struktura krystaliczna, idealna w
        > swej symetrii i tak doskonała, że usunięcie jednego atomu niszczy całą konstruk
        > cję.

        No właśnie... Próbowałem znaleźć jakiś sensowny algorytm symetryczny. I oto do
        czego doszedłem:
        1) Poprzez algorytm symetryczny rozumiem taki, w którym każdy uczestnik
        realizuje ten sam schemat, chociaż dla każdego "sygnał wejściowy" jest inny -
        kolory kapeluszy pozostałych. Nie ma żadnego podziału na grupy, ustawiania w
        kolejności itd. Nie ma zatem analizowania "co widzą inni"!
        2) Zakładam, że schemat dla każdego z nich jest jednoznaczny, tzn. nie ma w nim
        elementu losowości. Przy określonej liczbie widzianych białych/czarnych
        kapeluszy możliwa jest tylko jedna odpowiedź (bialy/czarny/nie wiem).
        3) Myślę że użyteczne będzie wprowadzenie trzech pojęć - analigocznie jak w
        fizyce - czyli stanu "makro" i stanu "mikro" oraz "entropii". Stan mikro to
        określona konfiguracja kapeluszy na głowach kolejnych więźniów (np. BCCBCBB).
        Takich stanów jest 128. Stan "makro" określa całkowitą ilość czarnych i białych
        kapeluszy i może przyjmować jedną z ośmiu wartości (od 0 białych do 7 białych).
        Każdemu stanowi makro przypisujemy określoną entropię, czyli ilość stanów mikro,
        które mu odpowiadają: dla przykładu stan makro "1 biały" jest realizowany przez
        7 stanów mikro, a więc entropia dla stanu "1B/6C" wynosi 7.
        4) Wartości entropii dla kolejnych stanów makro:
        0 Białych -> 1
        1B -> 7
        2B -> 21
        3B -> 35
        4B -> 35
        5B -> 21
        6B -> 7
        7B -> 1
        Oczywiste jest, że algorytm musi dawać sukces szczególnie dla stanów o dużej
        entropii. W szczególności musi dawać pewność sukcesu dla stanów 3B i 4B, bo
        jeśli będzie dawał fałszywy wynik dla przynajmniej jednego z tych stanów, to
        całkowite prawdopodobieńśtwo sukcesu będzie nmiejsze niż 75% (35/128 to więcej
        niż 1/4), a więc algorytm będzie nieoptymalny.
        5) A szukamy algorytmu optymalnego:D.
        6) Zatem sukces dla układów 3B i 4B przyjmujemy za punkt wyjścia. W obu tych
        przypadkach 4 więźniów widzi układ "3B/3C", a trzech widzi układ "2/4". Łatwo
        zauważyć, że ci, którzy widzą "3/3" muszą siedzieć cicho: w przeciwnym wypadku
        wymóg symetrii oznacza, że wszyscy musieliby powiedzieć to samo. Gdyby to była
        odpowiedź "biały", algorytm taki dawałby przegraną dla układu "3B/4C", a jeśli
        tą odpowiedzią byłoby "czarny", to porażka nastąpiłaby dla układu "4B/3C".
        7) Zatem układ typu "3 plus 4" musi być odgadywany przez tych, którzy widzą na
        głowach pozostałych konfigurację "4 plus 2". Czyli: widzę dwa białe mówię biały,
        widzę dwa czarne mówię czarny.
        8) Algorytm zbudowany wg uwag z punktów 6) i 7) daje pewność sukcesu dla układów
        typu "4 plus 3", niestety jednak daje on pewność porażki dla układów typu "2
        plus 5": część z więźniów (dokładnie pięciu) widzi układ "2 plus 4" i zgodnie z
        poprzednimi wnioskami (patrz 6 i 7) będzia odgadywała, że ma na głowie kapelszu
        w tym kolorze który widzi na głowiach dwóch towarzyszy. A to oznacza klęskę.
        9) Porażka dla stanów "2B/5C" i "5B/2C" oznacza, że całkowite prawd. sukcesu
        jest nie większe niż (128-2*21)/128=41/64, a więc dużo mniej niż 75%. Nawet
        jeśli stany "1 plus 6" i "0 plus 7" dało się poprawnie "rozkodować" (nie ma
        sensu sprawdzać czy jest to możliwe).
        10) I to właściwe by było na tyle. Można te rozważania traktować jako próbę
        dowodu, z jasno nakreślonymi założeniami i klarownym, mam nadzieję,
        wnioskowaniem. Wniosek końcowy ewidentnie nie zgadza się z tym co mówi Cardemon,
        więc proszę o komentarz, gdzie tkwi błąd: czy inaczej rozumiemy pojęcie
        "symetryczności" algorytmu? Być może po prostu błąd jest we wnioskowaniu, ale ja
        go nie widzę.
        11) Boli mnie głowa.
        12) Cardemonie, chyba już pora żebyś nas trochę naprowadził:).

        pozdrawiam kopperek
          • Gość: kminnek Re: Krótki komentarz nr 3 IP: *.neoplus.adsl.tpnet.pl 23.05.05, 01:36
            Kopperku!Nie komplikuj prostego zadania z prawdopodobieństwa i nie wyprowadzaj
            do akcji ciezkich dział z entropią włącznie.Cardemon snuje mistyczne sugestie o
            kryształowej strukturze itd.Wersja tego zadania z pięcioma zainteresowanymi
            jest w ksiązeczce"Konbinatoryka, prawdopodobieństwo i zdrowy rozsądek"
            Zakrzewskiego i Żaka.Ta symetria rozwiązan polega na tym,że kazdy ma jednakowe
            prawdopodobieństwo odgadnięcia - 1/2. Każdy ma taką szanse, pod warunkiem, że
            inny mu nie przeszkodzi mówiac coś innego.
        • mesquaki Re: Krótki komentarz nr 3 23.05.05, 03:30
          kopperek napisał:

          > 1) Poprzez algorytm symetryczny rozumiem taki, w którym każdy uczestnik
          > realizuje ten sam schemat, chociaż dla każdego "sygnał wejściowy" jest inny -
          > kolory kapeluszy pozostałych. Nie ma żadnego podziału na grupy, ustawiania w
          > kolejności itd. Nie ma zatem analizowania "co widzą inni"!

          Ciekawe, ja raczej widziałam tę symetrię w kolorach. To znaczy, algorytm byłby
          taki sam (antysymetryczny?) dla skazańców widzących xByC i yBxC. W związku z
          tym dzieliłam na grupy, zagnieżdżałam w grupach, ustawiałam w trójkąty i
          kóleczka ile wlezie.
          Aktualnie jestem na etapie zagnieżdżania piątek w siódemkach, a w piątkach
          trójek :).
          Bo jednolite algorytm algorytmy dla wszystkich, bez podziału na grupy, już
          chyba wyeksploatowaliśmy?

          pozdrawiam
          m
    • Gość: grzesiek Re: Siedmiu Dezerterów IP: *.cbk.waw.pl / *.cbk.waw.pl 21.05.05, 13:15
      Wreszcie i ja doznalem wspomnianego "olśnienia", czyli że zrozumialem że jest
      możliwe lepsze rozwiązanie niż 50%. Podziwiam tych którzy na to wpadli, mimo
      "oczywistych" dowodów (choćby moich) że jest to niemożliwe.
      Pomogla mi analiza rozwiązania z 4 osobową grupą glówną i 3 osobowa grupą
      interwencyjną. Jak juz to zrozumialem, to pokusilem się o wlasne rozwiązanie:

      Siedmiu dezerterów nazywam A,B,...,G i określam cztery grupy 4 osobowe i jedną
      3 osobową:
      1) A,B,C,D
      2) B,C,D,E
      3) C,D,E,F
      4) D,E,F,G
      5) A,B,C
      Dalej podobnie jak u Ullera - jeśli w pierwszej czwórce są warunki do zgadywania
      to pozostali siedzą cicho, jeśli nie to może w drugiej, itd. Jeśli w żadnej
      czwórce nie ma warunków to zgaduje trójka interwencyjna.

      Przez warunki do zgadywania w czwórce rozumiem to że nie ma rozkladu
      2 biale + 2 czarne.
      A jeśli są warunki to ten kto widzi trzy takie same losuje przeciwny.

      Losowanie w trójce: ten kto widzi dwa takie same losuje przeciwny.

      Ta strategia daje sukces w 112 ze 128 wszystkich możliwych rozkladów
      kapeluszy, czyli 87.5%.

      • Gość: grzesiek Re: Siedmiu Dezerterów IP: *.cbk.waw.pl / *.cbk.waw.pl 21.05.05, 13:43
        Niestety muszę odwolać swoje rozwiązanie, chociaż nie wycofuję się z opinii
        że > 50% jest możliwe (np. rozwiązanie z grupami 4+3 jest OK).

        Bląd znalazlem rozpatrując rozklad:

        ABCDE..
        bbccc..

        W tej sytuacj B powinien zgadywać w ramach drugiej czwórki, ale niestety
        B nie wie czy w pierwszej czwórce są warunki do zgadywania, a zatem nie wie
        czy w ogóle druga czwórka ma prawo zgadywać.
        • Gość: pewny Po zastanowieniu się IP: *.neoplus.adsl.tpnet.pl 21.05.05, 17:16
          Więźniowie sa ponumerowani numerami 1, 2, 3. Strażmik rzuca monetę i zakłada
          pierwszemu biały kapelusz, drugie losowamie -też bialy kapelusz - trzeci
          więzień czeka na swoje nakrycie głowy, wierzxąc po przekonywującyxh
          rozmowaćh,ze ani chybi wyoadnie mu czarny, ale strażnik z takim samym
          prawdopodobięństwem może wyrzucic znowu biały, nie czując zadnych zobowiązań
          wobec deliberacji,że układ 2+1 występuje częsciej, niz inne. Układ trzech
          białych jest tak samo prawdopodobny jak BBC (jak i CBC i kazdy inny).
          Widzący o kolegów dwa kapelusze tej samej barwy nie wie nic o swoim, bo nie
          wie, jak upadła "jego" moneta.
          Przedstawione przeż niektorych rozumowanie doprowadza do wniosku,że tym łatwiej
          odgadnąć barwę, im więcej jest uczestnikow poddanych próbie.
          • re4ct0r Re: Po zastanowieniu się 21.05.05, 18:13
            Pewny napisal:
            "ale strażnik z takim samym prawdopodobięństwem może wyrzucic znowu biały, nie
            czując zadnych zobowiązań wobec deliberacji,że układ 2+1 występuje częsciej,
            niz inne. Układ trzech białych jest tak samo prawdopodobny jak BBC (jak i CBC i
            kazdy inny)."

            Tak uklad trzech takich samych ma takie samo prawdopodobienstwo jak wszystkie
            inne uklady ale... zauwaz moj drogi "pewny" kolego ze sa tylko dwa uklady w
            ktorych wszyscy trzej beda mieli takie same nakrycia glowy... w pozostalych
            przypadkach (a jest ich 6) wystąpi uklad 2+1 a wiec prawdopodobienstwo ze
            wszyscy wylosuja to samo wynosi 25% podczas gdy uklad 2+1 wystapi z prawd.
            75%... Zagadka cardemona jest bardzo interesujaca i mimo ze rozumiem o co
            chodzi to nie umiem znalezc optymalnego rozwiazania:D:D
            • Gość: Obserwator Re: Po zastanowieniu się IP: *.neoplus.adsl.tpnet.pl 21.05.05, 20:54
              Przestańcie wypistwać bzdury na temat tego,że duże prawdopodobieństwo układu
              2+1 ma jakikolwiek wpływ na jedno rozmieszczenie kapeluszy.Gdyby takie
              losowania odbywały sie codzennie, to takie układy wystepowałyby stosunkowo
              często, ale nie w jednym jedynym przypadku. Prawdopodobieństwo jekiegoś
              zdarzenia mówi tylko o częstotliwości wystepowsnia zjawiska w dużych seriach
              doświadczeń. Kto ma zamiar raz grać w karty, może nie przejmować się
              prawdopodobieństwem - to jest potrzebne tyn,którzy grają stale.Z tego,ze nikt w
              mojej pracy nie wygrał dotąd w totolotka nie zwiększa mojej szansy na wygraną.
              • kopperek Re: Po zastanowieniu się 21.05.05, 21:22
                Gość portalu: Obserwator napisał(a):

                > Przestańcie wypistwać bzdury na temat tego,że duże prawdopodobieństwo układu
                > 2+1 ma jakikolwiek wpływ na jedno rozmieszczenie kapeluszy.Gdyby takie
                > losowania odbywały sie codzennie, to takie układy wystepowałyby stosunkowo
                > często, ale nie w jednym jedynym przypadku. Prawdopodobieństwo jekiegoś
                > zdarzenia mówi tylko o częstotliwości wystepowsnia zjawiska w dużych seriach
                > doświadczeń. Kto ma zamiar raz grać w karty, może nie przejmować się
                > prawdopodobieństwem - to jest potrzebne tyn,którzy grają stale.

                No nie do końca, chociaż jest w tym ziarno prawdy - zależy o jakich wartościach
                prawdopodobieństwa mówimy. Gdyby mi przyszło wybierać między dwiema opcjami o
                prawdopodobieństwie 0.001 i 0.003, to pewnie też bym - dla pojedynczego
                eksperymentu - te wartości olał, ale gdyby to było odpowiednio 0.2 i 0.6, to
                już nie. Kwestia tego, czy masz jakieś inne kryterium - niech to nawet będzie
                wiara we własną intuicję:) - które możesz zastosować. Bo koniec końców jakieś
                jednak zastosujesz.

                Z tego,ze nikt w
                >
                > mojej pracy nie wygrał dotąd w totolotka nie zwiększa mojej szansy na wygraną.

                Oczywiście że nie, ale to zupełnie inny problem.
      • Gość: uważny Re: Siedmiu Dezerterów: 87.5% IP: *.neoplus.adsl.tpnet.pl 23.05.05, 13:36
        Szanowni dyskutanci! Odpowiedzmy sobie na pytanie:Czy po serii 10 rzutów monetą
        i otrzymaniu 10 orłów(co jest mało prawdopodobne, ale możliwe i niekiedy sie
        zdarza)wyrzucenie jedenastego orła jest bardziej prawdopodobne niż wyrzucenie
        reszki? Podobnie w układzie OOOxOOOOOO ( 9 orłów i w srodku zakryty wynik x?)
        Wiadomo,że najbardziej prawdopodobny układ jest 5+5, ale jesli zaszedł akurat
        konkretnie ten pokazany, to co powiemy o prawdopodobieństwie x?
        • Gość: pafcio Re: Siedmiu Dezerterów: 87.5% IP: *.aster.pl / *.aster.pl 23.05.05, 13:45
          prawdę pisząc nie mam już sił starać się pokazać, gdzie jest błąd w rozumowaniu
          niedowiarków. dlatego apeluję do wszystkich, którzy niedowierzają argumentom,
          że są możliwe takie strategie o napisanie krótkiego programiku, w którym w
          tysiącu pętli będą dla 3 zawodników następujące założenia:
          - jeżeli co najmniej jeden z nich zgadnie jaki ma kapelusz (wybrany z
          prawdopodobieństwem 50%) na głowie i żaden nie pomyli się to wygrali - w
          przeciwnym wypadku przegrali
          - po wylosowaniu dla nich kapeluszy, ten który widzi 2 kapelusze tego samego
          koloru mówi kolor przeciwny, ten który widzi po jednym kapeluszu z obu kolorów
          mówi nie wiem.
          - następnie sprawdzane jest czy któryś z nich się pomylił i w takim przypadku
          do licznika wygranej dodaje się/nie dodaje jeden
          - i od początku
          a następnie proszę się zastanowić dlaczego komputer po wyliczeniu wyniku
          pokazuje na złość niedowiarkom wynik dążący do 75% a nie do 50%.

          pozdrawiam
          pafcio
          • Gość: grzesiek Re: Siedmiu Dezerterów: 87.5% IP: *.cbk.waw.pl / *.cbk.waw.pl 23.05.05, 18:20
            Mam radę dla tych którzy chcą weryfikować swoje pomysly przy użyciu
            komputera. Nie trzeba losowo wybierać bardzo wielu ukladów, wystarczy
            rozpatrzeć 128 wszystkich mozliwych ulożeń kapeluszy. Wszystkie te ulożenia
            są jednakowo prawdopodobne, więc skutecznośc strategii będzie po prostu ulamkiem
            N / 128, gdzie N jest liczbą tych ulożeń, dla których strategia doprowadzila do
            sukcesu.
            Do programowego generowania 128 przypadków najwygodniej użyć zwyklej pętli for
            od 0 do 127, a następnie mlodsze 7 bitów zmiennej indeksowej potraktować jako
            wyróżniki kolorów kapeluszy.
        • Gość: gosc Re: Siedmiu Dezerterów: 87.5% IP: *.ire.pw.edu.pl 23.05.05, 14:07
          Gość portalu: uważny napisał(a):

          > Szanowni dyskutanci! Odpowiedzmy sobie na pytanie:Czy po serii 10 rzutów
          > monetą i otrzymaniu 10 orłów (co jest mało prawdopodobne, ale możliwe i
          > niekiedy sie zdarza) wyrzucenie jedenastego orła jest bardziej
          > prawdopodobne niż wyrzucenie reszki?
          Oczywiscie, ze w tym momencie prawdopodobienstwo jest 50%, ale przeciez nie na
          tym polega problem w zagadce!


          > Podobnie w układzie OOOxOOOOOO ( 9 orłów i w srodku zakryty wynik x?)
          > Wiadomo,że najbardziej prawdopodobny układ jest 5+5, ale jesli zaszedł
          > akurat konkretnie ten pokazany, to co powiemy o prawdopodobieństwie x?
          Oczywicie 50% i nikt ze zgadujacych tego nie kwestionuje. Rozwiazania dotycza
          INNEGO PROBLEMU!
          • Gość: uważny Re: Siedmiu Dezerterów: 87.5% IP: *.neoplus.adsl.tpnet.pl 23.05.05, 14:49
            Problem jest w tym,ze to wcale nie jest inny problem niż pokazany wyżej.Jesli
            ktoś widzi dwa białe, to jest pewientylko tego,że nastapiło rozdanie BBB lub
            BBC - oba z jednakowym prawdopodobięństwem 1/8. To że częsciej występują inne
            układy tu nie ma znaczenia, bo tu jest wybór jednego z dwóch możliwych. Przy
            BxB jest to jeden z układów BBB lub BCB - tu srodkowy więżień jest w sytuacji
            trzeciego (z poprzedniego przykładu). Gdyby zarzad w2ięzienia codziennoe
            dokonywał tego typu zabawy, to układ 2+1 wystepowałby trzy razy częsciej niż 3
            • Gość: PM Re: Siedmiu Dezerterów: 87.5% IP: *.neoplus.adsl.tpnet.pl 23.05.05, 15:17
              Bardzo mi przykro i podejzewam się o niedorozwój,ale nie widzę róznicy między
              zgadywniem trzeciego wyniku rzutu monetą kiedy o serii wiem OxO,OOx,xOO i x
              każa mi zgadywać, a odgadnięciem koloru kapelusza, kiedy dwa z nich widzę jako
              odwzorowanie rzutu ww monet. Dla monet mówia mi z przekonaniem o
              prawdopodobieństwie równym 1/2, a kapelusze już sie temu nie chcą poddać i
              część zgadujących wierzy,że jest inaczej, biorąc za świadka komputer. Komputera
              tu nie winie, tylko programistę.
            • Gość: gosc Re: Siedmiu Dezerterów: 87.5% IP: *.ire.pw.edu.pl 23.05.05, 15:25
              Nie jest problemem jaka ma szanse pojedynczy zgadujacy w konkretnym momencie,
              tylko jaka ma szanse cala grupa przy stosowaniu takiej czy innej strategii
              grupowej. Gdyby zarzad więzienia codziennie dokonywał tego typu zabawy, to
              grupa zdajaca sie na jednego skazanego wychodzilaby calo srednio cztery dni na
              osiem, a grupa stosujaca strategie podana w rozwiazaniach wychodzilaby calo
              srednio szesc dni na osiem.
      • andy._ Re: Siedmiu Dezerterów: 87.5% 23.05.05, 21:41
        Potwierdzam 87.5% :)
        Nie podaję jeszcze rozwiązania, ale podzielę sie pewnymi wrażeniami.
        Przede wszystkim dołączam się do wszystkich głosów o niesamowitości,
        wielopłaszczyznowości/wielopoziomowości czy wręcz genialności tej arcytrudnej
        zagadki.
        Rozwiazanie 50% jest oczywiste, ale ciekawe iż kilka osób wbrew oczywistym
        wywodom i dowodom uporczywie twierdzi, że wszystkie lepsze wyniki to humbug.
        Algorytm Pafcia skwitowałem komentarzem, że jest on optymalny w klasie
        rozwiązań globalnych i trzeba szukać poprawy w podziałach na grupy. Okazało się
        to nie do końca prawdą. Rzeczywiście jest on optymalny (co sprawdziłem
        odpowiednim programikiem zanim wydałem taką opinię) jeżeli kierujemy się
        kryterium ile bialych i ile czarnych kapeluszy widzimy. Wydaje się, że w klasie
        rozwiązań globalnych nie może być innych kryteriów - a jednak!
        Ciekawe czy brak na ten temat komentarza Cardemona w jego podsumowanich był
        przypadkowy, czy też chodziło o nie sugerowanie kierunku poszukiwań? W każdym
        razie dla mnie ten brak komentarza był pewną wskazówką czy może nie wrócić
        jeszcze do rozwiązań globalnych.
        Potem nastąpiło fantastyczne w swojej prostocie 75% Ullera oraz poprawka na
        78.125%
        Po wzmiance o symetrii szukałem jeszcze symetrycznych pomysłów grupowych,
        układałem 7 bitów w różne ładne figury, ale czułem, że symetria będzie raczej
        globalna z jakimś piekielnym algorytmem.
        No i przyszła iluminacja ...

        Pozdr.
        A._
        • cardemon Re: Siedmiu Dezerterów: 87.5% 23.05.05, 22:23
          BRAWO Andy!!!

          Wszystkie spostrzeżenia i uwagi jak najbardziej trafne, aż brak mi słów uznania.
          Korciło mnie strasznie, żeby coś po drodze podpowiedzieć, wskazać właściwy
          kierunek, ale gryzłem się nieustannie w język. Będzie jeszcze miejsce i czas,
          żeby przedstawić pełne rozwiązanie, ale myślę, że warto zacząć od początku czyli
          podać od czego się to wszystko zaczęło, a zaczęło się od:

          "Zagadka kolorowych kapeluszy absorbuje teoretyków

          Matematyczna zagadka, która wydaje się mieć poważne implikacje w teorii
          kodowania, zastanawia matematyków i informatyków. Dr Todd Ebert, instruktor nauk
          komputerowych na Uniwersytecie Irvine przedstawił tę zagadkę w swojej pracy
          doktorskiej na Uniwersytecie Santa Barbara w 1998. Rozwiązanie podobno ma
          wielkie implikacje w dziedzinie korekcji błędów.
          Zagadka jest taka: trzech graczy wchodzi do pokoju i na głowie każdego
          umieszczony zostaje czerwony lub niebieski kapelusz, wybrany losowo. Gracze
          widzą kolory innych kapeluszy, ale nie widzą koloru swojego własnego. Niemożliwa
          jest jakakolwiek komunikacja, a gracze muszą jednocześnie odgadnąć kolor swojego
          własnego kapelusza, albo spasować. Cała grupa wygrywa symboliczne 3 miliony
          dolarów, jeżeli przynajmniej jeden gracz odgadnie poprawnie i nikt się nie
          pomyli. Zagadka jest sformułowaniem strategii, która maksymalizuje
          prawdopodobieństwo, że grupa, składająca się z różnej liczby osób, wygra nagrodę."

          www.tomshardware.pl/technews/20010416.html
          Polecam też link do angielskojęzycznego artykułu na temat tego problemu
          (przedruk z New York Times):

          instruct1.cit.cornell.edu/courses/math336/hat.html
          Z tego artykułu zaczerpnąłem słowa porównujące rozwiązanie do struktury
          kryształu (nawiązanie do wypowiedzi dr. Amina Shokrollahi'ego).

          Na koniec jeszcze raz wyrażam najwyższe słowa uznania dla Andy'ego i cieszę się,
          że problem został pomyślnie rozwiązany.

          CdM
          • andy._ Re: Siedmiu Dezerterów: 87.5% 23.05.05, 23:23
            Ja też kręciłem się w kółko bez efektu przez sporą część weekendu, ale
            przyjemność wyrwania się z takiego kręgu i dojścia do czegoś niespodziewanego
            jest ogromna.
            Może dozować rozwiązanie stopniowo dając szanse chętnym na samodzielną
            kontynuację?
            Rozwiazanie dla N=7 jest z dokładnoscią do pewnego kluczowego szczegółu
            analogiczne jak dla N=3. Dla N=3 symetria polega na dwóch biegunach BBB i CCC
            pomiędzy którymi są węzły BCC, BBC, BCB, CBB, CCB i CBC. Dla N=7 będzie wiecej
            biegunów i więcej węzłów ...

            Pozdr.
            A._
            • mesquaki Re: Siedmiu Dezerterów: 87.5% 23.05.05, 23:47
              Jestem pod głębokim wrażeniem, zarówno zagadki, jak i rozwiązania Andy'ego.
              I chętnie bym już je poznała.

              Choć trochę się obawiam,że będzie jak w pewnym starym opowiadaniu SF, w którym
              istniała strategia szachowa tak porażająco doskonała, że każdy, kto ją
              zobaczył, popadał w obłęd:)

              m
              • andy._ Re: Siedmiu Dezerterów: 87.5% 24.05.05, 00:01
                Może nie będę wykładał jeszcze kawy na ławę, ale podam tem kluczowy szczegół
                dla N=3:
                Dla BBC trzeci zgadujący nie dlatego mówi C bo widzi dwa B tylko dlatego, że
                BBx "bliżej" do węzła BBB niż do węzła CCC.

                Pozdr.
                A._
              • kopperek Re: Siedmiu Dezerterów: 87.5% 24.05.05, 00:31
                m napisała:

                "Jestem pod głębokim wrażeniem, zarówno zagadki, jak i rozwiązania Andy'ego.
                I chętnie bym już je poznała.

                Choć trochę się obawiam,że będzie jak w pewnym starym opowiadaniu SF, w którym
                istniała strategia szachowa tak porażająco doskonała, że każdy, kto ją
                zobaczył, popadał w obłęd:)

                m"

                to zupełnie jak z Wirem Całkowitego zrozumienia Douglasa Adamsa...
                "Wir Całkowitego Zrozumienia ewokuje obraz wszechświata metodą ekstrapolacyjnej
                analizy materii.
                Dla wyjaśnienia: Ponieważ na każdą cząsteczkę materii we wszechświecie
                odddziaływują w jakiś sposób wszystkie pozostałe cząsteczki wszechświata,
                teoretycznie możliwe jest wnioskowanie o właściwościach wszystkiego, co istnieje
                - o każdym słońcu, każdej planecie, ich orbitach, składzie chemicznym oraz ich
                historii ekonomicznej i społecznej - na podstawie wyników badań dowolnego
                elementu wszechświata, czyli na przykład kawałka ponczowego tortu."

                myślę że algorytm Andy'ego działa mniej więcej podobnie....;)

                "Wsadzony do wiru osobnik natychmiast widzi całą niewyobrażalną nieskończoność
                stworzenia, a gdzieś w środku obrazu pojawia się mikroskopijny punkt oraz
                skierowana na niego strzałka, na której widnieje napis: OTO TY".

                a to o nas:D.

                Też chętnie bym poznał algorytm.
    • andy._ "o tej zagadce można opowiadać godzinami" 24.05.05, 09:57
      No to zaczynam:

      Dla trzech skazanych rozwiązanie też cechuje się piękną symetrią i podany
      schemat jest tylko jednym z możliwych.

      Zastosuję notację wprowadzoną przez Mesquaki:

      1 kolumna - kolory kapeluszy na głowach 3 więźniów;
      2 kolumna - deklaracje tych 3 więźniów;
      3 kolumna - wynik całościowy dla trójki)

      1_BBB__CCC__rozstrzelanie
      2_BBC__??C__wolność
      3_BCB__?C?__wolność
      4_BCC__B??__wolność
      5_CBB__C??__wolność
      6_CBC__?B?__wolność
      7_CCB__??B__wolność
      8_CCC__BBB__rozstrzelanie

      Jeżeli zastąpimy B przez C, a C przez B to cała tabelka się zaneguje, schemat
      nadal będzie poprawny, ale oczywiście nie jest to istotnie różne rozwiązanie i
      nadal cechuje się ono taką właściwością, że głosujemy na kolor "mniejszościowy".

      Lecz czy już nie jest zaskakujący poniższy, też prawidłowy schemat:

      1_BBB__??B__wolność
      2_BBC__CCB__rozstrzelanie
      3_BCB__B??__wolność
      4_BCC__?C?__wolność
      5_CBB__?B?__wolność
      6_CBC__C??__wolność
      7_CCB__BBC__rozstrzelanie
      8_CCC__??C__wolność

      No tak, schemat jak schemat, można się dopatrywać róznego rodzaju symetrii, ale
      jakie kryterium stosują więźniowie? I tu leży całe sedno decydujące o tym, że
      ta piękna zagadka jest z najwyższej półki. Udzieliłem już istotnej podpowiedzi
      w moim poprzednim poscie, dokończenie wkrótce... (po odgadnięciu kryterium
      przejście na siedmiu skazanych to już małe piwo)

      Pozdr.
      A._
      • mesquaki lampion 24.05.05, 21:41
        No to ja sobie narysowałam strukturę Kripke'go (stany nierozróżnialne przez
        więźnia 1 połączone krawędziami w kierunku X, więźnia 2 w Y, więźnia 3 w Z) ,
        nadałam tym krawędziom polaryzację zgodnie z decyzją więźnia, (strzałka w
        kierunku, stanu, który obstawia) no i wyszedł mi ładny sześcianik z dwoma
        przeciwległymi wierzchokami (biegunami) od których wszystkie 3 strzałki
        odchodzą, a więc będą to sytuacje źle odgadnięte. Strzałki pokazują stany
        prawidłowo odgadnięte.A biegun to by była taka sytuacja, że jak ktoś ma do
        wyboru ją i alternatywną, to zawsze wybierze alternatywną.

        Zastosować tego do 4,5 i 6 więźniów się nijak nie udało.
        A co do siedmiu...

        Majaczy mi się taka struktura, coś jak podługowaty lampion, zbudowana z
        krawędzi, które łączą stany nierozróżnialne przez więźnia. No i ma toto dwa
        bieguny na wierzchołkach 7B i 7C i po 7 biegunów postaci 3B4C i 4B3C, takich że
        się wzajemnie uzupełniają. To znaczy, z każdego bieguna 3B4C 3 strzałki idą w
        kierunku 21 stanów 2B5C, a 4 w kierunku 4B3C i vice versa. Czyli w biegunach
        się skupi 16 pomyłek. A krawędzie odchodzące od biegunów będą wskazywały stany
        prawidłowo odgadnięte, 7 strzałek * 16 biegunów= 112.

        Maligna???
        m
            • Gość: grzesiek Re: lampion IP: *.cbk.waw.pl / *.cbk.waw.pl 25.05.05, 12:21
              Chyba zaczynam rozumieć o co chodzi. Warunek że odleglość między
              biegunami >= 3 zamienil bym na inny - że każdy z pozostalych punktów
              (nie biegunowych) powinien mieć tę wlasność, że istnieje w jego okolicy
              dokladnie jeden biegun odlegly o jeden. Jeśli tak nie będzie, to:
              1) Jeśli wokól punktu nie ma żadnego bieguna to nikt nie będzie zgadywal,
              2) Jeśli będzie więcej biegunów, to będzie zgadywać więcej osób niż jedna.
              Obie sytuacje są niekorzystne.

              Komputerem znalazlem następujący uklad biegunów:

              1: CCCCCCC
              2: CCCCBBB
              3: CCBBCCB
              4: CCBBBBC
              5: CBCBCBC
              6: CBCBBCB
              7: CBBCCBB
              8: CBBCBCC
              9: BCCBCBB
              10: BCCBBCC
              11: BCBCCBC
              12: BCBCBCB
              13: BBCCCCB
              14: BBCCBBC
              15: BBBBCCC
              16: BBBBBBB

              ale jak do tego dojść na piechotę to nie wiem, czekam na wyjaśnienia Andy-ego.
              • andy._ Re: lampion 25.05.05, 14:53
                A kto powiedział, że nie używałem komputera? Pisałem programiki sprawdzające
                różne koncepcje, ale akurat zestaw biegunów uzyskałem inaczej. Oto już trzeci
                zestaw (o ile propozycja Mesquaki spełnia warunek >=3):
                BBBBBBB
                BBBCCCB
                BBCBCBC
                BBCCBCC
                BCBBBCC
                BCBCCBC
                BCCBCCB
                BCCCBBB
                + negacje.
                Swoją drogą ciekawe ile jest różnych 16-tek mogących być biegunami? Ale to już
                raczej nie zagadka tylko zadanie.
                Jeśli znajdę trochę więcej czasu to opiszę jak dochodziłem do rozwiązania

                Pozdr.
                A._
                • mesquaki Re: lampion 25.05.05, 15:08
                  Ja to zrobiłam na piechotę. Wzięłam dowolny stan z 3C4B, 6 pozostałych stanów
                  3C4B tak, żeby wszystkie były odległe od siebie o 4 bity, 7C i ich negacje. Tak
                  żeby było ładnie i symetrycznie :).
                  m
        • andy._ Re: lampion 24.05.05, 23:47
          Zadna maligna tylko ciepło, ciepło, a nawet gorąco!

          Dla trzech więźniów sprawa jest chyba jasna - sześcianik z ośmiu
          sytuacji/wierzchołków jest doskonałym modelem.

          Dla 4,5,6 więźniów tracimy strukturę krystaliczną, która znowu się pojawia dla
          siedmiu!
          Z wyrażenia
          7 strzałek * 16 biegunów= 112
          można dojść do równania na liczbę biegunów N:
          W * N + N = 2 ^ W (gdzie W to liczba więźniów)

          W N
          3 2
          4 3.2
          5 5.67
          6 9.4
          7 16

          Widać, że dla W=3 i W=7 następuje "krystalizacja" wyniku całkowitego.

          Lampion mi się podoba chociaż ja w pewnym momencie zrezygnowałem z rysowania
          tych dziesiątków krawędzi na płaszczyźnie i poszedłem a w stronę algebraiczną.
          Niestety muszę już dziś kończyć, jutro opiszę moje rozwiązanie

          Pozdr.
          A._
          • mesquaki Re: lampion 25.05.05, 00:32
            No to wszystko jasne. Suuuper, Andy mnie wciągnął do Wiru :).
            Chylę czoła, Andy. Genialny pomysł.

            Zastanawiam się tylko, o czym będę jutro rozmawiać z szefową? Bo chyba o
            zagadce (godzinami :) nie będzie chętna.
            m
            • lapacz_w_zycie Okropność 25.05.05, 14:16
              Czytam informację:
              BBC opublikowało nieprawdziwe informacje (...)
              i myślę: wolność.

              Prośba do Cardemona:
              przed kolejnym takim zadaniem
              uprzejmie proszę o ostrzeżenie
              analogiczne do tego jakie znajduje się
              na papierosach.
              Może być np.
              Próba rozwiązania może spowodować
              długotrwałe oderwanie od rzeczywistości
              i wywołać kompleksy.
      • andy._ Re: "o tej zagadce można opowiadać godzinami" 25.05.05, 12:41
        ...obiecane dokończenie:

        We wtrąconym w międzyczasie podwątku "Lampion" Mesquaki bardzo ładnie
        rozsupłała węzeł, który dla przypomnienia wyglądał następująco:

        1_BBB__??B__wolność
        2_BBC__CCB__rozstrzelanie
        3_BCB__B??__wolność
        4_BCC__?C?__wolność
        5_CBB__?B?__wolność
        6_CBC__C??__wolność
        7_CCB__BBC__rozstrzelanie
        8_CCC__??C__wolność

        A teraz moja odpowiedź na pytanie jaką strategię stosują odgadujący.
        Zacznę od tego, że jest to strategia globalna, to znaczy wszyscy więźniowie
        stosują ten sam algorytm (nie ma żadnego podziału na grupy).
        Trudość zagadki polega na tym, że ten algorytm nie bazuje tylko na tym co widzą
        poszczególni skazańcy, ale dodatkowo na pewnych z góry ustalonych i znanych
        wszystkim więźniom stałych. W podanym przykładzie tymi stałymi są rozkłady
        kolorów BBC oraz CCB, które grupa w czasie wstępnej narady przeznacza na
        straty, to znaczy jeśli los przydzieli im takie rozkłady kolorów to zostaną
        rozstrzelani (25%). Na szczęście w pozostałych 75% mają PEWNOŚĆ przeżycia jeśli
        zastosują poniższą strategię:
        Patrzę na widoczne kapelusze i sprawdzam na ilu pozycjach (oczywiście nie
        biorąc pod uwagę własnej) kolory różnią się od wybranych stałych. Jeżeli się
        nie różnią od którejś ze stałych to mówię kolor odwrotny niż w tej stałej na
        mojej pozycji, jeżeli z żadną ze stałych nie mam zgodności to deklaruję "nie
        wiem".
        Dla siedmiu więźniów strategia jest identyczna, problem tylko polega na
        odpowiednim wyborze 16-tu odpowiednich stałych

        Pozdr.
        A._
        • Gość: PM Re: Siedmiu Dezerterów IP: *.neoplus.adsl.tpnet.pl 25.05.05, 22:26
          Ciekawą innowacje wprowadził inicjator wątku "Dwie cele", kiedy kolory są
          przydzielane losowo, ale z róznymi prawdopodobieństwami.
          Przy jednakowych prawdopodobieństwach (rzut monetą)podsobna idea dotyczy 2^n -1
          więźniów, przy rzucie dwiema monetami (np OO=biały, zas pozostałe - czarny) już
          sprawa sie komplikuje.
          • Gość: Wątpiący Podejrzenie nieścisłosci IP: *.neoplus.adsl.tpnet.pl 28.05.05, 03:17
            Jaka jest dyspozycja w stosunku do deklarujących w przypadku siódemki? Dla
            trójki jest prosto -Zgłaszaj kolor,którego nie widzisz lub milcz. Dla
            siedmiu"Zgłaszaj kolor którego jest mniej lub milcz" gwarantuje sukces w
            35/64=54,7% i zastanawia ten wysoki procent andy'ego.W sytuacji 2B+5C dwóch
            widzi 1B+5C i zgłasza (wg.umowy)C, ale pięciu uwidzi 2B+4C i też zgłasza
            B,przekonani,ze tak powinni i kładą całą imprezę. Niezależnie od wprowadzonych
            węzłów nie widzę, jak zapobiec niefortunnym odzywkom. Przy układach 3+4 trzech
            mówi,czterech milczy a takich układow jest 70 wsród 128. Od pewnego czasu
            dyskusja wygasła, a poża zgłoszonym wynikiem nie bardzo wiadomo, skąd
            wypłynął.Cerdemon wygląda na zadowolonego,ale też nie spieszy z wyjaśnieniami,
            tylko zachwyca się kryształową struturą zagadki, o czym dosyc mętnie mówi
            wspomniany przez niego artykul w j. angielskim.
            • andy._ Re: Podejrzenie nieścisłosci 28.05.05, 09:38
              Wydawało mi się, że w podwątkach "lampion" i "o tej zagadce można opowiadać
              godzinami" wszystko zostało już wyjaśnione, a w szczególności dyspozycja, że
              nie głosujemy na kolor "większościowy" tylko w zależności od węzłów.
              Nieprawdą jest, że "Przy układach 3+4 trzech mówi, a czterech milczy".

              Pozdr.
              A._
              • Gość: Wątpiący dalej Re: Podejrzenie nieścisłosci IP: *.neoplus.adsl.tpnet.pl 28.05.05, 13:56
                Rozumiem Twoja radość z wprowadzenia niezdefiniowanych węszłów i odległosci od
                nich, ale poża chęci "rozmawiania o tym godzinami" bez skonkretyzowania metody,
                sprawa nie jest całkowicie przejrzysta, bo nie padła odpowiedź,jak konkretnie
                wyglada ten algorytm.
                Prawdopodobieństwo 75% jest zozumiałe, jesli zostawi sie decyzje wybranej
                trójce więźniów, powiedzmy o najwyższych numerach. Ponieważ prawdopodobieństwo
                układu kolorów dla danej trójki jest takie samo, niezależnie od liczby
                pozostałych więźniów, wszystkim pozostałym kazemy milczeć, a dana trójka ma
                znane przepisy.,dajaće opisane już prawdopodobieństwo. Nie ma potrzeby
                wprowadzac nowych bytow.
                Wyjaśniam:Układ BBB wybranej trójki wystepuje z określoną liczbą układow dla
                pozostalych (16 dla pozostałych czterech). to samo z układem BBC i dalszymi.
                Uklad 2+1 wystapi 96 razy na 128 możliwych = 75%.W jaki sposob można zwiększyć
                to prawdopodobięństwo pozostaje tajemnicaą algorytmu i węlów.Nie ma co juz
                maglować przypadku trzech, bo w prosty sposob wyjasniła to kama w wątku "dwie
                cele" bezezłowo.
                • andy._ "o tej zagadce można opowiadać godzinami" 28.05.05, 21:14
                  Widzę, że o tej zagadce rzeczywiście "można godzinami", szczególnie z tymi co
                  nie wierzą w wynik ponad 50%, albo wątpią.
                  Maglowanie przykładu trzech bylo jednak celowe bo pozwoliło na odejście od
                  schematu "którego koloru więcej widzę". Schemat ten jest skuteczny dla trzech
                  więźniów, ale nie daje się uogólnić na 7-miu skazanych (to co pisze Kama
                  w "dwie cele" nie wychodzi poza ten schemat i nie pozwala na zrobienie kroku do
                  przodu, co zresztą potwierdzają Twoje wątpliwości).
                  Dopiero zauważenie, że wyjątkowymi rozkładami nie muszą być BBB i CCC (przy
                  jednoczesnej zmianie schematu) pozwala wprowadzić istotnie różne rozwiązania
                  dla trzech skazanych i uogólnienie dla siedmiu. Teraz muszę wyjść, ale jutro (o
                  ile sieć pozwoli) napiszę szczegółowe, konkretne, jednoznaczne rozwiązanie ...

                  Pozdr.
                  A._
                  • andy._ "o tej zagadce można opowiadać godzinami" 29.05.05, 12:31
                    " ...Dziś jest noc przed dniem egzekucji, wszyscy więźniowe siedzą w jednej
                    celi ..."

                    Oto podsumowanie nocnej narady siedmiu dezerterów:
                    Mamy 87.5% szansy na uniknięcie rozstrzelania jeżeli każdy dezerter
                    1. zapamieta swój numer (od D1 do D7);
                    2. wykuje na pamięć szesnastowierszową tabelkę z ponumerowanymi pozycjami
                    D D D D D D D
                    1 2 3 4 5 6 7
                    B B B B B B B
                    C C C C C C C
                    B B B C C C B
                    C C C B B B C
                    B B C B C B C
                    C C B C B C B
                    B B C C B C C
                    C C B B C B B
                    B C B B B C C
                    C B C C C B B
                    B C B C C B C
                    C B C B B C B
                    B C C B C C B
                    C B B C B B C
                    B C C C B B B
                    C B B B C C C
                    3. Po nałożeniu kapeluszy porówna sześć widzianych kolorów z każdym z szesnastu
                    wierszy tabelki i jeżeli widziany układ jest zgodny z którymkolwiek wierszem to
                    zgłasza kolor przeciwny niż jego własny kolor w tym wierszu tabelki. W innym
                    razie (żaden wiersz się nie zgadza) mówi "nie wiem".
                    Oczywiście porównywanie uwzględnia pozycje kolumn tabelki i np. dezerter D3
                    widząc CB?BCCC odpowiednio na pozycjach D1-D2 i D4-D7 zauważa zgodność z
                    ostatnim wierszem tabelki i zgłasza "mam C" (bo na pozycji D3 w tym wierszu
                    jest B).

                    Pozdr.
                    A._
                    • andy._ "o tej zagadce można opowiadać godzinami" 29.05.05, 12:38
                      Nagłówek tabelki lekko się rozsynchronizował, ale wydaje się nadal czytelny.
                      Gdyby ktoś miał wątpliwości to w takich przypadkach należy użyć "odpowiedz
                      cytując" (dostępna tylko dla zalogowanych) i cytat będzie juz odpowiednio
                      sformatowany

                      Pozdr.
                      A._
                      • Gość: Wątpiący już mniej Re: "o tej zagadce można opowiadać godzinami" IP: *.neoplus.adsl.tpnet.pl 29.05.05, 15:03
                        Rzeczywiście można godzinami,głównie,zeby wyjaśniać to co raz bardziej
                        precyzyjnie.Według Twojego opisu kazdy z tych siedmiu może utożsamić sięz tym
                        samym, powiedzmy z ostatnim, układem i wszzyscy radośnie podają barwę przeciwną
                        do noszonej, przegrywając. Jeżeli bazujemy na tych układach, to jak jest z
                        innymi? W układzie rzeczywistym różniącym się tylko jedną pozycją od ostatniego
                        ten jeden rzeczywiscie zgaduje, a pozostali, nie utożsamiając się z żadnym
                        układem , pasują.To rzeczywiściejest niegłupie, tylko tych bazowych układów
                        powinno być wg mnie więcej.Dziękuję za wprowadzenie w temat i jeżeli znajdę
                        niedoróbkę ze satysfakcją zgłoszę.
                        • Gość: PM Re: "o tej zagadce można opowiadać godzinami" IP: *.neoplus.adsl.tpnet.pl 30.05.05, 14:09
                          Andy wyjaśnił metodę postępowania, ale pewnie nie wszyscy rozumieją istotę
                          przedstawionej metody – sadzę po sobie, bo nie od razu doszło to do mnie.
                          Pomysł jest prosty, ale na tym polega sukces Andy’ego, że go dostrzegł. To
                          mianowicie, że prawdopodobieństwo konkretnego rozkładu kolorów wśród siedmiu
                          zainteresowanych jest 7 razy mniejsze od sumy rozkładów różniących się jedna
                          pozycją od tego konkretnego. Znacznie trudniejsze było znalezienie metody
                          dającej tylko jednemu wypowiadać się na temat swojego nakrycia głowy, gdyż
                          kilku deklarantów ilustrowałoby przysłowie „gdzie kucharek 6…”.Pomysł
                          z „węzłami” jest genialny, choć nie doczytałem się, skąd je wziąć. Domyślam
                          się, że można postąpić tak: Wypisujemy wszystkie układy
                          • andy._ Re: "o tej zagadce można opowiadać godzinami" 30.05.05, 17:08
                            Cztery uwagi na gorąco:
                            - Z tym znajdowaniem węzłów to nie jest takie proste. Podany sposób nie daje
                            gwarancji róznicy na minimum trzech pozycjach pomiędzy dowolną parą węzłów z
                            szesnastki (ale może się udać).
                            - niestety "w pozostałych 16" wszyscy się pomylą i nie mają szansy na powtórny
                            eksperyment.
                            - Podobne rozumowanie można przeprowadzić dla 15, 31, 63, itd (widzę, że 53 to
                            literówka).
                            - dla 9-ciu lepiej wytypować siódemkę!

                            Pozdr.
                            A._
                            • Gość: PM Re: Na gorąco IP: *.neoplus.adsl.tpnet.pl 30.05.05, 19:25
                              To cos mi umknęło uwadzę. Po co ta róznica?
                              Te liczby to 2^n - 1. Rzeczywiście, wszyscy wykrzykuja nie to co trzeba, ale
                              ta zgodnośc moze wzruszyc szefa zakładu i ponowi próbę.
                              Masz rację do 14 wybrać siódemkę, dla 15 nowa baza itd do 62. może da sie
                              wykombinować cos dla liczb pośrednich. W kazdym razie, dzięki za wyjaśnienia.
                              Duże brawa!
                              • andy._ Re: Na gorąco 30.05.05, 20:20
                                Ta różnica jest kluczowa, bo tylko wtedy węzły ułożą się w "kryształ" o którym
                                pisał Cardemon.
                                A tak już bez poezji to powtarzam moje uszczegółowienie idei Mesquaki:
                                Z wyrażenia: 7 strzałek * 16 biegunów(węzłów) = 112
                                można dojść do równania na liczbę biegunów N:
                                W * N + N = 2 ^ W (gdzie W to liczba więźniów)

                                W N
                                3 2
                                4 3.2
                                5 5.67
                                6 9.4
                                7 16

                                Widać, że dla W=3 i W=7 (a także jak zauważyłeś dla 2^N-1)
                                następuje "krystalizacja" wyniku całkowitego.

                                Nie stawiam kropki nad i, aby czytający mogli samodzielnie dojść do związku
                                pomiędzy równaniem a warunkiem >=3.

                                Pozdr.
                                A._
                                • tororo Re: Na gorąco 30.05.05, 23:11
                                  Witam wszystkich
                                  Po długim zimowym śnie z powrotem wracam do krainy łamigłówek.
                                  Łamigłowka wrzucona przez Cardemona - oczywiście jak zwykle niesamowita.
                                  Wróciły "stare cardemnowe klimaty". Dzięki ci Cardemonie !

                                  Do Andy'ego mam pytanie. Napisałeś
                                  "Mamy 87.5% szansy na uniknięcie rozstrzelania jeżeli każdy dezerter
                                  1. zapamieta swój numer (od D1 do D7);
                                  2. wykuje na pamięć szesnastowierszową tabelkę z ponumerowanymi pozycji..."

                                  Jak się przygladam zaproponowanej metodzie - to wydaje mi się ,że jednak każdy
                                  powinien też zapamiętać numer przydzielony jego współtowarzyszom. Inaczej w
                                  żaden sposób nie będzie mógłodpoznać z którym węzłem ma do czynienia - mylę się
                                  czy nie?

                                  Poniewaz zagadka jest już rozwiązana, więc nie zrobię szkody jesli podam wyniki
                                  szperania po necie.

                                  1) Problem mozna też rozwiązać bez zapamietywania całej tablicy.
                                  Procedura (autor Peter Winkler) jest nastepująca ją :

                                  Kazdy otrzymuje numer od 1 do 7. Musi pamietać jakie numery mają pozostałe osoby
                                  i misi znać reprezentację tych liczb w systemie dwójkowym

                                  Z chwilą kiedy zobaczy kapelusze na głowach innych dodaje, ale w mod 2 (0+1=1;
                                  0+0=0; 1+1=0)wszystkie numery tych, którzy mają czarne kapelusze. Jesli wynik
                                  jest 000 to mówi że ma czarny kapelusz, jesli wynik równy jest jego numerowi -
                                  mówi że ma biały kapelusz. W pozostałych przypdkach milczy.

                                  2) problem pojawił sie w sieci w 2001 roku i znany był jako "hat problem".
                                  Proponowane rozwiązania (głownie takie jak Andy'ego) wynikają z zastosowania
                                  jednego z kodów Hamminga uzywanych do kontroli przesyłanych danych. W
                                  stosowanych kodzie nazywanym - (7,4 Hamming code) - do kontroli przesyłu 4
                                  bitowych słów uzywane są dodatkowo 3 bity kontrolne. Całość tworzy 16 7-bitowych
                                  słów zwanych kodami. To są te węzły z rozwiązania Andy'ego. Jesli przesłana 7
                                  bitowa informacja nie nalezy do zbioru tych 16 słów - a do zbioru pozostałych
                                  112 (z możliwych 128) to znaczy że w czasie przesyłu informacji wkradł się bład
                                  w 1 lub dwóch bitach. Bład nie zostanie wykryty jesli zostaną zmienione 3
                                  bity. (bo taka jest "odległość bitowa" między kodanmi- zwana odległością Hamminga.
                                  Wiecej możecie znaleźć w Googlu wrzucając powyższe nazwy i terminy. Jest tego
                                  całkiem sporo - w większości przypadków - ale nie we wszystkich - przyda się
                                  podstawowa znajomość algebry liniowej.

                                  Z ciekawostek - okazuje się ze z podobnych metod korzysta przyroda przy
                                  kontroli przekazywania informacji m.in. o białkach.

                                  Szczególne słowa uznania składam wszystkim tym którzy z zgadnieniami kontroli
                                  przesyłu informacji nie mieli dotąd do czynienia a dzielnie poszli w ślady
                                  Hamminga m.in formułując definicję odległości między poszczególnymi stanami(on
                                  wynalazł swoje metody w latach 40-tych zeszłego wieku)


                                  Pozdr
                                  tororo
                                  • andy._ Re: Na gorąco 31.05.05, 10:28
                                    > Jak się przygladam zaproponowanej metodzie - to wydaje mi się ,że jednak
                                    > każdy powinien też zapamiętać numer przydzielony jego współtowarzyszom.
                                    > Inaczej w żaden sposób nie będzie mógł rozpoznać z którym węzłem ma do
                                    > czynienia - mylę się czy nie?
                                    Oczywiście racja. Pisząc o wykuciu tabelki na pamięć miałem na myśli tabelkę
                                    razem z nagłówkiem (D1-D7), a wtedy przyporządkowanie numerów do konkretnych
                                    więźniów wydaje się oczywiste. Z drugiej strony przy takim podejściu punkt 1. o
                                    zapamietaniu swojego numeru staje się nadmiarowy (chciałem aby wywód był jak
                                    najbardziej łopatologiczny, a stał się nieprecyzyjny). W każdym razie celna
                                    uwaga, dzięki :)

                                    Procedura Winklera jest bardzo zręczna i zdecydowanie łatwiejsza do
                                    zapamiętania niż cała tabelka. To tylko potwierdza, że "o tej zagadce można
                                    godzinami...".

                                    Z pojęciem kodu Hamminga spotkałem się w czasie studiów, ale kojarzyło mi się
                                    wyłącznie (i dosyć mgliście) z wykrywaniem i korekcją błedów transmisji danych,
                                    ale nie z zagadką Cardemona. Większy wpływ na moje poszukiwania mogła mieć już
                                    mniej mglista pamięć o kodach Gray'a (bo to prosta idea słów binarnych
                                    różniących się tylko na jednej pozycji), ala tak naprawdę zdecydowała wskazówka
                                    o symetrii rozwiązania i brak komentarza Cardemona na moje stwierdzenie, że
                                    rozwiązanie Pafcia jest optymalne przy podejściu globalnym. To skłoniło mnie do
                                    porzucenia poszukiwania rozwiązań w podgrupach i powrotu do myślenia
                                    globalnego. Kiedy zauważyłem symetrię w rozwiązaniu dla trzech dezerterów i
                                    zrozumiałem na czym ona polega, przejście do siedmiu było prawie oczywiste.

                                    Pozdr.
                                    A._
Inne wątki na temat:

Popularne wątki

Nie pamiętasz hasła

lub ?

 

Nie masz jeszcze konta? Zarejestruj się

Nakarm Pajacyka