Kapelusze razy 100

[republican]

Jestes dowodca 100 osobowego batalionu, jestescie w
niewoli.
Dowodca sil wroga powiedzial wam ze nazajutrz caly
oddzial bedzie ustawiony w pojedyncza kolumne i kazdy
z was bedzie mial na glowie kapelusz, bialy lub
czarny.
Bedziesz widzial kapelusze wszystkich przed toba i
nie bedziesz widzial kapeluszy z tylu i na twojej
glowie.
Wrog startujac od tylu kolumny bedzie sie pytal
kazdego z was po kolei o kolor kapelusza.
Odpowiedz prawidlowa to wolnosc, bledna to
rozstrzelanie o swicie.
Jako dowodca masz jeden dzien do znalezienia
najlepszej strategii ktora uwolni maximum ludzi.
Kazdy z Was bedzie slyszal odpowiedz na pytanie i
decyzje wroga, tak lub nie.

[smiechowiec]

Jeśli w momencie pytania widzę wszystkie kapelusze poza moim
lub widzę część kapeluszy, a o pozostałych mam wiedzę o ich kolorze wynikającą z wypowiedzi już pytanych żołnierzy i reakcji strażników to mogę powiedzieć, że znam liczbę kapeluszy koloru białego, poza moim.
Skoro wiedzę N białych kapeluszy to istnieją 2 możliwości
- kapeluszy białuch jest N
- kapeluszy białuch jest N + 1
W związku z tym jeśli założę, że liczba białych kapeluszy jest parzysta mogę jednoznacznie podać liczbę N lub N+1.
Pomylić może się jedynie pierwsza osoba gdyż ma 50% szans, że liczba białych kapeluszy jest parzysta.
Jeśli pierwsza osoba nie odzyska wolności to znaczy, że założenie było błędne i całkowita liczba białych kapeluszy jest nieparzysta. Więc każdy z pozostałych osób będzie już wiedziała co powiedzieć uwzględniając zasłyszane informacje oraz to co widzi.

Przykładowo załóżmy, że jest 51 białych kapeluszy.
Pierwszy żołnierz ma czarny kapelusz, więc widząc 51 białych kapeluszy musi założyć, że ma biały i mówi zgodnie z umową, że ma biały kapelusz.
Nie zostaje jednak uwolniony.
W związku z tym, że pozostali żołnierze usłyszeli co się stało mają wiedzę, że kolor pierwszego kapelusza jest czarny, a liczba białych kapeluszy jest nieparzysta.
Więcej pomyłek już być nie może.
II widząc 50 białych kapeluszy wie, że kolor jego kapelusza jest biały.
Trzeci widząc 49 białych kapeluszy wie, że kolor jego kapelusza jest czarny, a gdyby widział 48 białych to znaczy, że ma czarny itd.

[republican]

Gratuluje.
Jak zwykle zepusles mi cala przyjemnosc.

[smiechowiec]

> Jak zwykle zepusles mi cala przyjemnosc.
Bardzo przepraszam, następnym razem postaram się powstrzymać 48 godzin.

[Gość: Pablo]

Uważam, że Twoje rozwiązanie jest słabe.
Bo co jeśli 100% ma biały kapelusz?

[dr.bo]

Powtórzę rozwiązanie Śmiechowca, ale chciałbym uwypuklić fakt, że informacja od wroga jest całkowicie zbędna.

Ustalamy, że ostatni podaje w sposób zakodowany, czy widzi parzystą liczbę kapeluszy białych. "Biały" oznacza "tak", "czarny" - "nie". Ma 50% szans na przeżycie.
Koniec. Reszta niech po prostu liczy.

Dla ułatwienia można im podać prosty algorytm:
1. widzę n białych kapeluszy
2. usłyszałem m razy "biały" zanim nadeszła moja kolej.
3. m i n są jednocześnie parzyste albo nieparzyste: mówię "biały"
4. else: mówię "czarny"
5. idę do domu.

Wynik: przeciętnie 99,5 uratowanych.

[hetman_sloniowy]

A jaka jest optymalna strategia, jeśli kolorów kapeluszy jest N, gdzie N jest
liczbą naturalną z przedziału od 1 do 100 włącznie ?

Oczywiście dla każdego N należy przyjąć, że poszczególne możliwe kolory
kapeluszy są znane "uczestnikom zabawy".

[dr.bo]

Myślę, że to jest na tyle odmienny problem, że warto by było umieścić go w
osobnym wątku.
Na pierwszy rzut oka można uratować co najmniej połowę, np. przyjmując zasadę,
że co druga osoba wymienia kolor kapelusza osoby stojącej przed nią.

Ponadto prosiłbym o doprecyzowanie: czy zgadujący znają N i czy każdy kolor musi
wystąpić.

[hetman_sloniowy]

dr.bo napisał:

> Ponadto prosiłbym o doprecyzowanie: czy zgadujący znają N i czy każdy kolor mus
> i
> wystąpić.

Tak, znają. Poza tym co napisałem, niech analogia będzie pełna, czyli nie musi
być tak, że wystąpi każdy z zapowiedzianych kolorów (w wersji podanej przez
republicana opcja, że wystąpiły same czarne albo same białe nie była wykluczona).

[smiechowiec]

Ja bym zaproponował rozwiązanie analogiczne tzn
pierwszych N wojaków ma przypisane kolejne kolory.
Jeżeli żołnierz widzi parzystą liczbę kapeluszy w danym kolorze wtedy wypowiada ten kolor, w przeciwnym wypadku inny.
Pierwszych N ma szansę na przeżycie 1/N, pozostali 1.

[dr.bo]

Ale jeżeli N jest większe niż połowa zgadujących to chyba lepiej zastosować
wariant "co drugi podaje kolor kapelusza przed nim". Wtedy przeżyje połowa z n
zgadujących (minus jeden, jeżeli n jest nieparzyste) z prawdopodobieństwem
równym 1 a pozostali z prawdopodobieństwem 1/N każdy.
Dla n zgadujących przeciętnie:
n/2 + n/2N gdy n jest parzyste
(n-1)/2 + (n+1)/2N gdy n jest nieparzyste
będzie wolnych.

[smiechowiec]

dr.bo napisał:
> Ale jeżeli N jest większe niż połowa zgadujących to chyba lepiej zastosować
> wariant "co drugi podaje kolor kapelusza przed nim".
>Wtedy przeżyje połowa z n zgadujących

Wydaje mi się, że zawsze powinno przeżyć więcej osób, pod warunkiem, że założymy potrafią liczyć.
Algorytm można ulepszyć w ten sposób
- dla każdego koloru przypiszemy kolejną liczbę 1,2,3 ...
- pierwszy pytany podaje kolor, który wynika z sumy wszystkich widzianych przez niego kolorów.

Przykład dla 3 osób - 3 kolory 1, 2, 3.
Pierwszy widzi kolory 3 i 2 ich suma to 5, a reszta 5 przez 3 = 2
więc podaje kolor numer 2.
Drugi widzi kolor numer 3 wiec wie, że ma kolor 2, bo reszta z dzielenia 3 przez 3 = 0, a on wie, że jej wartość to 2 więc mówi 2.
Kolejny analogicznie oblicza sobie, że jego kolor to 3 bo 2 - 2 = 0,
więc jedyny kolor jaki mu zostaje to taki, który przy dzieleniu przez 3 daje resztę 0.