Oprawcy miśków II

[uller]

Postanowiłem przepisać do nowego wątku swoją mutacje zagadki z wątku - "Moze
ktos rozwiąze".

Pewni okrutni oprawcy złapali 30 Miśków. Nie zabili oni jednak od razu
wszystkich Miśków tylko dali im szanse na uratowanie życia. Mądre misie
opracowały strategie dzięki której 29 z nich przeżyło.

Ale jak herszt oprawców dowiedział się że tylko jeden Misiek zginął wymyślił
nowa makabryczną łamigłówkę. Każdemu z pozostałych 29 Miśków założyli losowo
czapeczkę albo niebieską albo czerwoną. Żaden Misiek nie wiedział jakiego
koloru czapeczkę miał na głowie, ale każdy z nich widział czapeczki
pozostałych miśków. Miśki nie miały możliwości dania komukolwiek
jakiegokolwiek znaku. Potem zamknięto ich w osobnych celach. Oprawcy przeszli
wszystkie cele w nieznanej nikomu kolejności pytając się każdego Miska
jakiego koloru czapkę ma na głowie. Gdy miś odpowiedział nieprawidłowo
natychmiast został rozstrzelany (jednym strzałem), a gdy odpowiedział
prawidłowo - zachował życie a oprawcy siarczyście klęli tak, że słychać ich
było w całym więzieniu. Inne Miśki słyszały tylko strzały lub przekleństwa
oprawców (nie słyszały odpowiedzi wcześniej pytanych Miśków).
Miśki jednak wiedziały wcześniej o zamiarach swoich oprawców i znowu
opracowały strategię która gwarantowała największej możliwej ich liczbie
przeżycie. Jaka jest ta liczba? (największa liczba Miśków które na pewno
przeżyją)

Pozdrawiam
Uller

[lapacz_w_zycie]

niezłe, daję 14.

lwz

[Gość: grzesiek]

przeżyje 28, albo nawet wszyscy.

przede wszystkim wszystkie misie muszą policzyć ile widzą czewonych czapek
i zapamiętać czy jest to liczba parzysta.

reguła odpowiadania dla pierwszego: jeśli widziałem parzystą liczbę czerwonych
to mówię "niebieska", jeśli nieparzystą - "czerwona".

reguła odpowiadania dla następnych: jeśli pierwszy przeżył to znaczy
że wszystkich czerwonych czapek jest parzysta liczba, jeśli nie przeżył -
nieparzysta. stąd można już wywnioskować co się ma samemu na głowie.

[uller]

Bravo - sam tego nie przewidziałem.
Proponuję jeszcze zmierzyć się z 2 i 3 wariantem.

Pozdrawiam
Uller

[lapacz_w_zycie]

> przeżyje 28, albo nawet wszyscy.
chyba nie do końca...
wersja II różni się zasadniczo od I (jeśli dobrze zrozumiałem) -
w rozwiązaniu z wersji klasycznej wykorzystywana jest nie tylko wiedza o wyniku
próby, ale też o treści odpowiedzi poprzedników. W 'Oprawcy miśków II'
odpowiedzi poprzedników nie są znane.
Mój komplet rozwiązań:
strzały i przekleństwa - 14
strzały - pewnie coś koło 7
cisza - 0

lwz

[uller]

Wszystko zepsułem tymi przekleństwami.
Proponuję jeszcze dwa warianty tej zagadki

2) misie słyszą tylko strzały - nikt nie przeklina.

3) misie nic nie słyszą.

[lapacz_w_zycie]

ups, jaka fatalne pomyłka,
w takim razie podtrzymuję rozwiązanie 14 dla
wersji ze strzałami

lwz

Do Uller - 2 dodatkowe warianty

[Gość: kaem]

Rozwazanie drugiego wariantu chyba nie ma wogóle wiekszego znaczenia, bowiem
jest on praktycznie tym samym wariantem co pierwszy. Jak usłysza strzal to beda
wiedziec ze zle odpowiedzial, a jak strzału nie bedzie to bedzie oznaczac ze
przezył. Czyli brak strzału jest rownoznaczny z przeklenstwami z wariantu
pierwszego.

[uller]

Zgadzam się... prawie. :)
Zapytam się tylko tak aby zasiać ziarno niepewności,
a skąd ktoś wie czy jest tym pierwszym czy nie gdy nie padł strzał?

Pozdrawiam
Uller

[Gość: grzesiek]

W przypadku 3) gdy misie nic nie słyszą odpowiedzią jest ZERO. Jeśli by
jednak kategoryczne pytanie "ile na pewno przeżyje?" zamienić na "ile średnio
przeżyje?" to przypadek 3) jest podobny do zagadki Cardemona z siedmioma
więźniami. W tamtej zagadce okazało się że rozwiązania trzeba szukać w teorii
kodów Hamminga - konkretnie kodu (7,4). Liczba 29 nie jest długością żadnego
kodu Hamminga. Gdyby misiów było 31 to można by to podciągnąć do kodu (31,16),
a tak należy użyć kodu (15,11). Nie tłumaczę co to wszystko znaczy, bo raz że
to już było a dwa że w internecie można znaleść stos informacji na ten temat.
Kod (15,11) daje szansę przeżycia = 1 - 1/2^(15-11) = 93.75%, co pomnożone przez
29 daje trochę ponad 27 miśków.
Ale jak 29 misiów ma użyć kodu (15,11)? Najprościej jeśli każdy z nich
za wczasu (jeszcze przed oglądaniem czapek u innych) wybierze sobie 14 kolegów
i potem będzie patrzył tylko na ich czapki. Być może jakieś kombinowanie
z wieloma (może wszystkimi) podzbiorami 14 kolegów jeszcze zwiększy szansę.

[Gość: grzesiek]

Najpierw napisałem, potem pomyślałem. To jest zawsze zgubne.
Niestety ta zagadka NIE JEST podobna do tamtej o siedmiu skazańcach -
tam można było odpowiedzieć "nie wiem" i odpowiedzialność była grupowa.
Tu każdy miś odpowiada za siebie.

[Gość: kradam]

Tak jak grzesiek, to wydaje się być inną zagadką niż ta o skazańcach. Kolejne
miśki nie słyszą odpowiedzi poprzednich a jedynie jej wynik. A pierwszy z nich
nawet w wariancie skazańców jest losowy.
Wydaje mi się, że _gwarantowaną_ liczbą niezależnie od poniższych wariantów jest
zero.

[kradam]

Tyle, że pytanie jest o strategię gwarantującą ... a nie o liczbę... Uppps. :-)

[uller]

> W przypadku 3) gdy misie nic nie słyszą odpowiedzią jest ZERO.

Niestety nie jest to prawidłowa odpowiedz. Na pewno da sie kogoś uratować :)

[Gość: allygator]

Ale w opisie nie jest napisane, że czapki czerowne i niebieskie są rozdzielone
po równo. To chyba ważne w naszych rozważaniach

[uller]

Trzeba rozpatrzyć wszystkie możliwe przypadki, nawet te kiedy wszystkie Miśki
będa miały czapeczki tego samego koloru. Treść zadania nie wyklucza tego.

Pozdrawiam
Uller.

Oprawcy Miśków II - wariant 3

[uller]

W 3 wariancie łamigłówki choćbyśmy wymyślili jakiś super hiper algorytm to nie
zmieni on faktu, że każdy z miśków będzie miał dokładnie 50% szans na przeżycie.

Ale dla grupy 29 Miśków istnieją takie algorytmy, które zagwarantują przeżycie
co najmniej jednego z nich. Nie jest ważne kto przeżyje, ale liczba ocalonych.

Powodzenia
Uller

[Gość: grzesiek]

Myślę i myślę i coraz mniej wierzę że to jest możliwe, a jednocześnie
jestem coraz bardziej ciekaw ewentualnego rozwiązania. To może byś Uller
podał swoje.

[uller]

Nie ma sprawy, mogę podać swoje rozwiązanie. Na razie jednak nie chciałbym psuć
innym zabawy więc wolałbym przesłać to rozwiązanie na e-mail prywatny. Tak więc
gdzie mam wysłać moją odpowiedź?

Pozdrawiam
Uller

[Gość: grzesiek]

To ja może też jeszcze pomyślę ...

[mesquaki]

Wydaje mi się, że można uratować co najmniej siedmiu, ale muszę jeszcze nad tym
pomyśleć.

[mesquaki]

Myślenie nic ciekawszego nie przyniosło, więc pozostanę przy tych siedmiu.

Wybieramy ośmiu miśków od zadań specjalnych.
Wszyscy głosują zawsze na kolor większościowy, lub czerwony w wypadku równego
rozłożenia widzianych kolorów czapeczek.
Z wyjątkiem ośmiu specjalnych miśków, które widząc sytuację w okolicy remisu
(14:14 lub 13:15), głosują przeciwnie do zasad.

W ten sposób, gdy jest co najmniej 17 czapeczek danego koloru, przeżyją wszyscy
z czapeczkami o tym kolorze, a w pozostałych przypadkach zależy to od tego,
jak rozłożą się kolory czapek specjalnych misiów (x czerwonych i y niebieskich).
13C16N 16-y
14C15N x+y
15C14N 15-x+y
16C13N 16-x
Najmniej miśków (7) przeżyje, jeśli rozkład czapeczek będzie 15C14N i wszystkie
miśki specjalne będą miały czapeczki czerwone.

[Gość: grzesiek]

Dobre!
sam kombinowałem bardzo podobnie, ale z inną liczbą miśków specjalnych -
14 lub 15 i wtedy wychodziło mi że w pewnych szczególnych układach wszystkie
giną. gratuluję pomysłu że liczba miśków specjalnych to 1/4 całości a nie 1/2.

[uller]

Bravo Mesquaki!
To jest pierwsze rozwiązanie które gwarantuje przeżycie conajmniej jednego
miśka, a nawet aż 7!!!
Jeszcze raz moje słowa uznania.

Ale zabawa się jeszcze nie skończyła.
Kto da więcej? :)

Pozdrawiam
Uller