Siedmiu Dezerterów

[cardemon]

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

[Gość: kama]

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]

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]

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

[andy._]

To tylko 32.8125%
Po rozszerzeniu na
Jeśli widzisz 4 lub 5 lub 6 kapeluszy w tym samym kolorze zgłoś kolor przeciwny
dostajemy 54.6875%

Pozdr.
A._

[Gość: musk]

odpowiedZ podana przez kame jest poprawna , zagadka srednio-trudna

[Gość: pafcio]

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ść: Ula]

hej, strasznie fajna zagadka. i potrzebowalabym jej na...zajecia. studiuje
pedagogike kreatywnosci i mamy takie zajecia z zagadkami. zadalabym je mojej
grupie, ale musze znac odpowiedz. czy moglabym ja dostac na maila (zeby nie
psuc zabawy innym)? moj mail [e-mail] :)

[Gość: jo]

egzekutor miał okulay i mu w nie patrzyli

[Gość: Kama]

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._]

Strategia jednego wytypowanego stosującego algorytm podany prze Kamę daje 50%,
czyli tyle samo gdyby zawsze mówił biały albo czarny.

Pozdr.
A._

[andy._]

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ść: pm]

Pafcio mówi m.in. "Kto widzi 4 czarne i dwa białe mówi biały". Tak może widzieć
5 więźniów (gdy jest 5c+2b) i wtedy kazdy z nich mówi biały, t zn trzech się
myli i wszyscy giną.Lepiejjednak , kiedy mówi jeden wytypowany, a pozostali nie
wiem.

[Gość: kama]

Należy zwrócić uwagę,że nie może być błędnej wypowiedzi, tylko dobra lub "nie
wiem" System Pafcia gwarantuje błąd, jesli każdy widzący tylko dwa lub jeden w
danym kolorze poda ten kolor. Wtedy większośc poda ten sam kolor, wiec któryś
zrobi bład.

[Gość: Kujonik]

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]

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

Krótki komentarz - Re: Siedmiu Dezerterów

[cardemon]

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]

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]

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]

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.

Wniosek z narady

[Gość: PM]

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.

[Gość: Kama]

Wnioskowanie z tego co widać przypomina wiarę,że w totku trzeba skreślać
liczby, które sie jeszcze nie pojawiły w poprzednich grach.

[kornel-1]

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]

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

[kornel-1]

kornel-1 napisał:
> 75% widzę i się z tym zgadzam 32/128+48/128= 0.75

miało być po mojemu:
> 75% widzę i się z tym zgadzam 30/128+66/128= 0.75

k.

[mesquaki]

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

[mesquaki]

mesquaki napisała:

> widzę 3 C: Biały

miało być na odwrót, oczywiście:
widzę 3B: Czarny

[cardemon]

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]

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 :).

[kornel-1]

Autor: mesquaki
Data: 20.05.2005 => 04:18 <=

Cardemonie! czy nie masz malutkich wyrzutów sumienia?
;-)
K.

[cardemon]

> Autor: mesquaki
> Data: 20.05.2005 => 04:18 <=
>
> Cardemonie! czy nie masz malutkich wyrzutów sumienia?
> ;-)

Nie, w żadnym stopniu! Bo to tylko 21:18 czasu Mes. :) :) :)

pzdr. CdM

[Gość: pafcio]

> 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)

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

[mesquaki]

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 :).

[kopperek]

super rozwiązanie i super zagadka! Skąd ten Cardemon bierze takie perełki?!

[kornel-1]

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

[cardemon]

kornel-1 napisał:

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

Niestety rozwiązanie Mesquaki tego wymogu nie spełnia. :(
CdM

[kopperek]

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]

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]

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]

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]

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]

> 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]

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.

Krótki komentarz nr 2

[cardemon]

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]

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]

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]

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]

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]

>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]

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ść: Pafci]

[Gość: kama]

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]

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]

> 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]

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]

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]

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]

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+]

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]

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 +]

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]

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%.

Krótki komentarz nr 3

[cardemon]

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]

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]

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]

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]

> 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

[kopperek]

sorry za literówki, zamiast 41/64 powinno też być 43/64, ale to bez znaczenia.

[Gość: kminnek]

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]

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]

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]

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ć.

Po zastanowieniu się

[Gość: pewny]

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]

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]

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]

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.

[andy._]

Na razie zaklepuję sobie wynik i siadam do sprawdzenia poprawności.

Pozdr.
A._

[Gość: uważny]

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]

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]

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]

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]

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]

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]

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._]

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]

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

[Gość: grzesiek]

ALE GDZIE JEST TO ROZWIĄZANIE ANDY-EGO????

Przeszukalem caly wątek i oprócz kilku luźnych uwag nie widzę
rozwiązania dla 87.5%.

Pytam dlatego, bo sam też myślalem że mam rozwiązanie na 87.5 (nawet je
pochopnie wyslalem), ale znalazlem w nim bląd. Dlatego też chcialbym
zobaczyć rozwiązanie Andy-ego w calej krasie, tak aby móc je przeanalizować.

[kopperek]

dołączam się do gratulacji - tym bardziej że spędziłem nad tym problemem
ostatnie trzy wieczory (bez efektu). No i ciekaw jestem bardzo rozwiązania!
Chyba nie ma na co czekać, nie?:)

pzdr.

[andy._]

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]

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._]

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]

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.

"o tej zagadce można opowiadać godzinami"

[andy._]

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._

lampion

[mesquaki]

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

[mesquaki]

Na przykład, mogłyby być biegunami stany:
BCBCBCB
BCCBCBB
BBCBBCC
CCBBBBC
BBBCCBC
CBBBCCB
CBCCBBB
BBBBBBB
i ich negacje.

?

[andy._]

Trzeba sprawdzić, czy każdy z 16-tu biegunów rózni się od pozostałych 15-tu na
minimum 3 pozycjach
A._

[Gość: grzesiek]

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._]

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]

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._]

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]

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

Okropność

[lapacz_w_zycie]

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._]

...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ść: raffix78]

Zupełnie nie wierzę, że da się wyjśc ponad 50%.
Jesli ma ktoś programik ,który implementuje taką strategię to bardzo proszę o
przesłanie - może wtedy uwierzę, choć wątpię : [e-mail]

[Gość: gosc]

To nie jest sprawa wiary, tylko zrozumienia zagadki i logiki!
Poza tym nie rozumiem jak mozna wierzyc "programikowi ,który implementuje taką
strategię", a nie wielu wywodom, ktore sie tutaj pojawialy?

[Gość: PM]

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.

Podejrzenie nieścisłosci

[Gość: Wątpiący]

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._]

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]

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.

"o tej zagadce można opowiadać godzinami"

[andy._]

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._

"o tej zagadce można opowiadać godzinami"

[andy._]

" ...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._

"o tej zagadce można opowiadać godzinami"

[andy._]

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]

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]

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._]

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]

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._]

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._

[Gość: Ufny]

To równanie N*(W+1)= 2^W wyjasnia ,że zarówno N, jak i W+1 sa potęgami 2 i
okresla liczbę wezłów N=2^W/(W+1), ale to juz banał.Struktura kryształu jest
sympatyczna, ale niekonieczna.Bez kryształu tez zadziała.(?)

[andy._]

Oj, nie zadziała ...
Równanie nie pozwala na jakiekolwiek luki.

Pozdr.
A._

[tororo]

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._]

> 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._

[Gość: darekw]

A to oznacza, że decyduje wiedza matematyczna ...