SPOILER! Kattints ide a szöveg elolvasásához!
szerintem kilenc ember biztosan megmenthetõ! (a tizedik lutri.)
a fekete sapkákat jelöljük egyessel (1) a fehéreket nullával (0)
(a stratégia kísértetiesen hasonlít a számítástechnikában használatos paritás vizsgálathoz.)
a tizedik ember megszámolja, hogy hány fehér és hány fekete sapkát lát maga elõtt a feketék 1-et, a fehérek 0-át. összeadja és kap eg számot 1-9 -ig. ezt kiegészíti párosra, vagyis 1-essel, ha páratlan 0-val ha páros. ezt a számot visszaváltja színre (1-fekete, 0-fehér) és ezt mondja be. (paritásbit=párosságjelzõ, itt az aktuális sorozat összegének párosságát jelzi)
mivel az õ sapkájáról nincs infó ezért az életbenmaradásának esélye 50%
a többiek viszont életben maradhatnak.
hogyan?
nézzük a kilencedik embert, aki nyolc sapkát lát. megszámolja a feketét, fehéret, számra váltja, összeadja.
ismeri tehát a többiek sapkaszinét és hogy páros számú felete volt e, vagy se.ha a tizedik feketét mondott, akkor páratlan számú fekete van a kilenc emberen. ha a kilencedik párosat lát, akkor fekete van rajta, ha páratlant, akkor fehér. ha a tizedik fehéret mondott, akkor páros számú fekete van. ha ekkor a kilencedik páros számú feketét lát, akkor az övé fehér. ha páratlant, akkor fekete.
így a kilencedik tudja a saját sapkája szinét. bemondja, megmenekül.
a nyolcadik (és a többi) feladata annyiban tér el a kilencedikérõl, hogy ha az õt megelõzõ ember fekete sapkás volt, akkor a tizedik ember válaszát (a paritásbitet) ellenkezõjére változtatva folytatja, hiszen ha egy fekete sapkás kilép a sorból, akkor a fekete sapkák száma csökken eggyel, így párosból páratlanra, páratlanból párosra vált az összeg.
így a kilenc meg is menekült.
Egy konkrét példa: (1= fekete, 0=fehér)
a tizedik ezt látja: 110100111
ekkor az összeg (vagyis az egyesek száma):6
így hogy páros legyen 0-t kell hozzáadni, tehát bemondja, hogy fehér.
ekkor a többiek tudják, hogy a paritásbit nulla (p=0)
a kilencedik ezt látja: 10100111 (a saját 1-esét nem)
számol 5 egyest látok, a tizedik szerint páros számú van kilencünkön, tehát rajtam fekete van. bemondja, nyer.
a nyolcadik ezt látja: 0100111
de mivel az elõzõ fekete volt, ezért a paritást ellentettjére változtatja (p=1), vagyis tudja, hogy nyolcukon összesen páratlan számú fekete sapka van, mivel páros számút (4-et) lát, így tudja, hogy rajta fekete van. bemondja, életben marad.
a hetedik ezt látja:100111
mivel elõzõleg feketét mondtak paritás bitet vált (p=0), vagyis tudja, hogy hetükön összesen páros számú sapka van. mivek 4-et lát, tudja, hogy rajta fehér.
bemondja, jó.
a hatodik ezt látja: 00111
nem változtat a paritásbiten, mivel nem fekete esett ki,
a három páratlan szám, p=0, tehát rajta fekete van.
az ötödik ezt látja:0111
de mivel az elõzõ felete volt, paritást vált (p=1)
páratlant (3) lát, a paritásbit szerint is annyinak kell lennie, tehát õ nem módosító, vagyis fehér.
a negyedik ezt látja: 111
p=1, vagyis páratlan, ez stimmel, tehát gehéret mond.
a harmadik ezt látja: 11
p=1, tehát összesen páratla, de kettõt lát csak, így rajta is fekete van.
a másodij ezt látja: 1
paritástvált, mivel a harmadik fekete volt (p=0), vagyis összesen kettõjükön páros számú fekete van, tehát rajta is fekete.
az elsõ nem lát semmit, de mivel az elõzõ fekete volt, így paritást vált, vagyis p=1, azaz összesen páratlan számú fekete sapka van, az meg csak rajta lehet, így bemondja.