Probléma a foglyokkal és sapkákkal kapcsolatban, amelyek színét meg kell határozni
Pihenés / / December 31, 2020
A zárórendszer az összes sapkát látja, de csak „fekete” vagy „fehér” mondatot tud mondani, miközben mindenkit tájékoztat a rejtett információkról. A foglyok nem ismerik a fekete-fehér sapkák teljes számát, kettőnél több lehetőség van. De csak két változatra korlátozódnak, amikor a paritás fogalmáról van szó: a szám lehet páros vagy páratlan.
A probléma megoldásának kulcsa a következő: a foglyok egyetértenek abban, hogy az első válaszadó például "fekete", ha páratlan számú fekete sapkát lát elöl, és "fehéret", ha páros számú fekete sapkát lát sapkák.
Nézzük meg a fenti kép példáját. Az 1. legmagasabb fogoly három fekete sapkát lát maga előtt. Hangosan "feketén" beszél. Ez mindenkinek azt az információt adja, hogy páratlan számú fekete sapka van előttünk. Az első fogoly hibázott a sapka színével, de ez nem ijesztő: ha egyszer szabad helytelenül válaszolni.
A 2. fogoly páratlan számú fekete sapkát lát maga előtt. Megértette, hogy fehér, és helyesen válaszol. A 3. fogoly páros számú fekete sapkát lát, és azt hiszi, hogy fekete sapkát visel, amelyet az első két fogoly látott.
A 4. számú fogoly meghallja a választ, és rájön, hogy páros számú fekete sapkát kell keresnie, mert a háta mögött volt egy fekete, de csak egyet lát előre, és arra a következtetésre jut, hogy a sapkája fekete. Az 5-9. Számú foglyok páratlan számú fekete sapkát keresnek, amelyeket látnak, miközben rájönnek, hogy fehér sapkát viselnek. A sor a tizedik fogolyra kerül. Ha a 9. fogságban páratlan számú fekete sapka látható, az csak egy dolgot jelent - a 10. fogságban fekete sapka van.
Így működne ez az algoritmus bármely hubcaps készlet esetén. Az első résztvevő esetében a hibás válasz valószínűsége 50%, de a páros-páratlan paritásról szóló információ, amelyet megad, lehetővé teszi a többi fogvatartott számára, hogy kitalálja a sapka színét.
Minden válaszadó elkezdi értékelni az előttünk álló páros és páratlan korlátok számát. Ha az elméjében kiszámított szám nem esik egybe azzal, amit lát, akkor a sapkája azonos színű. Ilyen esetben a következő válaszadó minden alkalommal figyelembe veszi, hogy a fennmaradó felső korlátok páratlan-furcsasága megváltozott.
Ez a rejtvény egy TED-Ed videó fordítása.