A Nizhny Novgorod portál
Este a kannibál több gnómot is fogott, és reggelire evett. Jó hangulatban maradt, úgy döntött, hogy több gnómnak esélyt ad a menekülésre és megmagyarázza a feltételeket.
- Másnap reggel - felelte -, építek önt egy oszlopba, és véletlenszerűen két színű kalapot (piros és kék) helyezek el. "Az oszlopban szereplő utolsó óta megkérdezem, milyen színű a sapka. Hagyom el, azok, akik rossz színt hívnak, majd meglátják mindazokat, akik állnak előttetek, és hallják a válogatott válaszokat, de senki nem látja a sapka színeit, csak egy szót mondhat: "piros" vagy " kék ", különben egyszerre eszem."
A gnómok nem ismerik a vörös és a kék kalapok arányát. Nincs további jelzés (intonáció, válaszok szüneteltetése stb.).
Mindazonáltal, az éjszaka folyamán a gnómok a válaszok sorrendjével jöttek létre, amely ezeken a körülményeken keresztül biztosította mindazok túlélését, akik közül az egyiken kívül maradt (ennek ellenére esélye volt a túlélésre).
Kérdés: milyen módon jöttek fel a gnómok?
VÁLASZ
Az érvelés menetrendje
Egyszerű megoldások, amikor minden törpe például a fej előtti színt hívja, nem felel meg. Ebben az esetben a gnómok az egyiken ismerik a színüket, és másoknak meg kell áldozniuk magukat az alsóbbrendű megmentés érdekében. Nem felel meg.
Képzeljük el egy pillanatra, hogy nincsenek korlátozások a gnómok közötti kommunikációra. Az első gnóm képes lesz a többi sapka színeinek hangjára. De sajnos senki sem tud segíteni: senki sem látja a sapkáját. A többi opció nélküli gnómnak csak a kupak színeit kell beszélnie - különben a megoldás nem érhető el. Csak az első törpe engedheti meg magának azt a luxust, hogy a túlélésre egy bizonyos kódgondolatot átad, amelynek segítségével túlélhetik.
Tehát csak az első törpe, aki látja az előtte álló embereket, képes titkosítani néhány információt a többieknek. De mit lehet titkosítani, ha a válasz csak 2: "piros" vagy "kék"?
Az a tény, hogy nem kell átvinni a teljes sorozatot. Minden következő törpe ugyanazokkal az információkkal rendelkezik, mint mindenki más: látja a kupakokat, és meglátja korábbi kollégáinak válaszait szerencsétlenségben. Az első törpének (és az összes többi törpének) azt mondja neki, hogy el kell különíteni az aktuális törpének többi részéről az ő sapka színének kiszámítását.
A válaszok két változatában lehet például titkosítani, például "egyenletes" és "furcsa". Ezután vidd be a vörös színt 1-nek, és a kék 0 lesz. Az első gnóm összefoglalja a többi sapka színeit, ezzel a kóddal. És az eredmény hangosan jelent meg (pl. Piros - "egyenletes", "kék" - furcsa - a törpöknek egész éjjel meg kell érteniük).
A második törpe, miután hallotta a titkosítást, összefoglalja mindazokat, akik előretekintenek. Ha az eredmény egybeesik azzal, amit az első törpe mondott, akkor a sapka színe nem befolyásolta a teljes összeget. Tehát "nulla" - kék. Ha az eredmény megváltozott, akkor ez az "egység" - vörös.
A harmadik és a későbbi gnómok nemcsak az előttük levőket, hanem az előző gnómok válaszát is figyelembe veszik. És hasonlítsa össze az eredményt az első gnóm titkosításával, számítva a különbséget (kupakjának színe).
Ez a módszer lehetővé teszi, hogy túlélje az N-1 gnómot. A gnómok száma nem számít, a probléma megoldható bármelyik N. Az első gnóm nem feltétlenül meghal: 50% -os valószínűséggel a kódolás egybeeshet a sapka színével, majd élve és jól marad.
Ui Azt mondják, hogy ezt a feladatot egy interjúban kínálják a Microsoftban