חידות לוגיות

Zlý král měl ve svém sklepě 1000 lahví dobrého vína. Sousední královna usilovala o to, aby se zlého krále zbavila, a proto poslala svého sluhu, aby králi víno otrávil. Královy stráže však sluhu chytili hned poté, co stihl přidat jed do jedné z lahví. Bohužel nestihli zjistit do které. Výslechem se podařilo zjistit, že jed je tak silný, že i kdyby byl zředěn milionkrát, stále by člověka spolehlivě zabil. A navíc se jeho účinky projeví až po uplynutí jednoho měsíce.
Král se proto rozhodl, že použije některé ze svých vězňů, aby víno ochutnali. Protože byl chytrý, věděl, že místo použití 1000 vezňů (tolik jich neměl) mu stačí obětovat pouze 10, aby zjistil, ve které láhvi se jed nachází. A navíc už po 5 týdnech bude moci v klidu pít ze zbylých lahví.
Jak se mu to podaří?

Show/hide solution:

Nejprve si láhve očíslujeme od 1 do 1000 a vězně očíslujeme od 0 do 9. Vezmeme binární zápis čísla láhve a příslušné bity určují, kterým vězňům dáme z láhve napít.
Po měsíci zjistíme, kteří vězňové zemřeli (příslušné bity budou 1) a podle toho určíme číslo otrávené láhve.
Z toho plyne, že 10 vězňů by nám vystačilo i na 1023 láhví (2¹⁰-1).
Praktická poznámka: Láhve je dobré číslovat podle kvality vína - nejlepší víno s co nejmenším počtem jedničkových bitů, aby se z něj tolik neupíjelo ;-)

» גלריה » חידות לוגיות