.: Rychlé menu: navigace .:. odkazy .:. kategorie .:. vyhledávání .:. archivy .:. autoři :.  

08.12.2003



Černé a bílé klobouky. Velmi pěkná hádanka. Řešení je jednoduché. Ale přijít na něj je docela fuška — i když — jak pro koho. Nebojte se, v zadání není chyba a celý úkol je řešitelný.

Zadání:
46 lidí čeká následující zkouška:
Budou postaveni na dlouhé schodiště tak, aby vylosovaný šťastlivec stojící nahoře viděl na všechny své kolegy a ti ostatní viděli už jen na ty pod sebou. Krom prvního dostane každý na hlavu černý nebo bílý klobouk. Počet černých ani bílych ovšem není znám. Šťastlivec stojící nahoře řekne pouze „černá” nebo „bílá” a člověk stojící pod ním musí poznat (nebo si spočítat), jakou barvu klobouku má na hlavě. Opět může říci „černá” nebo „bílá” a postupně všichni ostatní musí říct barvu klobouku, který mají na hlavě. Pokud se jen jeden splete, budou všichni hlavním chodem na domorodé hostině. Lidé přemýšleli celou noc, až vymysleli taktiku, s jejíž pomocí se ani jeden z nich nemůže splést. Na copak lidé přišli ve stavu nejvyšší nouze?

Až na správné řešení někdo přijde, zveřejním i zdroj, ze kterého tuto krásnou hádanku mám. Zatím linkovat nebudu, protože na oné stránce je i řešení.

Tak tady je původní zadání i s řešením:


Zadal White Dog, 08.12.2003 17:31:03, 12 komentářů...,
TrackBack URL tohoto příspěvku je http://blog.maly.cz/tb.php/639

Zpět na článek

HotLinks
Reakce na jiných stránkách (TrackBack)
Prevazne Neskodny...: Hádanka, tentokrát na tento den
Zobrazit komentáře v chronologickém pořadí

 - svetlo (web)

nejak nevidim co je na tom sloziteho?
    

Re: - White Dog (web)

Výborně - správné řešení {smile}
    


První udá paritu - Ivan (web)

podle dohodnutého systému - řekněme které barvy klobouků je lichý počet; všichni následující pak mají při lichém počtu kloboučníků (což je tady splněno - 45) dostatek údajů pro doplnění jednoho bitu (barvy svého klóbrce) z toho, co řekli ti předcházející a z toho co vidí pod sebou {smile}
    

Re: První udá paritu - Arthur Dent (web)

Přesně tohle jsem WhiteDogovi popisoval velmi podobnými slovy... V podstatě je to jak v mariáši: Jeden naznačí a ostatní musí dopočítat...
    


 - Trillian (web)

a co když budou všechny klobouky bílé?
    

Re: - Arthur Dent (web)

To nevadí...
    


Asi mi něco uniká - Sokolík (web)

Omlouvám se, vím, že po sedmičce vína se nemám do takových úvah pouštět, ale co když ten první prostě řekne tu barvu, co má ten pod ním a ten jí tím pádem ví a vidí zase na toho pod ním. Něco mi uniklo ?
    

Re: Asi mi něco uniká - Arthur Dent (web)

Ano, ale mně to napoprvé uniklo taky: Každý (tedy druhý a další) musí říct tu barvu, kterou má sám na hlavě... Na svůj klobouk si ovšem nevidí...

Jen ten první může říct cokoliv, ten žádný klobouk nemá...
    


Pro méně chápavé... - pixy (web)

(... kterých je nás asi většina):

Ten první nemá klobouk, takže nemusí říkat, co má sám na hlavě (což už ostatní musí) - takže může říct cokoli. Když se všichni předem dohodnou, že ten první spočítá, jestli vidí sudý nebo lichý počet (třeba) černých klobouků, tak to ostatním postačí (viz dál). Ale protože podle pravidel i ten první může říct jen "černá" nebo "bílá", tak se dohodnou, že v jeho případě bude znamenat černá=lichý počet, bílá=sudý počet (i nula).

Takže se koukne a uvidí pod sebou řekněme 23 černých klobouků, takže řekne "černá" (kód pro lichý počet). Druhý v řadě tím pádem ví, že (včetně něj) je v řadě lichý počet černých klobouků. A buďto jich sám vidí taky lichý počet (to znamená, že sám na hlavě černý klobouk mít nemůže a má tedy bílý), nebo jich vidí naopak sudý počet (a tím pádem ví, že přebývající černý má na hlavě on sám). Takže může hrdě a spolehlivě říct barvu svého klobouku.

Ten pod ním postupuje stejně - ví, že na začátku bylo černých klobouků licho. Pokud jeho předchůdce oznámil, že má bílý klobouk, tak ví, že černých je pořád lichý počet - a pokud má jeho předchůdce černý klobouk, ví, že se parita černých změnila na sudou.

A tak postupují všichni. Každý na začátku vidí, kolik klobouků má pod sebou, slyší původní paritu (sudo/licho) a při každém ohlášení černého klobouku tu paritu změní. Ten poslední už nevidí nic (tedy nula klobouků, a nula je sudá) - když k němu doputuje infomace o sudé paritě, ví, že má bílý klobouk - když se k němu dostane lichá parita, musí zbývat lichý počet černých klobouků - tedy jeden, ten jeho.

BTW - na rozdíl od původního řešení s *touhle* domluvou nezáleží na tom, jestli je všech lidí sudý, nebo lichý počet. Bude to fungovat úplně stejně s 45, 46, nebo 47 lidmi. {smile}
    

Re: Pro méně chápavé... - Arthur Dent (web)

No, moje řešení bylo naprosto stejné... Také jsem se pak divil, když jsem se dočetl v tom řešení, že je nějak důležité, že jedněch je sudý a druhých lichý počet.

A podruhé jsem se divil, že řešení je třeba "vymislet". {smile}
    

Re: Pro méně chápavé... - Ivan (web)

Způsob domluvy určuje použitelnost pro obecný případ (pixy) a pro případ s lichým počtem klobouků (to co jsem měl na mysli já a co je i v řešení) - pokud domluva zní, že první hlásí barvu, ve které je zastoupený lichý počet kobouků, bude to fungovat v zadaném případě, ale pro sudý počet kloubouků je lichost nebo sudost stejná pro bílou i černou množinu, takže by načínatel musel buď mlčet nebo hlásit černou i bílou (podle skladby klobouků). Způsob, který jste navrhli vy, kdy se ohlášenou barvou kóduje parita vybrané barvy, je pochopitelně univerzálnější {smile}
    
HotLinks
Zpět na článek